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

1 ответ 1

4

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

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

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

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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