Солдаты Конвея
Солдаты Конвея — математическая головоломка, предложенная Джоном Конвеем в 1961 году.
Описание[править | править код]
Доска разделена горизонтальной линией, которая простирается до бесконечности. Над линией расположены пустые ячейки, а под линией — произвольное количество фишек. Ход состоит из того, что одна из фишек перепрыгивает через соседнюю на пустую ячейку, вертикально или горизонтально (но не по диагонали), съедая при этом фишку, через которую перепрыгнула. Цель головоломки состоит в том, чтобы разместить солдата как можно выше горизонтальной линии.
Результаты[править | править код]
Конвей доказал, что, независимо от используемой стратегии, не существует конечной последовательности ходов, которая позволит солдату продвинуться более чем на четыре ряда выше горизонтальной линии. В его доказательстве используется полуинвариант — сумма по всем фишкам тщательно подобранных весов на клетках. Он доказал, что общий вес может только уменьшаться или оставаться постоянным. Это доказательство воспроизведено в ряде популярных книг по математике.
Вариации и обобщения[править | править код]
- Саймон Тэтэм и Гарет Тейлор показали[1][2], что до пятого ряда можно добраться с помощью бесконечной серии ходов.
- Если разрешены диагональные прыжки, можно достичь 8-го ряда, но не 9-го.
- В n-мерной версии игры самая высокая строка, которая может быть достигнута, — это . Доказательство Конвея влечёт, что строка не может быть достигнута. Значительно сложнее показать, что строка может быть достигнута[3].
- Похожая задача была предложена М. Л. Концевичем в 1981 году для Турнира городов. Эта задача была признана одной из лучших среди опубликованных в «Задачнике Кванта» в 1981 году, её решению была посвящена отдельная статья[4].
Примечания[править | править код]
- ↑ Simon Tatham. Reaching row 5 in Solitaire Army (web version). Дата обращения: 5 ноября 2021. Архивировано 22 октября 2021 года.
- ↑ Simon Tatham. Reaching Row Five in Solitaire Army. Дата обращения: 5 ноября 2021. Архивировано 7 ноября 2021 года.
- ↑ H. Eriksson (1995). "Twin jumping checkers in Z_d". European J. Combin. 16: 153—157.
- ↑ А. Ходулёв. Расселение фишек Архивная копия от 27 марта 2022 на Wayback Machine Квант. 1982, №7, c. 28---31.
Литература[править | править код]
- E. Berlekamp, J. Conway and R. Guy, Winning Ways for Your Mathematical Plays, 2nd ed., Vol. 4, Chap. 23: 803—841, A K Peters, Wellesley, MA, 2004.
- R. Honsberger, A problem in checker jumping, in Mathematical Gems II, Chap. 3: 23—28, MAA, 1976.
- G. Bell, D. Hirschberg and P. Guerrero, The minimum size required of a solitaire army, INTEGERS Electronic Journal of Combinatorial Number Theory, Vol 7, G7, 2007.
Ссылки[править | править код]
- cut-the-knot.org explains the game
- A page describing several variations of the game, with recent references
- Weisstein, Eric W. "Conway's Soldiers". MathWorld.
- Interactive version of the game (1)
- Interactive version of the game (2)
- Plus online magazine describes the game