|
|
 |
Условие
При каком наименьшем n квадрат n×n можно разрезать на квадраты 40×40 и 49×49 так, чтобы квадраты обоих видов присутствовали?
Решение
Заметим, что при n = 2000 = 40·49 + 40 требуемое разрезание существует (рис. слева).
Допустим, что найдётся квадрат n×n, где n < 2000, удовлетворяющий условию. Тогда в нём можно выбрать столбец (строку), пересекающий как квадрат 40×40, так и квадрат 49×49; таковым, например, окажется один из выделенных на рисунке справа трёх рядов.
Пусть в выбранном ряду a квадратов 40×40 и b квадратов 49×49. Тогда 40a + 49b = n, где a ≥ 1 и b ≥ 1.
Пусть i-й столбец (1 ≤ i ≤ n) квадрата n×n пересекается с ai квадратами 40×40 и bi квадратами 49×49. Тогда из равенства
40(ai – a) + 49(bi – b) = 0 следует, что ai – a делится на 49, bi – b делится на 40, и если ai ≠ a, то bi ≠ b. В этом случае, если b < 40, то bi ≥ 41 и n ≥ 2009, а если b ≥ 40, то
n ≥ 49·40 + 40 = 2000, так как a ≥ 1.
Значит, если n < 2000, то для всех i, 1 ≤ i ≤ n, ai = a, bi = b. Следовательно, первый столбец пересекается с a квадратами 40×40 и первые 40 столбцов с другими квадратами 40×40 не пересекаются.
Аналогично следующие a квадратов 40×40 целиком содержатся в столбцах 41–80. Тогда следующие квадраты 49×49 располагаются в столбцах 50–98, и т.д. до столбца с номером 40·49. Далее можно отрезать первые 40·49 столбцов и повторить рассуждение с оставшимися.
В итоге получаем, что n делится на 40·49, то есть n = k·40·49. Но уравнение 40a + 49b = 40·49 при a ≥ 1, b ≥ 1 целых корней не имеет. Значит,
n ≥ 2·40·49 > 2000. Противоречие.
Ответ
n = 2000.
