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

[3m0o]

Edit:

Testo nascosto, fai click qui per vederlo

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

[Brancaleone]

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

Testo nascosto, fai click qui per vederlo

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 )

Testo nascosto, fai click qui per vederlo

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

[Brancaleone]

Testo nascosto, fai click qui per vederlo

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 …

[3m0o]

Testo nascosto, fai click qui per vederlo

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

Testo nascosto, fai click qui per vederlo

… alla seconda mossa il giocatore 1 ignora il suo primo numero …

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

… 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

[3m0o]

Testo nascosto, fai click qui per vederlo

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]

Testo nascosto, fai click qui per vederlo

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