ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 110034
Темы:    [ Разрезания на части, обладающие специальными свойствами ]
[ Уравнения в целых числах ]
[ Делимость чисел. Общие свойства ]
[ Доказательство от противного ]
Сложность: 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 пересекается с 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 ≤ nai = 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.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2000
Этап
Вариант 4
Класс
Класс 10
задача
Номер 00.4.10.4
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2000
Этап
Вариант 4
Класс
Класс 11
задача
Номер 00.4.11.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .