6

Как найти это минимальное число на интуитивном уровне - понятно (см. рисунок)

введите сюда описание изображения

Пусть задана сторона квадрата n, тогда это число равняется:

min = 4 + (n^2 - (3*floor(n/2)^2 + ceil(n/2)^2) (1)

то есть для четных n, min = 4, а для нечётных min = 4 + кол-во единичных квадратов

Но непонятно, как формально доказать формулу (1)?

То есть что вот это

(n^2 - (3*floor(n/2)^2 + ceil(n/2)^2)

есть ни что иное, как минимально необходимое количество единичных квадратов.

update

как оказалось, формула 1 не оптимальна в общем случае (см пример @Harry)

Тогда вопрос:

Как найти минимальное число квадратов кроме самого себя, которыми можно покрыть этот квадрат ?

5
  • Вам надо доказать формулу для вашего решения, или доказать, что такое ваше решение - оптимальное? Вообще-то квадрат покрывается одном квадратом, кстати :)
    – Harry
    15 сен 2018 в 15:08
  • @Harry что это решение оптимально ) ну и понятно что покрытие самим собой не учитываем, ввиду тривиальности
    – ampawd
    15 сен 2018 в 15:12
  • А оно и не оптимально в общем случае...
    – Harry
    15 сен 2018 в 15:24
  • @Harry это почему ?
    – ampawd
    15 сен 2018 в 15:24
  • Для 7X7 ответ: 9. Задача не очень тривиальная, есть сведение к простым множителям, но дальше хорошей формулы нет: 1, 2 6 мар 2020 в 5:36

1 ответ 1

4

В общем случае ваше решение не оптимально. Для доказательства, к счастью, достаточно контрпримера - вот он:

введите сюда описание изображения

Слева - ваше решение, справа - немного получше (не буду утверждать, что оптимальное).

Тьфу, ну я даю... Тут же вообще можно было поделить квадрат 9x9 на 9 квадратов 3x3! Ладно, оставлю уж свой позорняк... :)

12
  • 4
    мдауж, тривиальность этой задачи все больше и больше улетучивается
    – ampawd
    15 сен 2018 в 15:32
  • 1
    Недаром я с детства не очень любил геометрию :)
    – Harry
    15 сен 2018 в 15:34
  • 1
    @Kromster правильно казалось, тут вобщн весь вопрос в том, чтобы найти оптимальную формулу
    – ampawd
    16 сен 2018 в 9:58
  • 2
    @Kromster Ну конечно, если кардинально изменить вопрос по ходу дела - то все ответы на предыдущий будут не более чем комментарии :) Вы не пробовали задачку "найти тройку чисел, сумма квадратов первых двух равна квадрату третьего" сменить на "а для n-ой степени?", а в ответ на "таких нет" опять изменить вопрос на "доказать, что"?... :) Тем более что задача - судя по тому, что ей уже скоро 100 лет, а формулы так и нет - как минимум простого решения не имеет...
    – Harry
    17 сен 2018 в 4:38
  • 1
    Вот поэтому я на такие "мутные" вопросы и не отвечаю, пока не получу от ТС нормальной формулировки. А после ее получения и ответа - отправляю задавать новый вопрос, а не дополнять старый. В данном же случае, данный ответ, что на изначальный вопрос, что на текущий - скорее комментарий, а не ответ.
    – Kromster
    17 сен 2018 в 5:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.