Солдаты Конвейса - Википедия - Conways Soldiers

Солдаты Конвея или проблема с шахматным прыжком один человек математическая игра или головоломка, придуманная и проанализированная математиком Джон Хортон Конвей в 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}} приблизительно 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 ^ {п-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 сумма _ {п = 2} ^ { infty} varphi ^ {п} = 1}$. Применение этой идентичности производит

${ Displaystyle S_ {1} = ( varphi +2) (1+ varphi +1) = ( varphi +2) ^ {2} = 5 + 3 varphi приблизительно 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., ни один солдат не может достичь клетки пятого ряда после конечного числа прыжков.

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

• Э. Берлекамп, Дж. Конвей и Р. Гай, Лучшие способы для ваших математических пьес, 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)
• Плюс онлайн-журнал описывает игру