Conways vojáci - Conways Soldiers - Wikipedia

Conwayovi vojáci nebo checker-jumping problém je jedna osoba matematická hra nebo hádanka, kterou vytvořil a analyzoval matematik John Horton Conway v roce 1961. Varianta peg solitaire, odehrává se na nekonečný šachovnice. Deska je rozdělena vodorovnou čarou, která se rozprostírá na neurčito. Nad řádkem jsou prázdné buňky a pod řádkem libovolný počet herních kousků neboli „vojáků“. Stejně jako v peg solitaire, tah se skládá z jednoho vojáka, který skočil přes sousedního vojáka do prázdné cely, svisle nebo vodorovně (ale ne diagonálně), a odstranil vojáka, který byl přeskočen. Cílem této hádanky je umístit vojáka co nejvíce nad vodorovnou čáru.

Uspořádání vojáků Conwaye k dosažení řad 1, 2, 3 a 4. Muži označení „B“ představují alternativu k těm označeným „A“.

Conway dokázal, že bez ohledu na použitou strategii neexistuje žádná konečná posloupnost tahů, která vojákovi umožní postoupit o více než čtyři řady nad vodorovnou čáru. Jeho argument používá pečlivě zvolené vážení buněk (zahrnující Zlatý řez ) a dokázal, že celková hmotnost může pouze klesnout nebo zůstat konstantní. Tento argument byl reprodukován v řadě populárních matematických knih.^{[Citace je zapotřebí ]}

Simon Tatham a Gareth Taylor ukázali^[1][2] že do páté řady se dostanete přes nekonečný série tahů. Pokud jsou povoleny diagonální skoky, lze dosáhnout 8. řádku, ale ne 9. řádku.^{[Citace je zapotřebí ]} Bylo to také ukázáno^{[Citace je zapotřebí ]} že v n-dimenzionální verze hry, nejvyšší řádek, kterého lze dosáhnout, je ${ displaystyle 3n-2}$. Conwayův váhový argument ukazuje^{[Citace je zapotřebí ]} že řádek ${ displaystyle 3n-1}$ nemůže být dosaženo. Je podstatně těžší ten řádek ukázat ${ displaystyle 3n-2}$ umět být dosažen.^[3]

Conwayův důkaz, že pátá řada je nepřístupná

Zápis a definice

Definovat ${ displaystyle varphi = { frac {{ sqrt {5}} - 1} {2}} přibližně 0,61803 , 39887 ldots}$. (Jinými slovy, ${ displaystyle varphi}$ zde označuje reciproční z Zlatý řez.) Dodržujte to ${ displaystyle varphi ^ {2} = 1- varphi}$.

Nechte cílový čtverec označit hodnotou ${ displaystyle varphi ^ {0} = 1}$a všechny ostatní čtverce budou označeny hodnotou ${ displaystyle varphi ^ {n}}$, kde ${ displaystyle n}$ je Vzdálenost na Manhattanu na cílové pole. Poté můžeme spočítat „skóre“ konfigurace vojáků sečtením hodnot čtverců vojáků. Například konfigurace pouze dvou vojáků umístěných tak, aby se při příštím skoku dostali na cílové pole, by měla skóre ${ displaystyle varphi ^ {1} + varphi ^ {2}}$.

Když voják přeskočí jiného vojáka, je třeba zvážit tři případy:

1. Když voják skočí vůči cílové pole: Nechť je hodnota pole vojáka ${ displaystyle varphi ^ {n}}$ pro některé ${ displaystyle n}$a hodnota čtverce, na který přeskočí, bude ${ displaystyle varphi ^ {n-1}}$; pak je celková změna skóre po skoku ${ displaystyle varphi ^ {n-2} - varphi ^ {n-1} - varphi ^ {n} = varphi ^ {n-2} (1- varphi - varphi ^ {2}) = 0}$.
2. Když voják zůstane stejný vzdálenost od cílového pole po jeho skoku: V tomto případě je změna skóre ${ displaystyle varphi ^ {n} - varphi ^ {n-1} - varphi ^ {n} = - varphi ^ {n-1}}$.
3. Když voják skočí pryč od cílového pole: Zde je změna skóre ${ displaystyle varphi ^ {n + 2} - varphi ^ {n + 1} - varphi ^ {n} = varphi ^ {n} ( varphi ^ {2} - varphi -1) = - 2 varphi ^ {n + 1}}$.

