Strategia

[axpgn]

Supponiamo che due giocatori, a turno, scrivano su una lavagna un intero positivo soggetto a due condizioni:

1) nessun intero può essere maggiore di un limite $L$ prefissato
2) nessun intero può essere un divisore di un numero già scritto

Perde la partita il primo che non può più giocare.

Provare che, qualsiasi sia il limite $L$, esiste sempre una strategia vincente per il primo che gioca.

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Edit:

Ci penso, ma preciserei che questa strategia esiste per ogni \(L > 1 \) se lo zero può essere scritto oppure \(L > 2 \) se lo zero non può essere scritto.
Infatti nel primo caso se \(L=1 \)
Il primo giocatore scrive \(0 \) e il secondo \(1 \), e il primo perde.
Il primo giocatore scrive \(1\) e il secondo \(0\), ed il primo perde.

Ho detto una cavolata....mi sono dimenticato della seconda condizione

[Brancaleone1]

Non sono sicuro che si risolva così, ma ci provo - chiedo venia nel caso scriva delle boiate:

Esiste un teorema (per mia ignoranza non so se corrisponde al teorema Zermelo-Kuhn) che afferma come una strategia vincente per uno dei giocatori esiste SE sussistono tutte le seguenti ipotesi:

1) il gioco è condotto da due giocatori che eseguono alternativamente una mossa;
2) il gioco termina con la vittoria o del primo o del secondo giocatore (non esiste possibilità di pareggio);
3) i giocatori possono muovere scegliendo un'azione tra un insieme di mosse possibili;
4) in ogni istante i giocatori sono informati completamente su tutte le mosse già compiute e su tutte quelle che potranno essere fatte;
5) esiste un limite superiore per il numero di mosse in una partita.

Per il caso in esame, tutte queste ipotesi sono verificate, quindi uno dei giocatori ha una strategia vincente.
Mettiamo per assurdo che il secondo giocatore abbia questa strategia vincente. Dato che il teorema funziona per qualunque numero di mosse a patto che non sia infinito, e dato che $L$ può essere un qualunque numero intero positivo (cioè $0$ escluso), pongo il caso $L=2$, dove l'unica mossa valida è:

1° giocatore: $2$

Il 2° giocatore perde, ma questo risultato è in contrasto con l'assunzione che egli abbia una strategia vincente che deve quindi appartenere al 1° giocatore.

[axpgn]

Buonissima risposta ma mi pare che manchi un punto fondamentale (o almeno così credo io, sbagliando )

Non conosco il teorema in questione e d'altronde le "regole" sono tutte rispettate; tuttavia non mi pare di desumere da ciò che la strategia vincente (che dal teorema sicuramente esiste), sia sempre riferita a uno solo dei due ovvero potrebbe dipendere da $L$: per alcuni $L$ vince sempre il primo che gioca, per altri $L$ vince sempre il secondo.

Allora potremmo fare così: assumo che la tua risposta vada bene ma riusciresti a trovare una procedura che non dipenda da uno specifico $L$ nella dimostrazione?

Cordialmente, Alex

[Brancaleone1]

"axpgn":
Allora potremmo fare così: assumo che la tua risposta vada bene ma riusciresti a trovare una procedura che non dipenda da uno specifico $L$ nella dimostrazione?

Mi arrendo: non ne so abbastanza per dare una risposta di senso compiuto

[axpgn]

