Форум умных людей

конкурс на разрезание проводится следующим образом: сирион придумывает два целых числа m и n, а мунлайт с жекасом пытаются разрезать прямоугольник m*n на квадраты.
выигрывает тот, у кого количество квадратов получится меньше.
разница в том, что жекас выполняет поиск среди всех разрезаний на квадраты с целочисленными длинами сторон, а мунлайт ищет разрезания на квадраты с рациональными длинами сторон.
сможет ли мунлайт победить?

сирион он же хитрый
такие числа придумает  - уууууу.

Первое что приходит в голову - разложить дробь m/n в цепную и найти сумму всех членов. Это и будет минимальное число квадратов. Если решение другое то это будет очень интересно.

пример минимального разрезания:
прямоугольник 5*6 разрезается на два 3*3 и три 2*2, итого пять квадратов.

цепная дробь "советует" отрезать квадрат с торца, т.е., один 5*5 и пять 1*1, итого шесть квадратов.  не минимально.

имеется в виду, сможет ли мунлайт победить при некоторых загаданных мной m и n?

да, не исключается возможность подкупа мунлайтом ведущего для получения благоприятных m и n

минимальный такой прямоугольник имеет полупериметр равный
Показать скрытый текст

во всяком случае меньше найти не удалось.

здесь показано как можно разрезать прямоугольник 25 x 23.
Показать скрытый текст

минимальный прямоугольник это 19 x 17.

жекас по секрету сказал, что смог бы разрезать прямоугольники 23*25 и 46*50 на 8 квадратов каждый, и это предел

а что там с 17*19 ?

Да жекас прав. И с 19*17 не получается. 19*17 и 38*34 оба делятся на 9 квадратов.

25x23
Показать скрытый текст

а разрежется прямоугольник 69х61 на
-  8 квадратов??
-  9 квадратов?

http://demonstrations.wolfram.com/MrsPerkinssQuilts/

мне уже пора признаться, что я - гадский гад, предложивший не решённую проблему под видом задачки?

:-)

допустим что кто-то заявит что он нашёл прямоугольник который можно разрезать на 100500 рациональных квадратов и не менее чем на 100501 целых квадратов. как бы он смог это (второе утверждение) доказать?
 :-)

я могу сказать только то что среди прямоугольников которые можно разрезать не более чем на 12 квадратов таких с большой вероятностью нет.

как он сможет доказать - это проблема доказывающего )

ну, а применительно к этому конкурсу мы считаем, что у сириона есть компьютер, выполняющий бесконечный цикл за 4 секунды