Conways soldater

Arrangemang av Conways soldater för att nå raderna 1, 2, 3 och 4. Soldaterna markerade "B" representerar ett alternativ till de markerade "A".

Conway's Soldiers eller schackhoppningsproblemet är ett matematiskt spel eller pussel för en person som skapades och analyserades av matematikern John Horton Conway 1961. En variant av pegpatiens, det utspelar sig på ett oändligt schackbräde. Brädan delas av en horisontell linje som sträcker sig i det oändliga. Ovanför linjen finns tomma celler och under linjen finns ett godtyckligt antal spelpjäser, eller "soldater". Som i peg-patiens består ett drag av att en soldat hoppar över en intilliggande soldat in i en tom cell, vertikalt eller horisontellt (men inte diagonalt), och tar bort soldaten som hoppades över. Målet med pusslet är att placera en soldat så långt över den horisontella linjen som möjligt.

Conway bevisade att, oavsett vilken strategi som används, finns det ingen ändlig sekvens av rörelser som gör att en soldat kan avancera mer än fyra rader över den horisontella linjen. Hans argument använder en noggrant vald viktning av celler (som involverar det gyllene snittet ), och han bevisade att den totala vikten bara kan minska eller förbli konstant. Detta argument har återgivits i ett antal populära matematikböcker.

Simon Tatham och Gareth Taylor har visat att den femte raden kan nås via en oändlig serie drag. Om diagonala hopp tillåts kan 8:e raden nås, men inte 9:e raden. Det har också visat sig att i den n - dimensionella versionen av spelet är den högsta raden som kan nås $3n-2$ . Conways viktningsargument visar att raden $3n-1$ inte kan nås. Det är betydligt svårare att visa att rad $3n-2$ kan nås.

Conways bevis på att den femte raden är otillgänglig

Notation och definitioner

Definiera $\varphi ={\frac {{\sqrt {5}}-1}{2}}\approx 0,61803\,39887\ldots$ . (Med andra ord, $\varphi$ betecknar här den reciproka av det gyllene snittet .) Observera att $\varphi ^{2}=1-\varphi$ .

Låt målkvadraten märkas med värdet $\varphi ^{0}=1$ , och alla andra rutor märkas med värdet $\varphi ^{n}$ , där ${ \displaystyle n}$ är Manhattans avstånd till målrutan. Sedan kan vi beräkna "poängen" för en konfiguration av soldater genom att summera värdena för soldaternas rutor. Till exempel, en konfiguration av endast två soldater placerade för att nå målrutan vid nästa hopp skulle ha poängen $\varphi ^{1}+\varphi ^{2}$ .

När en soldat hoppar över en annan soldat finns det tre fall att ta hänsyn till:

1. När en soldat hoppar mot målrutan: Låt värdet på soldatens kvadrat vara $\varphi ^{n}$ för några $n$ , och värdet på kvadraten han hoppar över vara $\varphi ^{n-1}$ ; då är den totala poängförändringen efter hoppet $\varphi ^{n-2}-\varphi ^{n-1}-\varphi ^{n}=\varphi ^{n-2}(1-\varphi -\varphi ^{2})=0$ .
2. När en soldat förblir på samma avstånd från målrutan efter sitt hopp: I detta fall är förändringen i poäng $\varphi ^{n}-\ varphi ^{n-1}-\varphi ^{n}=-\varphi ^{n-1}$ .
3. När en soldat hoppar bort från målrutan: Här är poängförändringen $\ varphi ^{n+2}-\varphi ^{n+1}-\varphi ^{n}=\varphi ^{n}(\varphi ^{2}-\varphi -1)=-2\varphi ^{ n+1}$ .

Så inget hopp kommer någonsin att öka konfigurationens totala poäng.

Beräknar poängen för den initiala konfigurationen

Överväg nu en startkonfiguration där bara en oändlig horisontell linje är helt fylld med soldater.

Om denna horisontella linje av soldater är omedelbart under målrutan, är poängen för konfigurationen $\varphi +2\varphi ^{2}+2\varphi ^{ 3}+\ldots$ . Poängen för en linje två mellanslag under målkvadraten är $\varphi ^{2}+2 \varphi ^{3}+2\varphi ^{4}+\ldots =\varphi (\varphi +2\varphi ^{2}+2\varphi ^{3}+\ldots )$ . Poängen för en linje tre mellanslag nedan är $\varphi ^{2}(\varphi +2\varphi ^{2}+2\varphi ^{ 3}+\ldots )$ . Och så vidare.

Tänk på den fullständiga startkonfigurationen, där soldater fyller hela halvplanet under den röda linjen. Denna konfigurations poäng är summan av poängen för de individuella raderna. Därför, om målrutan är omedelbart ovanför den röda linjen, är poängen

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

Vid denna punkt, observera en annan intressant egenskap hos $\varphi$ , nämligen att $\sum _{n=2}^{\infty }\varphi ^{n} =1$ . Att tillämpa denna identitet producerar

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

Om målrutan är i andra raden ovanför den röda linjen, är varje soldat ett utrymme längre från målrutan, och så är poängen

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

Liknande:

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

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

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

När en soldat når målrutan efter ett ändligt antal drag, har slutkonfigurationen poängen $E=\varphi ^{0}+\epsilon$ , där $\varphi ^{0 }$ representerar bidraget från soldaten på målrutan och $\epsilon$ representerar (små, men positiva) bidragen från det oändliga antalet soldater som finns kvar någon annanstans på planet.

Sålunda har vi visat att när målrutan är i den femte raden ovanför det oändliga halvplanet av soldater, är startkonfigurationens poäng exakt $S_{5}=1$ ; slutkonfigurationens poäng är $E=1+\epsilon$ ; och eftersom ingen form av hopp någonsin ökar poängen, måste vi ha $S_{5}\geq E$ . Detta är en motsägelse; QED , det är omöjligt för någon soldat att nå en ruta på den femte raden efter ett begränsat antal hopp.

• E. Berlekamp, ​​J. Conway och R. Guy, Winning Ways for Your Mathematical Plays, 2nd ed., Vol. 4, kap. 23: 803—841, AK Peters, Wellesley, MA, 2004.
• R. Honsberger, Ett problem vid schackhoppning, i Mathematical Gems II, kap. 3: 23—28, MAA, 1976.
• G. Bell, D. Hirschberg och P. Guerrero, Den minsta storleken som krävs för en patiensarmé, INTEGERS Electronic Journal of Combinatorial Number Theory, Vol 7, G7, 2007.

externa länkar

• cut-the-knot.org förklarar spelet
• En sida som beskriver flera varianter av spelet, med senaste referenser
• Weisstein, Eric W. "Conways soldater" . MathWorld .
• Interaktiv version av spelet (1)
• Interaktiv version av spelet (2)
• Plus onlinetidningen beskriver spelet