Eppure ci sei vicino …

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Sopra Brancaleone ha dimostrato che esiste sempre una strategia vincente. Tento qui di dimostrare che tale strategia non può essere del secondo giocatore, per ogni \(L\).
Terminologia: Una mossa consiste nelle seguenti operazioni, il giocatore 1 prima e successivamente il giocatore 2 scrivono ciascuno un numero rispettando le due regole date.
Fissiamo \(L\), e supponiamo per assurdo che il secondo giocatore abbia una strategia vincente \(S_L\).
Allora alla prima mossa il giocatore 1 scrive un numero a caso \(1 \leq k \leq L \), il secondo giocatore scrive il numero relativo alla strategia vincente \(S_L\), alla seconda mossa il giocatore 1 ignora il suo primo numero e gioca come se fosse il secondo giocatore applicando \(S_L\). Se la strategia \(S_L\) gli dicesse di scrivere \( k\) allora scrive un numero a caso e quest'ultimo sarà il numero ignorato d'ora in poi dal giocatore 1 (nel caso iterare).
Siccome \(S_L\) è vincente allora il giocatore 1 vince la partita da lui ipotizzata e quindi vince anche la vera partita poiché iniziare per primi non influisce sul fatto che il giocatore 2 non possa più scrivere nessun numero nella partita ipotetica, ma anche il giocatore 2 vince poiché \(S_L\) è vincente, assurdo!
Quindi \(S_L\) non esiste!

[axpgn]

Mi sono perso

"3m0o":… alla seconda mossa il giocatore 1 ignora il suo primo numero …

Che significa? Una volta scritto, il numero è scritto, non si può "ignorare" …

"3m0o":… alla seconda mossa il giocatore 1 … gioca come se fosse il secondo giocatore applicando \( S_L \). …

Ma non può farlo perché se il secondo giocatore ha una strategia vincente questo significa che dopo aver giocato la sua prima mossa, qualunque siano le mosse fatte successivamente dal primo giocatore, egli può sempre controbatterle, altrimenti NON avrebbe una strategia vincente

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Si chiama strategy-stealing argument, ed è una dimostrazione per assurdo usata nella teoria dei giochi.
https://en.wikipedia.org/wiki/Strategy-stealing_argument

Ma ora mi viene il dubbio che questo gioco possa avere uno zugzwang e dunque questa argomentazione non può essere utilizzata.

[axpgn]

Ho dato solo un'occhiata al link ma non è questo il punto (a occhio penso sia lo stesso concetto già detto da Brancaleone): come l'hai scritta tu non è quella dimostrazione, non è chiara, insomma non funziona
Rileggi anche solo i due punti che ti ho sottolineato …

Che significa "ignorare"? Cosa intendi dire precisamente?
Cosa significa "il primo gioca come il secondo ma dopo che ha già fatto la sua prima scelta"?
Non è questo che si intende con "rubare il gioco …
Non dico di più, per ora … …

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"axpgn":

Ho dato solo un'occhiata al link ma non è questo il punto (a occhio penso sia lo stesso concetto già detto da Brancaleone): come l'hai scritta tu non è quella dimostrazione, non è chiara, insomma non funziona
Rileggi anche solo i due punti che ti ho sottolineato …

Che significa "ignorare"? Cosa intendi dire precisamente?
Cosa significa "il primo gioca come il secondo ma dopo che ha già fatto la sua prima scelta"?
Non è questo che si intende con "rubare il gioco …
Non dico di più, per ora … …

Cordialmente, Alex

No sono due cose diverse!
Ignorare significa questo: il primo giocatore scrive un numero \(k_1 \) il secondo giocatore applica la strategia vincente \(S_L\) e scrive \( \ell_1 \), il primo giocatore ora gioca come se non avesse scritto \(k_1\) e applica \(S_L\) e considera \( \ell_1 \) come primo numero.
Mi sono reso conto però che non funziona poiché muovere per primo può essere uno svantaggio se scrive il numero sbagliato. Ad esempio se \(L=3 \), e il primo giocatore scrive \(3\) oppure \(2\) perde sicuramente.
E questo ragionamento può essere applicato solo nei giochi in cui muovere per primo non è mai uno svantaggio indipendentemente dalla mossa che uno fa.

Edit:

Oddio... non so in realtà, non ho mai fatto teoria dei giochi seriamente. Magari è applicabile a questo gioco, ma non ne ho idea. L'unico problema che vedo è che se la strategia \(S_L\) applicata al primo numero \( \ell_1\) dice al primo giocatore di scrivere un numero che è un divisore di \(k_1\).
Se gli dicesse di scrivere \( k_1 \) oppure non un divisore di \(k_1\) allora la strategy-stealing argument funziona. Ma potrebbe non essere questo il caso, quindi... mah?!

[axpgn]

