Имеются двое песочных часов — на 7 минут и на 11 минут. Яйцо варится 15 минут. Как отмерить это время при помощи имеющихся часов?

   Решение

Темы:    [ Разрезания на части, обладающие специальными свойствами ] [ Уравнения в целых числах ] [ Делимость чисел. Общие свойства ] [ Доказательство от противного ]

Сложность: 4 Классы: 8,9,10

Прислать комментарий

Условие

При каком наименьшем 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 пересекается с 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.

Источники и прецеденты использования