Newsgroup: it.hobby.enigmi
Titolo: La tastiera del telefono

Questo è un problema che ho trovato su Internet e che mi sono
divertito ad analizzare qualche anno fa'; sembra che sia stato
presentato in una Olimpiade della Matematica del Costarica.
Spero che non Vi sia già noto. 
 
._ _ _._ _ _._ _ _.
|     |     |     |
|  1  |  2  |  3  |
|_ _ _|_ _ _|_ _ _|
|     |     |     |
|  4  |  5  |  6  |
|_ _ _|_ _ _|_ _ _|
|     |     |     |
|  7  |  8  |  9  |
|_ _ _|_ _ _|_ _ _|
 
 
Nella tavola soprastante sono disposti i numeri da 1 a 9 proprio come
la tastiera di un telefono.
 
I due giocatori, A e B, concordano un intero positivo S, detto Somma
del Gioco.
 
Si pensi ai riquadri della tabella come ai tasti di un calcolatore. Un
giocatore sceglie un numero e preme il tasto relativo. Esiste anche un
display ove appare il Totale.
 
All'inizio il Totale è posto uguale a 0. Ad ogni passo si aggiorna il
Totale sommando il valore che è stato scelto. Perde il giocatore che
per muovere è costretto a superare S.(*)
 
Il primo a giocare sceglie la cifra che vuole. Nei passi successivi si
può scegliere soltanto un numero che stia nella stessa colonna o nella
stessa riga dell'intero y che è stato precedentemente giocato, tranne
y stesso.
 
Per esempio se al passo t un giocatore ha scelto 3, al passo t+1 chi è
di turno può giocare soltanto 1, 2, 6, 9.
 
Facciamo un esempio di gioco.
 
I giocatori A, B concordano S = 14. A gioca per primo e preme 9.
Totale = 9.
 
B può scegliere tra 3, 6, 7, 8. Però 6, 7, 8 lo fanno perdere subito.
Deve premere 3. Totale = 12.
 
A può scegliere tra 1, 2, 6, 9. A preme 1. Totale = 13
 
B può scegliere 2, 3, 4, 7. Tutte le scelte sono perdenti. A vince. 
 
Dunque se S = 14, il primo giocatore ha una strategia vincente.
 
 
Prima serie di domande:
 
Nel caso S = 14, A è sicuro di vincere se preme un tasto diverso da 9?
 
E' vero che se S = 29, chi gioca per primo può sempre vincere?
 
Il primo giocatore ha una strategia vincente per ogni valore di S?
 
 
(*) Nelle mie analisi ho preferito lavorare al contrario: fissato il
totale S tolgo ogni volta il valore scelto e perde chi va sotto lo
zero. 
-- 
Buon divertimento, Dano


Intanto, in attesa di una analsisi più approfondita, posto un semplice
programma in C# che uso in casi come questo.
Il pattern è davvero elementare: un giocatore vince se trova almeno
una mossa perdente per l'avversario, perde se TUTTE le mosse possibili
sono vincenti per l'avversario.
 
        static int[,] grafo = { { }, { 2, 3, 4, 7 }, { 1, 3, 5, 8 },
{ 1, 2, 6, 9 }, { 1, 4, 5, 7 }, { 2, 4, 6, 8 }, { 3, 4, 5, 9 }, { 1,
4, 8, 9, }, { 2, 5, 7, 9 }, { 3, 6, 7, 8 } };
        public static bool Perde(string giocatore, string avversario,
int limite, int cursore)
        {
            bool perde = true;
            if (limite < 0)
                perde = false;
            else
                for (int i = 0; i < 4; i++)
                    perde = perde && Vince(avversario, giocatore,
limite - grafo[cursore, i], grafo[cursore, i]);
            return perde;
        }
 
        public static bool Vince(string giocatore, string avversario,
int limite, int cursore)
        {
            bool vince = false;
            if (limite < 0)
                vince = true;
            else
                for (int i = 0; i < 4; i++)
                    vince = vince || Perde(avversario, giocatore,
limite - grafo[cursore, i], grafo[cursore, i]);
            return vince;
        }
 
