Joc de Wythoff

Archiu:Westbury sub Mendip A066096T462.189 silver denarii cleaned for ID, January 2017. Two piles as hoard divided by find days. (FindID 810901).jpg

El joc de Wythoff es juga en dos piles de contadors

El joc de Wythoff és un joc de resta matemàtica per a dos jugadors, que es juga en dos piles de fiches. Els jugadors es turnan per a llevar les fiches d'una o abdós piles; en retirar fiches d'abdós piles, el número de fiches que es retiren de cada pila deu ser igual. El joc termina quan una persona lleva l'últim contador o contadors, guanyant aixina.

Una descripció equivalent del joc és que una sola dama d'escacs es coloca en algun lloc d'una gran cuadrícula de quadrats, i cada jugador pot moure la dama cap al cantó inferior esquerra de la cuadrícula: sur, oest o suroest, qualsevol número de passos. El guanyador és el jugador que mou a la dama al cantó.

Martin Gardner en el seu "columna de Jocs Matemàtics" de març de 1977 en Scientific American afirma que el joc es jugava en China baix el nom de 捡石子 jiǎn shízǐ ("arreplegar pedres"). El matemàtic neerlandés W. A. Wythoff va publicar un anàlisis matemàtic del joc en 1907.

Estratègia òptima

Archiu:Wythoff's Nim.svg

Una visualisació del joc de Wythoff de Nim. El quadrat inferior a l'esquerra és la posició (1,1) i els quadrats rojos són posicions fredes. Tinga's en conte que el quadro guanyador no està inclós en l'image.

Qualsevol posició en el joc pot descriure's per mig d'un parell de número entero (n , m) en n ≤ m, que descriuen el tamany d'abdós piles en la posició o les coordenades de la reina. L'estratègia del joc gira entorn a posicions fredes i posicions calents: en una posició freda, el jugador al que li toca moure perdrà en el millor joc, mentres que en una posició calenta, el jugador al que li toca moure's guanyarà en el millor jugar. L'estratègia òptima des d'una posició calenta és passar a qualsevol posició freda accessible.

La classificació de posicions en calenta i freda es pot realisar de forma recursiva en les següents tres regles:

1. (0,0) és una posició freda.
2. Qualsevol posició des de la que es puga alcançar una posició freda en un sol moviment és una posició calenta.
3. Si cada moviment conduïx a una posició calenta, llavors una posició és freda.

Per eixemple, totes les posicions de la forma (0, m ) i ( m , m ) en m  > 0 són calents, segons la regla 2. No obstant, la posició (1,2) és freda, perque les úniques posicions que es poden alcançar d'ell, (0,1), (0,2), (1,0) i (1,1), estan tots calentes. Les posicions fredes ( n , m ) en els valors més menuts de n i m són (0, 0), (1, 2), (3, 5), (4, 7), (6, 10) i (8, 13). (seqüència A066096 i A090909 en OEIS) (Vore també OEIS:  A072061)

Per a la versió misère d'este joc (aquell en el qual guanya qui d'acort en les regles, pert), (0, 1) i (2, 2) són posicions fredes, i una posició ( n , m ) en m ,  n  > 2 és frigga si i solament si ( n , m ) en joc normal esta fret.

Fòrmula per a posicions fredes

Wythoff va descobrir que les posicions fredes seguixen un patró regular determinat per la proporció áurea. Específicament, si k és qualsevol número natural i

$n_k=\lfloor k\varphi \rfloor =\lfloor m_k\varphi \rfloor -m_k$

$m_k=\lfloor k{\varphi }^2\rfloor =\lceil n_k\varphi \rceil =n_k+k$

a on φ és la proporció áurea i estem usant la funció chafe, llavors (n_k, m_k) és la k- ^ésima posició freda. Estes dos seqüències de números es registren en l'Enciclopèdia en llínea de seqüències d'número entero com OEIS Plantilla:OEIS2C i Plantilla:OEIS2C, respectivament.

Les dos seqüències n_k i m_k són les seqüències de Beatty associades en l'equació

$\frac{1}{\varphi }+\frac{1}{{\varphi }^2}=1.$

Com ocorre en general en els parells de seqüències de Beatty, estes dos seqüències són complementàries: cada número entero positiu apareix exactament una volta en cada seqüència.

Vore també

• Nim

• Joc de Grundy
• Matriu Wythoff