Солдаты Конвея

Солдаты Конвея — математическая головоломка, предложенная Джоном Конвеем в 1961 году.

Расположение солдат Конвея для достижения рядов 1, 2, 3 и 4.Солдаты, отмеченные буквой "В", представляют собой альтернативу солдатам, отмеченным буквой "А".

Описание

Доска разделена горизонтальной линией, которая простирается до бесконечности. Над линией расположены пустые ячейки, а под линией — произвольное количество фишек. Ход состоит из того, что одна из фишек перепрыгивает через соседнюю на пустую ячейку, вертикально или горизонтально (но не по диагонали), съедая при этом фишку, через которую перепрыгнула. Цель головоломки состоит в том, чтобы разместить солдата как можно выше горизонтальной линии.

Результаты

Конвей доказал, что, независимо от используемой стратегии, не существует конечной последовательности ходов, которая позволит солдату продвинуться более чем на четыре ряда выше горизонтальной линии. В его доказательстве используется полуинвариант — сумма по всем фишкам тщательно подобранных весов на клетках. Он доказал, что общий вес может только уменьшаться или оставаться постоянным. Это доказательство воспроизведено в ряде популярных книг по математике. 

Вариации и обобщения
  • Саймон Тэтэм и Гарет Тейлор показали[1][2], что до пятого ряда можно добраться с помощью бесконечной серии ходов.
  • Если разрешены диагональные прыжки, можно достичь 8-го ряда, но не 9-го.
  • В n-мерной версии игры самая высокая строка, которая может быть достигнута, — это . Доказательство Конвея влечёт, что строка не может быть достигнута. Значительно сложнее показать, что строка может быть достигнута[3].
  • Похожая задача была предложена М. Л. Концевичем в 1981 году для Турнира городов. Эта задача была признана одной из лучших среди опубликованных в «Задачнике Кванта» в 1981 году, её решению была посвящена отдельная статья[4].

Примечания
  1. Simon Tatham. Reaching row 5 in Solitaire Army (web version).
  2. Simon Tatham. Reaching Row Five in Solitaire Army.
  3. H. Eriksson (1995). “Twin jumping checkers in Z_d”. European J. Combin. 16: 153—157.
  4. А. Ходулёв. Расселение фишек Квант. 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.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.