Олимпиадная задача по математике: разрезание квадрата на 40×40 и 49×49 (8-10 класс)

  Заметим, что при  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 пересекается с a_i квадратами 40×40 и b_i квадратами 49×49. Тогда из равенства  40(a_i – a) + 49(b_i – b) = 0  следует, что  a_i – a  делится на 49,  b_i – b  делится на 40, и если  a_i ≠ a,  то  b_i ≠ b.  В этом случае, если  b < 40,  то  b_i ≥ 41  и  n ≥ 2009,  а если  b ≥ 40,  то

n ≥ 49·40 + 40 = 2000,  так как  a ≥ 1.

  Значит, если  n < 2000,  то для всех i,  1 ≤ i ≤ n,  a_i = a,  b_i = 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.