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

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

Условие

По кругу стоят 99 детей, изначально у каждого есть мячик. Ежеминутно каждый ребёнок с мячиком кидает свой мячик одному из двух соседей; при этом, если два мячика попадают к одному ребёнку, то один из этих мячиков теряется безвозвратно. Через какое наименьшее время у детей может остаться только один мячик?


Решение

  Занумеруем детей и мячики по часовой стрелке от 1 до 99.
  Пример. Пусть ребята 1 и 2 перебрасывают первый мячик друг другу. Остальные мячики с нечётными номерами всегда перекидываются против часовой стрелки, пока не попадают к второму ребёнку, который их выбрасывает (это происходит через нечётное число минут, и он в этот момент получает еще первый мячик). Мячики с чётными номерами перекидываются по часовой стрелке, пока не попадают к первому ребёнку, который их выбрасывает (после чётного числа минут первый мячик к нему возвращается). Нетрудно видеть, что после 98 бросков все мячики, кроме первого, будут выброшены.
  Оценка. Нам удобнее считать, что мячики не теряются, а склеиваются (с сохранением всех номеров) и собираются в конце у первого ребёнка. Пусть есть способ собрать у него все мячики за n минут. Если n нечётно, первый мячик обошёл полный круг (в противном случае он возвращается к первому ребёнку только через чётное число минут), то есть  n ≥ 99.  Если же n чётно, то второй мячик обошёл полный круг без одного шага (иначе он попадает к первому ребёнку только через нечётное число минут), то есть  n ≥ 98.


Ответ

Через 98 минут.

Замечания

7 баллов

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

олимпиада
Название Турнир городов
Турнир
Номер 29
Дата 2007/2008
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
задача
Номер 5

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

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