"3m0o":… il primo giocatore ora gioca come se non avesse scritto \(k_1\) e applica \(S_L\) e considera \( \ell_1 \) come primo numero. …

Scusami ma questo non ha senso, un giocatore non può giocare come "se non avesse fatto" quella mossa per il semplice fatto che l'ha fatta ovvero sono due "sequenze" di gioco diverse aver fatto una mossa e non averla fatta, inoltre un giocatore NON può nello stesso gioco "usare" la strategia vincente (se esiste in quel gioco) dell'altro perché se fosse possibile allora la strategia NON sarebbe vincente per l'altro … ok?

D'altronde, mi pare che hai constatato tu stesso che non funziona

Ho detto troppo … per ora …

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"3m0o":
Edit:

Oddio... non so in realtà, non ho mai fatto teoria dei giochi seriamente. Magari è applicabile a questo gioco, ma non ne ho idea. L'unico problema che vedo è che se la strategia \(S_L\) applicata al primo numero \( \ell_1\) dice al primo giocatore di scrivere un numero che è un divisore di \(k_1\).
Se gli dicesse di scrivere \( k_1 \) oppure non un divisore di \(k_1\) allora la strategy-stealing argument funziona. Ma potrebbe non essere questo il caso, quindi... mah?!

E se fosse solo questo il problema potrebbe essere risolto così:
Il primo giocatore scrive \(1\) al posto di \(k_1\), poi il secondo giocatore applica \(S_L\) a \(1\) scrive \( \ell_1\) e il primo giocatore applica \(S_L\) a \(\ell_1\), ed entrambi vincono, assurdo!

"axpgn":

[quote="3m0o"]… il primo giocatore ora gioca come se non avesse scritto \( k_1 \) e applica \( S_L \) e considera \( \ell_1 \) come primo numero. …

Scusami ma questo non ha senso, un giocatore non può giocare come "se non avesse fatto" quella mossa per il semplice fatto che l'ha fatta ovvero sono due "sequenze" di gioco diverse aver fatto una mossa e non averla fatta, inoltre un giocatore NON può nello stesso gioco "usare" la strategia vincente (se esiste in quel gioco) dell'altro perché se fosse possibile allora la strategia NON sarebbe vincente per l'altro … ok?

D'altronde, mi pare che hai constatato tu stesso che non funziona

Ho detto troppo … per ora …

[axpgn]

