Солдаты Конвея - Conways Soldiers - Wikipedia

Солдаты Конвея или проблема с шахматным прыжком один человек математическая игра или головоломка, придуманная и проанализированная математиком Джон Хортон Конвей в 1961 г. Вариант колышек пасьянс, это происходит на бесконечный шахматная доска. Доска разделена горизонтальной линией, которая продолжается до бесконечности. Выше линии - пустые клетки, а ниже - произвольное количество игровых фишек или «солдатиков». Как и в пасьянсе с колышками, ход состоит из одного солдата, перепрыгивающего через соседнего солдата в пустую клетку, вертикально или горизонтально (но не по диагонали), и удаления солдата, через который перепрыгнул. Цель головоломки - разместить солдата как можно выше над горизонтальной линией.

Расстановка солдат Конвея, чтобы добраться до рядов 1, 2, 3 и 4. Люди, отмеченные буквой «B», представляют собой альтернативу тем, кто отмечен буквой «A».

Конвей доказал, что, независимо от используемой стратегии, не существует конечной последовательности движений, которая позволила бы солдату продвинуться более чем на четыре ряда выше горизонтальной линии. Его аргумент использует тщательно подобранное взвешивание ячеек (включая Золотое сечение ), и он доказал, что общий вес может только уменьшаться или оставаться постоянным. Этот аргумент был воспроизведен в ряде популярных математических книг.^{[нужна цитата ]}

Саймон Татхам и Гарет Тейлор показали^[1][2] что к пятой строке можно попасть через бесконечный серия ходов. Если разрешены диагональные прыжки, можно добраться до 8-го ряда, но не до 9-го.^{[нужна цитата ]} Также было показано^{[нужна цитата ]} что в п-размерный версии игры, самый высокий ряд, который может быть достигнут, ${\displaystyle 3n-2}$. Весовой аргумент Конвея демонстрирует^{[нужна цитата ]} что строка ${\displaystyle 3n-1}$ недоступен. Показать эту строку значительно сложнее ${\displaystyle 3n-2}$ может быть достигнут.^[3]

Доказательство Конвея, что пятая строка недоступна

Обозначения и определения

Определять ${\displaystyle \varphi ={\frac {{\sqrt {5}}-1}{2}}\approx 0.61803\,39887\ldots }$. (Другими словами, ${\displaystyle \varphi }$ здесь обозначает взаимный из Золотое сечение.) Обратите внимание, что ${\displaystyle \varphi ^{2}=1-\varphi }$.

Пусть целевой квадрат будет помечен значением ${\displaystyle \varphi ^{0}=1}$, а все остальные квадраты должны быть помечены значением ${\displaystyle \varphi ^{n}}$, куда ${\displaystyle n}$ это Манхэттенское расстояние к целевой площади. Затем мы можем вычислить «балл» конфигурации солдат, суммируя значения квадратов солдат. Например, конфигурация из двух солдат, размещенных так, чтобы достигнуть целевого квадрата при следующем прыжке, будет иметь счет ${\displaystyle \varphi ^{1}+\varphi ^{2}}$.

Когда солдат перепрыгивает через другого солдата, следует рассмотреть три случая:

1. Когда солдат прыгает к целевой квадрат: Пусть значение квадрата солдата будет ${\displaystyle \varphi ^{n}}$ для некоторых ${\displaystyle n}$, а значение квадрата, через которое он перепрыгивает, будет ${\displaystyle \varphi ^{n-1}}$; тогда общее изменение очков после прыжка равно ${\displaystyle \varphi ^{n-2}-\varphi ^{n-1}-\varphi ^{n}=\varphi ^{n-2}(1-\varphi -\varphi ^{2})=0}$.
2. Когда солдат остается одно и тоже расстояние от мишени после его прыжка: в этом случае изменение счета ${\displaystyle \varphi ^{n}-\varphi ^{n-1}-\varphi ^{n}=-\varphi ^{n-1}}$.
3. Когда солдат прыгает прочь от целевого квадрата: Здесь изменение счета ${\displaystyle \varphi ^{n+2}-\varphi ^{n+1}-\varphi ^{n}=\varphi ^{n}(\varphi ^{2}-\varphi -1)=-2\varphi ^{n+1}}$.

Таким образом, ни один прыжок никогда не увеличит общую оценку конфигурации.

