Soldats de Conway

El problema dels soldats de Conway o el problema de les dames (en referència al jugue de taula) és un joc matemàtic per a una persona que va ser desenrollat i analisat pel matemàtic John Horton Conway en 1961. És una variant del solitari senku que es realisa en un tauler infinit. El tauler es dividix per una llínea horisontal que s'estén de forma indefinida, sobre la qual apareixen celes buides i en la part inferior una cantitat arbitrària de peces o soldats, una per casella. De la mateixa manera que en el joc de dames, els moviments consistixen que una peça brincar sobre una atra peça adjacent, ya siga vertical o horisontalment (pero no en diagonal) i "capturant-la" (eliminant-la del tauler) en el procés. L'objectiu del joc és dur a un soldat per damunt i tan llunt de la llínea horisontal com siga possible.

Apanys de soldats de Conway necessaris per a alcançar les files 1, 2, 3 i 4. Les posicions marcades en B són alternatives a les posicions marcades en A.

Conway va demostrar, que independentment de l'estratègia usada, no existix una série de moviments que permeten a un soldat alvançar més de quatre files per damunt de la llínea horisontal. L'argument de la prova involucra l'assignació de coeficients a les caselles d'una forma molt particular (i relacionada en la proporció áurea) de tal manera que la suma dels coeficients assignats a totes les fiches del tauler no puga ser incrementada per cap moviment permissible. Este argument ha segut presentat en diversos llibres de matemàtica popular.

Simon Tatham i Gareth Taylor han demostrat que és possible alcançar la quinta fila per mig d'una cantitat infinita de moviments, mateix resultat que apareix també en un artícul de Pieter Blue i Stephen Hartke.

Quan es permeten bots en diagonal, és possible dur als soldats fins a l'octava fila (pero no fins a la novena). S'ha demostrat també que, en la versió n-dimensional del joc, la màxima fila que es pot alcançar és 3n-2. L'argument de Conway demostra que la fila 3n-1 no és alcanzable encara que és considerablement més complicat demostrar que sí és possible aplegar a la fila 3n-2, com demostren en l'artícul de Eriksson i Lindstrom.

Prova de que la quinta fila és inaccessible

Notació i definicions

Podem supondre que les caselles corresponen a punts del pla cartesiano en coordenades sanceres, que els soldats estan inicialment en caselles que la seua ordenadas (coordenada i) no són positives i sense pèrdua de generalitat podem assumir que la casella objectiu està en les coordenades (0,5).

A cada punt de coordenades sanceres ocupat per un soldat li assignem el valor $x^n$ a on n és la distància d'eixe punt a la casella objectiu en la mètrica del taxi i

$x=\frac{\sqrt{5}-1}{2}$.

Considerem llavors la suma S de tots els térmens que corresponen a posicions ocupades. En el cas de que hi haguera una cantitat infinita de posicions ocupades, procedirem a usar séries en lloc de sumes.

Càlculs corresponents als moviments

La selecció de

$x=\frac{\sqrt{5}-1}{2}$,

es realisa en l'objectiu de que es complixca la relació

$x^2+x-1=0$

i per això

$x^r+x^{r-1}-x^{r-2}=0$ per a qualsevol valor sancer de r

és dir:

$x^{r-2}=x^r+x^{r-1}$ per a qualsevol valor sancer de r.

Si en realisar un bot, el soldat s'allunta de la casella objectiu, si la seua posició tenia originalment el valor

$x^r$

, el seu nou valor serà

$x^{r+2}$

pero tant la seua posició original (

$x^r$

) com la casella sobre la que va brincar (

$x^{r+1}$

) queden buides de manera que la suma total del tauler canvia per

$x^{r+2}-x^{r+1}-x^r=x^{r+2}-x^{r-2}$

i en ser $x<1$ dit canvi és negatiu per lo que la suma de tot el tauler disminuïx.

Per un atre costat, si en realisar un bot el soldat s'acosta a la casella objectiu, partint des d'una posició en valor $x^r$, el canvi de la suma total seria

$x^{r-2}-x^{r-1}-x^r=0$,

en atres paraules, la suma total del tauler permaneix sense canvi.

Demostració de l'impossibilitat

És possible demostrar, usant séries convergents, junt a la propietat $x^2=1-x$, que si totes les caselles en coordenades i negatives o zero estigueren ocupades, la suma total del tauler seria igual a 1, i per tant qualsevol configuració finita té una suma total estrictament menor que 1.

Per una atra part, mencionem dalt que qualsevol moviment fa que la suma total es mantinga igual o disminuïxca, pero mai aument.

Finalment, si despuix d'una série finita de moviments algun soldat aplegara a la casella que correspon al punt (0,5), el valor que tindria assignat seria $x^0=1$ i per tant que la suma de tot el tauler deu ser major d'1.

Lo anterior és una contradicció, ya que cap moviment pot fer que la suma total aumente i per tant mai pot excedir el seu valor inicial igual a un.

La conclusió és, llavors, que no és possible que un soldat aplegue a la casella corresponent al (5,0), és dir, un soldat mai pot alvançar cinc files cap a dalt.

Referències

• 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.
• H. Eriksson and B. Lindstrom, Twin jumping checkers in Z_d, Europ. J. Combinatorics, 16 (1995), 153–157.