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