Русская Википедия:Солдаты Конвея
Солдаты Конвея — математическая головоломка, предложенная Джоном Конвеем в 1961 году.
Описание
Доска разделена горизонтальной линией, которая простирается до бесконечности. Над линией расположены пустые ячейки, а под линией — произвольное количество фишек. Ход состоит из того, что одна из фишек перепрыгивает через соседнюю на пустую ячейку, вертикально или горизонтально (но не по диагонали), съедая при этом фишку, через которую перепрыгнула. Цель головоломки состоит в том, чтобы разместить солдата как можно выше горизонтальной линии.
Результаты
Конвей доказал, что, независимо от используемой стратегии, не существует конечной последовательности ходов, которая позволит солдату продвинуться более чем на четыре ряда выше горизонтальной линии. В его доказательстве используется полуинвариант — сумма по всем фишкам тщательно подобранных весов на клетках. Он доказал, что общий вес может только уменьшаться или оставаться постоянным. Это доказательство воспроизведено в ряде популярных книг по математике.
Вариации и обобщения
- Саймон Тэтэм и Гарет Тейлор показали[1][2], что до пятого ряда можно добраться с помощью бесконечной серии ходов.
- Если разрешены диагональные прыжки, можно достичь 8-го ряда, но не 9-го.
- В n-мерной версии игры самая высокая строка, которая может быть достигнута, — это <math>3n-2</math>. Доказательство Конвея влечёт, что строка <math>3n-1</math> не может быть достигнута. Значительно сложнее показать, что строка <math>3n-2</math> может быть достигнута[3].
- Похожая задача была предложена М. Л. Концевичем в 1981 году для Турнира городов. Эта задача была признана одной из лучших среди опубликованных в «Задачнике Кванта» в 1981 году, её решению была посвящена отдельная статья[4].
Примечания
Литература
- 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
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite journal
- ↑ А. Ходулёв. Расселение фишек Шаблон:Wayback Квант. 1982, №7, c. 28---31.
