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

Проект МЦНМО
при участии
школы 57
Задача 65839
Темы:    [ Процессы и операции ]
[ Четность и нечетность ]
[ Принцип крайнего (прочее) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Вялый М.Н.

Аня, Боря и Витя сидят по кругу за столом и едят орехи. Сначала все орехи у Ани. Она делит их поровну между Борей и Витей, а остаток (если он есть) съедает. Затем все повторяется: каждый следующий (по часовой стрелке) делит имеющиеся у него орехи поровну между соседями, а остаток съедает. Орехов много (больше 3). Докажите, что:
  a) хотя бы один орех будет съеден;
  б) все орехи не будут съедены.


Решение

  a) Пусть на n-м шаге у раздающего an орехов, а у следующего bn орехов (у третьего орехов нет). Предположим, что an всегда чётно. Тогда
an+1 = bn + ½ an,  bn+1 = ½ an  для всех n, поэтому  an+1 – 2bn+1 = (bn + ½ an) – an = – ½ (an – 2bn),  то есть число  |an – 2bn|  на каждом шаге уменьшается вдвое. Поскольку, однако,  a1 – 2b1 ≠ 0,  то на каком-то шаге разность  an – 2bn  должна стать нецелой. Противоречие.

  б) На каждом шаге число орехов уменьшается не более чем на 1. Если орехов всегда больше трёх, все доказано. В противном случае рассмотрим момент, когда впервые останется ровно три ореха. Получится обязательно позиция  (2, 1)  (в любой момент, кроме начального,  an ≥ bn > 0).  Далее она повторяется до бесконечности.

Замечания

баллы: 3 + 3

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

олимпиада
Название Турнир городов
Турнир
Номер 27
Дата 2005/2006
вариант
Вариант весенний тур, тренировочный вариант, 8-9 класс
задача
Номер 4

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

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