Разделы 
Дополнительно
Задача по математике - 3758
2019-06-16 
По окружности расположено несколько черных и белых фишек. Двое по очереди проделывают такую операцию: первый убирает все черные фишки, имеющие белого соседа (хотя бы с одной стороны), а второй после этого убирает все белые фишки, имеющие черного соседа. Так они делают до тех пор, пока не останутся все фишки одного цвета.
а) Пусть вначале было 40 фишек. Может ли случиться, что после того, как каждый сделает два хода, на окружности останется одна фишка?
б)* На окружности сначала было 1000 фишек. Через какое наименьшее число ходов на окружности может остаться одна фишка?
Решение:
.
На рис. показан пример расстановки 41 фишки; возле каждой фишки написан ее ранг - число, показывающее, за сколько ходов от конца она будет убрана. Строить такую расстановку удобно «с конца»; к остающейся последней черной фишке ранга 0 добавить два белых ранга 1, рядом с каждой из них добавить две черные ранга 2 (с той и другой стороны), рядом с каждой из черных - две белые ранга 3 и т. д. Ясно, что этот способ дает на каждом шагу максимально возможное число фишек соответствующего ранга. Тем самым для каждого $t$ получается расстановка с наибольшим возможным числом $a_t = b_t + w_t$ фишек - $b_t$ черных и $w_t$ белых, которая может за $t$ ходов превратиться в одну черную фишку ($b_0 = 1, w_0 = 0$); правило для последовательного вычисления ($b_t, w_t$) очень простое: при переходе от $t$ к $t + 1$ большее из чисел $b_t$, $w_t$ не меняется, а к меньшему добавляется удвоенное большее:
Для решения задачи а) достаточно из 41 точки на рис. выкинуть одну фишку ранга 4, не влияющую на ситуацию после первого хода (т. е. стоящую рядом с другой фишкой «4»), - например, для сохранения симметрии, отмеченную звездочкой.
Переход от 1000 фишек к одной не может произойти менее чем за 8 ходов, поскольку, как видно из таблицы, $a_7 = 577 < 1000$. Пример ровно с 1000 фишками можно получить из Максимальной расстановки для 8 ходов с $a_8 = 1393$ фишками, выбросив 393 фишки ранга 8, не влияющие на ситуацию после первого хода - это можно сделать, поскольку $2 \cdot 408 = 816$ фишек ранга 8, размещаясь среди 577 фишек ранга не более 7, образуют не менее $816 - 577 = 239$ пар стоящих рядом фишек.
Ответы: а) да, б) 8 ходов (каждый игрок - по 4 хода)
По окружности расположено несколько черных и белых фишек. Двое по очереди проделывают такую операцию: первый убирает все черные фишки, имеющие белого соседа (хотя бы с одной стороны), а второй после этого убирает все белые фишки, имеющие черного соседа. Так они делают до тех пор, пока не останутся все фишки одного цвета.
а) Пусть вначале было 40 фишек. Может ли случиться, что после того, как каждый сделает два хода, на окружности останется одна фишка?
б)* На окружности сначала было 1000 фишек. Через какое наименьшее число ходов на окружности может остаться одна фишка?
Решение:
.
На рис. показан пример расстановки 41 фишки; возле каждой фишки написан ее ранг - число, показывающее, за сколько ходов от конца она будет убрана. Строить такую расстановку удобно «с конца»; к остающейся последней черной фишке ранга 0 добавить два белых ранга 1, рядом с каждой из них добавить две черные ранга 2 (с той и другой стороны), рядом с каждой из черных - две белые ранга 3 и т. д. Ясно, что этот способ дает на каждом шагу максимально возможное число фишек соответствующего ранга. Тем самым для каждого $t$ получается расстановка с наибольшим возможным числом $a_t = b_t + w_t$ фишек - $b_t$ черных и $w_t$ белых, которая может за $t$ ходов превратиться в одну черную фишку ($b_0 = 1, w_0 = 0$); правило для последовательного вычисления ($b_t, w_t$) очень простое: при переходе от $t$ к $t + 1$ большее из чисел $b_t$, $w_t$ не меняется, а к меньшему добавляется удвоенное большее:
Для решения задачи а) достаточно из 41 точки на рис. выкинуть одну фишку ранга 4, не влияющую на ситуацию после первого хода (т. е. стоящую рядом с другой фишкой «4»), - например, для сохранения симметрии, отмеченную звездочкой.
Переход от 1000 фишек к одной не может произойти менее чем за 8 ходов, поскольку, как видно из таблицы, $a_7 = 577 < 1000$. Пример ровно с 1000 фишками можно получить из Максимальной расстановки для 8 ходов с $a_8 = 1393$ фишками, выбросив 393 фишки ранга 8, не влияющие на ситуацию после первого хода - это можно сделать, поскольку $2 \cdot 408 = 816$ фишек ранга 8, размещаясь среди 577 фишек ранга не более 7, образуют не менее $816 - 577 = 239$ пар стоящих рядом фишек.
Ответы: а) да, б) 8 ходов (каждый игрок - по 4 хода)
