Саша и Миша играют в игру: сначала по очереди называют число от 1 до 213 (первым называет Миша, числа должны быть разными). Затем каждый считает количество различных прямоугольников с целыми сторонами, периметр которых равен названному числу. Побеждает тот, у кого число прямоугольников окажется больше. Какое число должен назвать Миша, чтобы победить? Прямоугольники, отличающиеся поворотом, считаются одинаковыми. Например, прямоугольники 2×3 и 3×2 одинаковые.

Предыдущий
вопрос Следующий
вопрос

Мы заметим, что количество прямоугольников с целыми сторонами и периметром равным 2n равно числу целых делителей числа n.

Сначала посчитаем количество прямоугольников для каждого числа от 1 до 213 (для удобства можем использовать таблицу):

1 - 1 прямоугольник (1x1)
2 - 2 прямоугольника (1x2, 2x1)
3 - 2 прямоугольника (1x3, 3x1)
4 - 3 прямоугольника (1x4, 2x2, 4x1)
5 - 2 прямоугольника (1x5, 5x1)
...
23 - 4 прямоугольника (1x23, 23x1, 2x11, 11x2)
...
40 - 6 прямоугольников (1x40, 40x1, 2x20, 20x2, 4x10, 10x4)
...

И так далее. Чтобы выиграть, Миша должен выбрать такое число n, для которого количество целых делителей максимально. Таким образом, нам нужно найти число с наибольшим числом делителей в данном интервале от 1 до 213.

Если мы посмотрим на таблицу, то увидим, что число 48 имеет 10 целых делителей (1, 2, 3, 4, 6, 8, 12, 16, 24, 48). Это самое большое количество делителей среди чисел от 1 до 213.

Таким образом, Миша должен выбрать число 48, чтобы победить.