Mi spiace ma mi pare che non tu non abbia compreso cosa significhi "rubare il gioco" (oppure nel modo in cui lo hai scritto non è questo che si capisce ma tutt'altro … IMHO )

Ovvero NON puoi "rubare il gioco" mentre stai giocando ma lo puoi fare a priori (se si può fare ovviamente)

Ma tagliamo la testa al toro, ecco la mia dimostrazione:

Chiamo $A$ colui che gioca per primo e $B$ colui che gioca per secondo.

Supponiamo che $B$ abbia sempre una strategia vincente ovvero qualsiasi mossa faccia $A$ (prima compresa), $B$ è in grado di ribatterla, sempre. Chiaro?
Se $B$ non è in grado di rispondere sempre nel modo giusto, significa che NON ha sempre una strategia vincente.

Il numero $1$ può essere scritto (eventualmente) solo da $A$ e solo alla prima mossa di $A$.
Supponiamo che $A$ parta con lo scrivere il numero $1$; allora, siccome abbiamo supposto che $B$ ha sempre una strategia vincente, esiste almeno un $n$ compreso tra $1 Ma allora ne consegue che $A$ può iniziare lui da quel preciso $n$ e quindi vincere sicuramente.
D'altra parte se non esistesse nessun $n$ (compreso tra $1
In entrambi i casi $A$ ha sempre una strategia vincente.

(quale effettivamente questa sia è un altro paio di maniche )

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"3m0o":

E se fosse solo questo il problema potrebbe essere risolto così:
Il primo giocatore scrive \(1\) al posto di \(k_1\), poi il secondo giocatore applica \(S_L\) a \(1\) scrive \( \ell_1\) e il primo giocatore applica \(S_L\) a \(\ell_1\), ed entrambi vincono, assurdo!

Si esatto così funziona!!
Supponiamo che esiste una strategia vincente \(S_L(n)\) per il secondo giocatore, questo vuol dire che qualunque sia il numero \(n\) con \(1 \leq n \leq L\) scritto dal primo giocatore il secondo può sempre rispondere in modo tale che vince la partita.
Chiaramente per la regola 2. se il primo giocatore scrive un numero \(n\) compreso tra \(1 < n \leq L\) allora la strategia \(S_L(n)\) non dirà mai al secondo giocatore di scrivere \(1\) poiché non è un numero valido siccome \(1\) è divisore di \(n\).
Vogliamo dimostrare che l'esistenza di una strategia vincente \(S_L(n)\) per il secondo giocatore implica l'esistenza di una strategia vincente \(\tilde{S}_L\) per il primo giocatore, e questo è un assurdo poiché solo uno dei due può vincere la partita.
Partita ipotetica: strategia \(S_L(n) \) con \(1 < n \leq L \)

Sotto le nostre ipotesi abbiamo che se il primo giocatore scrive un numero qualunque numero tra \(1 < n \leq L \) allora il secondo giocatore vince scrivendo \( k_n \neq 1 \) in risposta a \(n\).

Partita reale: La strategia vincente \( \tilde{S}_L \) per il primo è la seguente scrive \(1 \) poi gioca \( S_L(S_L(1)) \).

Il giocatore 1 scrive \(1\).
Il giocatore 2 scrive \( S_L(1)\) e vince la partita
Il giocatore 1 scrive \( S_L( S_L(1) ) \) e vince la partita
Se il giocatore 1 non vincesse la partita vuol dire che se alla prima mossa avesse scritto \( S_L(1) \) allora il giocatore 2 non possiede una strategia vincente per questo numero, che va contro le nostre ipotesi.

Quindi se esiste una strategia vincente per il secondo giocatore esiste una strategia vincente per il primo e questo è assurdo!

E come puoi vedere ho applicato la strategy-stealing argument!! E non c'è alcun problema nel farlo!

Ps: ho notato adesso che abbiamo scritto la stessa cosa
Probabilmente mi ero spiegato male inizialmente, ma intendevo questo con la strategy-stealing argument.

Ho capito cosa non hai capito nel mio ragionamento iniziale. (edit:)

Al di là del fatto che la strategy-stealing per questo gioco funziona solo se il primo giocatore scrive \(1\) e non un numero a caso come pensavo inizialmente. Ma quando intendevo che gioca ignorando il primo numero intendevo che nella sua testa fa una partita ipotetica (guarda il messaggio sopra) in cui lui è il secondo giocatore, questa partita ipotetica risulterebbe vinta dal secondo giocatore applicando \(S_L\) e in questa partita ipotetica lui è il secondo giocatore. Siccome vince la partita ipotetica vince anche la partita reale in cui scrive \(1\) ed è primo giocatore, ma è assurdo se il secondo giocatore possiede una strategia vincente.
Chiaro che sia la "partita ipotetica" che la "partita reale" sono giocate a priori poiché non esiste alcuna partita in cui il secondo giocatore possiede una strategia vincente, ma sotto l'ipotesi che il secondo possieda una strategia vincente (cosa non fattibile) può effettivamente giocare la "partita reale" rubando la strategia "a posteriori", ma dal momento che l'ipotesi non è mai soddisfatta non potrà mai giocare questa "partita reale" e rimane un argomentazione a priori.
Sostanzialmente tu mi dici che il primo giocatore vince o la "partita ipotetica" o la "partita reale" quindi il primo possiede una strategia vincente ed il secondo no, ed è corretto!
Io dico che qualunque numero scriva il primo giocatore il secondo giocatore vince, ma sotto questa ipotesi sia il primo che il secondo giocatore vincono la "partita reale", assurdo! Ed è corretto!

[axpgn]

"3m0o":Probabilmente mi ero spiegato male inizialmente, …

E da un po' che te lo stavo dicendo … e non è indifferente la cosa

Cordialmente, Alex