Вычисление оценки начальной конфигурации

Теперь рассмотрим начальную конфигурацию, в которой только одна бесконечная горизонтальная линия полностью заполнена солдатами.

Если эта горизонтальная линия солдат находится непосредственно под целевым квадратом, то оценка конфигурации равна ${\displaystyle \varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots }$. Оценка линии два пробелов под целевым квадратом ${\displaystyle \varphi ^{2}+2\varphi ^{3}+2\varphi ^{4}+\ldots =\varphi (\varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots )}$. Оценка линии три пробелы ниже ${\displaystyle \varphi ^{2}(\varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots )}$. И так далее.

Рассмотрим полную стартовую конфигурацию, в которой солдаты заполняют всю полуплоскость ниже красной линии. Оценка этой конфигурации - это сумма оценок отдельных линий. Следовательно, если целевой квадрат находится непосредственно над красной линией, счет

${\displaystyle S_{1}=(\varphi +2(\varphi ^{2}+\varphi ^{3}+\varphi ^{4}\ldots ))(1+\varphi +\varphi ^{2}+\varphi ^{3}+\ldots )}$.

На этом этапе обратите внимание на еще одно интересное свойство ${\displaystyle \varphi }$, а именно, что ${\displaystyle \sum _{n=2}^{\infty }\varphi ^{n}=1}$. Применение этой идентичности производит

${\displaystyle S_{1}=(\varphi +2)(1+\varphi +1)=(\varphi +2)^{2}=5+3\varphi \approx 6.85410\ldots }$.

Если целевой квадрат находится во втором ряду над красной линией, каждый солдат находится на одну клетку дальше от целевого квадрата, и поэтому счет

${\displaystyle S_{2}=\varphi S_{1}=2+2\varphi }$.

По аналогии:

${\displaystyle S_{3}=\varphi S_{2}=2+\varphi }$,

${\displaystyle S_{4}=\varphi S_{3}=1+\varphi }$,

${\displaystyle S_{5}=\varphi S_{4}=1}$.

Когда солдат достигает целевой клетки после некоторого конечного числа ходов, конечная конфигурация имеет счет ${\displaystyle E=\varphi ^{0}+\epsilon }$, куда ${\displaystyle \varphi ^{0}}$ представляет вклад солдата в целевую клетку и ${\displaystyle \epsilon }$ представляет собой (небольшой, но положительный) вклад бесконечного количества солдат, которые остаются в других местах на плане.

Таким образом, мы показали, что, когда целевой квадрат находится в пятом ряду над бесконечной полуплоскостью солдат, счет стартовой конфигурации в точности равен ${\displaystyle S_{5}=1}$; оценка конечной конфигурации ${\displaystyle E=1+\epsilon }$; и поскольку ни один прыжок не увеличивает счет, мы должны иметь ${\displaystyle S_{5}\geq E}$. Это противоречие; Q.E.D., ни один солдат не может достичь клетки пятого ряда после конечного числа прыжков.

Рекомендации

1. Саймон Тэтхам. «Достижение 5-го ряда в Solitaire Army (веб-версия)».
2. Саймон Татхам; Гарет Тейлор. «Достижение пятой строки в пасьянсах» (PDF).
3. Х. Эрикссон; Б. Линдстрем (1995). «Двойные шашки для прыжков в Зідь». Европейский J. Combin. 16: 153–157.

• Э. Берлекамп, Дж. Конвей и Р. Гай, Лучшие способы для ваших математических пьес, 2-е изд., Т. 4, гл. 23: 803-841, А. К. Питерс, Уэллсли, Массачусетс, 2004.
• Р. Хонсбергер, Проблема в прыжках в шахматы, в Mathematical Gems II, гл. 3: 23–28, MAA, 1976.
• Г. Белл, Д. Хиршберг и П. Герреро, Минимальный размер, требуемый для пасьянсовой армии, INTEGERS Электронный журнал комбинаторной теории чисел, Том 7, G7, 2007.

внешняя ссылка

• cut-the-knot.org объясняет игру
• Страница с описанием нескольких вариантов игры с недавними ссылками.
• Вайсштейн, Эрик В. "Солдаты Конвея". MathWorld.
• Интерактивная версия игры (1)
• Интерактивная версия игры (2)
• Плюс онлайн-журнал описывает игру