Žádný skok tedy nikdy nezvýší celkové skóre konfigurace.

Výpočet skóre počáteční konfigurace

Zvažte nyní počáteční konfiguraci, kde je pouze jedna nekonečná vodorovná čára zcela vyplněna vojáky.

Pokud je tato vodorovná linie vojáků bezprostředně pod cílovým čtvercem, pak je skóre konfigurace ${ displaystyle varphi +2 varphi ^ {2} +2 varphi ^ {3} + ldots}$. Skóre čáry dva mezery pod cílovým čtvercem jsou ${ displaystyle varphi ^ {2} +2 varphi ^ {3} +2 varphi ^ {4} + ldots = varphi ( varphi +2 varphi ^ {2} +2 varphi ^ {3} + ldots)}$. Skóre čáry tři mezery níže jsou ${ displaystyle varphi ^ {2} ( varphi +2 varphi ^ {2} +2 varphi ^ {3} + ldots)}$. A tak dále.

Zvažte úplnou výchozí konfiguraci, kde vojáci zaplní celou polorovinu pod červenou čarou. Skóre této konfigurace je součtem skóre jednotlivých řádků. Pokud je tedy cílový čtverec bezprostředně nad červenou čárou, skóre je

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

V tomto okamžiku sledujte další zajímavou vlastnost ${ displaystyle varphi}$a sice to ${ displaystyle sum _ {n = 2} ^ { infty} varphi ^ {n} = 1}$. Použitím této identity se vytvoří

${ displaystyle S_ {1} = ( varphi +2) (1+ varphi +1) = ( varphi +2) ^ {2} = 5 + 3 varphi přibližně 6,85410 ldots}$.

Pokud je cílový čtverec ve druhé řadě nad červenou čárou, je každý voják o jedno políčko dále od cílového čtverce, takže skóre je

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

Podobně:

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

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

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

Když voják dosáhne cílového pole po určitém konečném počtu tahů, má konečná konfigurace skóre ${ displaystyle E = varphi ^ {0} + epsilon}$, kde ${ displaystyle varphi ^ {0}}$ představuje příspěvek vojáka na cílovém poli a ${ displaystyle epsilon}$ představuje (malý, ale pozitivní) příspěvek nekonečného počtu vojáků, kteří zůstávají jinde v letadle.

Ukázali jsme tedy, že když je cílový čtverec v páté řadě nad nekonečnou polorovinou vojáků, skóre výchozí konfigurace je přesně ${ displaystyle S_ {5} = 1}$; skóre konečné konfigurace je ${ displaystyle E = 1 + epsilon}$; a protože žádný druh skoku nikdy nezvýší skóre, musíme mít ${ displaystyle S_ {5} geq E}$. To je rozpor; Q.E.D., je nemožné, aby jakýkoli voják dosáhl čtverce v páté řadě po konečném počtu skoků.

Reference

• E. Berlekamp, ​​J. Conway a R. Guy, Winning Ways for Your Mathematical Plays, 2. vydání, sv. 4, kap. 23: 803—841, A K Peters, Wellesley, MA, 2004.
• R. Honsberger, Problém skákání dáma, v Mathematical Gems II, kap. 3: 23—28, MAA, 1976.
• G. Bell, D. Hirschberg a P. Guerrero, minimální velikost požadovaná pro solitairskou armádu, INTEGERS Elektronický deník kombinatorické teorie čísel, Sv. 7, G7, 2007.

externí odkazy

• cut-the-knot.org vysvětluje hru
• Stránka popisující několik variant hry s nedávnými odkazy
• Weisstein, Eric W. "Conwayovi vojáci". MathWorld.
• Interaktivní verze hry (1)
• Interaktivní verze hry (2)
• Plus online magazín popisuje hru