Basta chiamarlo con Vince("pippo", "pluto", 10, 1) per sapere se Pippo
vince partendo da 1 con limite 10
 
--
Ciao, Silv:o)

 programma in C# che uso in casi come questo.
 
Non ho provato ad implementare il tuo programma, perché ne ho invece
fatto uno "darwiniano" (stimolato dai vostri recenti post, che mi hanno
risvegliato vecchissimi ricordi). Provando con una Somma che va da 1 a
200, mi viene che A perde solo se S= 27, 43 o 64.
 
Vi torna oppure ho sbagliato tutto?
 
M.
 
-- 
Per rispondermi via e-mail togli l'ovvio.

Vi torna oppure ho sbagliato tutto?
 
OK, č giusto e risponde alla terza domanda.
 
Hai notato niente per valori di S superiori a 108?
 
-- 
Dano

 Vi torna oppure ho sbagliato tutto?
 
Ciao Maurizio, mi pareva strano che non ti facessi sentire su questi
argomenti ;)
anche per me vale il beneficio di inventario, però mi risultano più
valori non vincenti:
27, 43 e 64 ce li ho anche io, ma ne trovo uno minore (17) e diversi
altri maggiori.
Se 17 non ti risulta perdente, fai la prima mossa :)
 
Nel frattempo vado a ricontrollare, forse sbaglio qualcosa.
Se qualcuno volesse seguire il mio approccio "Catalano" (vinco se tu
perdi sempre, perdo se tu non vinci mai), non dimentichi di registrare
e riutilizzare i risultati man mano che li acquisisce, altrimenti la
ricorsione risulta davvero pesante.
 
--
Silv:o)
 

 Nel frattempo vado a ricontrollare, forse sbaglio qualcosa.
 
e ti pareva: ho sbagliato la matrice di adiacenza del 4
{1,4,5,7} invece di {1,5,6,7}
 
confermo i valori di Maurizio
 
--
Silv:o)

 sono vincenti per l'avversario.
 
in realtà le due procedure sono una l'inversa dell'altra, tanto vale
usarne una sola.
In pratica basta questa funzione per risolverecompletamente il
problema, ho anche introdotto un vettore tristate (null,true,false)
per sapere se in passato abbiamo affrontato la situazione, e con che
esito, per evitare ricorsione inutile:
----------------
public static bool Vince(int l, int c){
    if (l < 0) return false; //ho sballato, non ho certo vinto
    if (vincenti[l, c].HasValue) return vincenti[l, c].Value; //
sfrutto l'esperienza
    bool vince = true;
    foreach (int i in adiacenti[c])
        vince = vince && !Vince(l - i, i);
    vincenti[l, c] = vince;
    return vince;
}
----------------
 
Tutto qui! l è il limite rimasto, c la posizione corrente.
Basta inizializzare il vettore delle adiacenze e chiamare per esempio
Vince(29,1) per sapere se si vince partendo da 1 e dovendo arrivare a
30, o Vince(30,0) per sapre se si vince parmettendo all'avversario la
prima mossa.
10 righe di codice, potenza della ricorsione!
 
--
Silv:o)


 
Un altro modo per affrontarlo è usare un foglio excel
http://wikisend.com/download/613260/ihe.xls
 
per ogni S e per ogni tasto il valore nella cella indica se partendo
da quel tasto si PERDE.
la colonna a fianco riporta l'OR di tutte i tasti della riga, ovvero
se si perde in ogni caso.
Come si vede, solo i tre valori più volte nominati perdono
sistematicamente.
Si vede anche quello che chiedeva Dano, ovvero cosa succede da un
certo punto in poi.
 
--
Ciao, Silv:o)

10 righe di codice, potenza della ricorsione!
 
Non conosco il C# e nemmeno ho il relativo compilatore perci� non
posso giudicare il tuo programma (io lavoro solo in C).
 
