Wythoff's Game

[axpgn]

Un altro giochino sulla falsariga di questo.

Vi sono due gruppi di oggetti e due giocatori che muovono a turno.
Le mosse possibili sono due:
- il giocatore può rimuovere quanti oggetti vuole (anche tutti) da uno dei due gruppi.
- il giocatore può rimuovere quanto oggetti vuole (anche tutti) da entrambi i gruppi purché il numero degli oggetti rimossi da ciascun gruppo sia lo stesso.
Vince chi rimuove l'ultimo oggetto.
Qual è la strategia vincente (ammesso che esista) ?

Cordialmente, Alex

[orsoulx]

conosco il gioco ed esistono, naturalmente, strategie vincenti; a patto di trovarsi nelle situazioni opportune.
Ciao
B.

[nino_12]

Se i due gruppi sono composti dallo stesso numero di oggetti, ovviamente vince colui cui spetta muovere.
Negli altri casi, occorre, se possibile, occupare le posizioni che sono vincenti.

Ho trovato che sono sicure:
1 , 2
3 , 5
4 , 7

Proseguendo, ho fatto un tentativo con 7 , 12 , ma mi sono accorto che è perdente.
Allora, ho guardato l'enciclopedia delle sequenze dei numeri interi:
http://oeis.org/?language=italian

e ho scoperto che esiste la lower Wythoff sequence
1 , 3 , 4 , 6 , 8 , 9 , 11 , ...
(A000201)

e la upper Wythoff sequence
2 , 5 , 7 , 10 , 13 , 15 , 18 , ...
(A001950)

Ciao, Nino

[axpgn]

Come avete detto, esistono delle posizioni chiave, quelle che io chiamo "perdenti" perché sono quelle da lasciare all'avversario e si possono elencare in una sequenza cosiffatta $(1,2),(3,5),(4,7),(6,10),(8,13),...$.

Si possono notare alcune cose:

- la differenza tra i numeri della prima coppia è pari a $1$, la differenza tra quelli della seconda è $2$, tra quelli della terza è $3$ e così via ...
- tutti i numeri naturali sono rappresentati una e una sola volta.
- l'ennesima coppia è $(\lfloor alphan \rfloor;\lfloor alpha^2n \rfloor)$, dove $alpha=(1+sqrt(5))/2$.

Cordialmente, Alex

[orsoulx]

Questo gioco forse meritava una fine migliore. Diverse domande interessanti non sono nemmeno state formulate. Ad esempio:
(a) qual è la strategia da adottare nella versione misère, in cui chi esaurisce gli oggetti perde?
(b) esiste un algoritmo efficace per individuare la casella da raggiungere, senza scorrere di volta in volta, la sequenza delle posizioni 'vincenti'?
Ciao
B.

[axpgn]

Per il punto b) non ho un formula però una procedura che funziona sì ...
Data la coppia di numeri $(a,b)$ si prende il minore (supponiamo $a$) e lo si divide per $alpha$ e utilizzando i due interi in cui è compreso il risultato si verifica se $a$ fa parte di una coppia chiave; se sì si somma ad $a$ l'intero da cui "dipende" per verificare se anche $b$ completa la coppia "perdente" e in caso affermativo ... ahia ...; se invece $b$ è "buono", nel caso sia maggiore lo si riduce a questo, se è minore si prende $a-b$ come intero di riferimento e si calcola la coppia a cui arrivare; e quest'ultima è anche la procedura da utilizzare nel caso in cui $a$ sia "buono".

Cordialmente, Alex

[orsoulx]

@Alex
un po' confuso (per me, ovviamente), ma sostanzialmente: sì.
Ciao
B.

[axpgn]

Scritto di corsa, sorry ...

[axpgn]

Per il punto a) la sequenza di coppie chiave ("perdenti") parte dalle due di base ($(0,1)$ e $(2,2)$ e poi si ricomincia come prima $(3,5);(4,7);(6,10),...$.
Cercherò di dimostrarlo ...

Io chiamo "perdenti" le coppie dalle quali NON si può passare ad un'altra coppia perdente.
Le prime due sono $(0,1)$ e $(2,2)$ (si verifica direttamente).
Per le regole del gioco, date due coppie che hanno un numero in comune è sempre possibile passare da quella con il secondo numero maggiore a quella con il secondo numero minore; sempre per definizione, date due coppie che hanno la stessa differenza tra i numeri della coppia è sempre possibile passare da quella con in numeri più "alti" a quella con i numeri più bassi.
Da ciò, ne consegue che un dato numero $n$ può "stare" solo in una coppia perdente, mai in due, così come per ogni differenza tra i componenti la coppia esiste una sola coppia perdente con quella differenza.

Le coppie perdenti si costruiscono in questo modo ...
Chiamiamo $(a_n,b_n)$ la nostra coppia e $(a_i,b_i)$ le coppie perdenti precedenti, mentre poniamo $d_n=b_n-a_n$ e $d_i=b_i-a_i$.
Per $a_n$ si prende il numero minimo tra quelli "liberi" (cioè non appartenenti a nessuna delle coppie perdenti già costruite, da cui $a_n>a_i$) e per $d_n$ la prima differenza "libera" (da cui $d_n>d_i$), la loro somma mi dà il secondo membro della coppia $b_n$; tale numero è "libero" perché $b_n>a_n>a_i$ e $b_n=a_n+d_n>a_i+d_i=b_i$.
La coppia così costruita è perdente:
- se diminuisco $a_n$, il risultato sarà un $a_i$ (o $b_i$) e perciò la nuova coppia non può essere perdente perchè ne esiste già una con quel $a_i$ (o $b_i$)
- se diminuisco $b_n$, o il risultato è un $a_i$ (o $b_i$) e vale il discorso precedente oppure no ma allora la differenza sarà una $d_i$, ma ne abbiamo già una e quindi la nuova coppia non sarà perdente.
- se li diminusico entrambi (della stessa quantità) ricado nei casi precedenti.

Mi pare ci sia tutto ...

Cordialmente, Alex

[orsoulx]

Esiste una rappresentazione 'grafica' del gioco che permette di costruire facilmente le posizioni obiettivo, tanto nel gioco normale, quanto in quello misère. In una scacchiera a forma di quadrante, si deve muovere, a turno, una regina (capace delle normali mosse della medesima), con l'unica condizione che deve avvicinarsi al vertice del quadrante, che è il punto di arrivo. Ti risparmio le complicazioni che si potrebbero ottenere pensando di giocare con più di una regina.
Ciao
B.