Comunque conoscendoti non dubito del tuo programma.
E' in grado di rispondere alle prime due domande che avevo posto?
Ripeto
 
- Nel caso S = 14, A � sicuro di vincere se preme un tasto diverso da
9?
 
- E' vero che se S = 29, chi gioca per primo pu� sempre vincere?
 
E aggiungo:
 
- Cosa succede per somme superiori a 108?
 
 
(poi ne ho anche delle altre)
-- 
Dano  

certo punto in poi.
 
Bello! Non avevo pensato di usare excel e l'output č molto simile al
mio programma.
Con questo puoi rispondere facilmente a tutte le mie domande.
 
Come hai rilevato dopo la somma 108 si ripete continuamente lo stesso
pattern: A puň vincere se gioca 3,5 o 7.
 
Cosa succede se cambiamo la disposizione dei tasti? Ad esempio se
utilizziamo la disposizione del tastierino numerico del PC?
 
Le possibili disposizioni dei tasti sono 9! = 362880. Tutte queste
generano giochi diversi oppure alcune generano il medesimo gioco? E
nel caso quante sono che generano giochi diversi?
 
Le sequenze come quella che hai generato terminano sempre con un
pattern che si ripete ciclicamente?
 
Quando esiste un ciclo č sempre unitario (una sola riga)? Se non lo č
quale disposizione ha il ciclo massimo?
 
Quale disposizione presenta il massimo numero di valori che assicurano
la vittoria al secondo giocatore? (nel nostro caso erano solo 3)
 
Quale disposizione assicura sempre la vittoria al primo giocatore?
 
E poi potremmo complicare il gioco ancora di piů ....
 
-- 
Buon lavoro. Dano 

 (poi ne ho anche delle altre)
 
--
Ciao, Silv:o)

Quale disposizione assicura sempre la vittoria al primo giocatore?
 
Ne esistono moltissime (sono pi� del 10%)
 
Un altro elemento variabile � intervallo che esiste prima che inizi il
primo ciclo. Nel caso proposto il primo ciclo iniziava a 108; non �
affatto il massimo che � di 556 mentre il minio � zero: il ciclo pu�
iniziare dal numero 0.
Il numero di disposizioni perdenti in questo intervallo pu� arrivare
fino a 32 (nel caso di massima lunghezza di 556).
 
Arrivederci al prossimo problema (ci sto pensando)
 
-- 
Dano
 

 caratteristiche.
 
Qui secondo me sta il secondo motivo per cui il thread ha perso di
appeal. L'interesse maggiore per me è trovare lo strumento, analizzare
le varianti è un po' meno divertente. Abbiamo scoperto che si può
affrontare con la programmazione, magari ricorsiva ed anche con Excel.
Si può istruire facilmente un automa che impara a giocare.
Invece quello che mi sarebbe piaciuto è trovare una strategia "a
mano", con considerazioni per esempio legate a simmetrie,
complementarietà, raggruppamenti dei tasti.
 
Il gioco di Nim è un bellissimo gioco perchè ha una strategia molto
difficile da trovare se non la si conosce, è allo stesso tempo
semplice e complesso anche per piccole dimnsioni, si può giocare con
divertimento per tentativi; si può ovviamente affrontare per via
algoritmica o con gli automi ma difficilmente ci avvicineranno alla
magia dello xor.
 
--
Ciao, Silv:o)

 almeno due partecipanti per tenere viva una discussione
 
intendevo almeno altri due oltre al proponente :)
 
--
Silv:o)

magia dello xor.
 
Mi ricordo quando stupii i miei amici con un mio programma in basic su
Commodore 64 che giocava a Nim e non perdeva mai!
 
Prova a dare un'occhiata al mio prossimo messaggio sul gioco Matrix.
 
-- 
Ciao, Dano

 Qualche riferimento su Internet?
 
polya burnside
 
-- 
Ciao, Silv:o)