OliForum Matematico

Durante il viaggio in autobus da Bensheim a Riva del Garda, durato in totale $13$ ore, Alessia e Cesare, avendo tanto buontempo, si mettono a giocare al famosissimo gioco "un-due-tre", così funzionante: si usano le carte da briscola estesa (dall'asso al dieci più fante, cavallo e re; di quattro semi distinti, coppe, bastoni, spade e ori), che vengono divise equamente tra Alessia e Cesare, impilate e mescolate a faccia in giù. Dunque ciascuno dei due ha la sua pila di ventisei carte con cui giocare. Alessia parte, prende la sua prima carta e la appoggia sul tavolino. D'ora in poi tutti i turni saranno così: se l'ultima carta in cima al tavolino è dal quattro in su (quindi non un asso né un due né un tre), si prende la propria prima carta e si gira a faccia in su sopra la pila del tavolino; se invece è una carta di segno $n\le3$, allora l'altro deve girare le prime $n$ carte dalla sua pila e porle sul tavolino. Le $n$ carte si girano una alla volta: se tutte e $n$ sono dal quattro in su, allora la persona che aveva giocato la carta di segno $n\le3$ prende tutta la pila del tavolino e la gira a faccia in giù mettendola sotto la propria pila di carte; se invece nel girare $n$ carte giunge anche una carta di segno $n\le3$, il turno passa all'altra persona. Quando un giocatore prende tutta la pila del tavolino e la gira a faccia in giù mettendola sotto la propria pila di carte (d'ora in poi quest'azione verrà detta "mossa X"), tocca a costui partire: prende la sua prima carta in cima e la appoggia sul tavolino, e poi è il turno dell'altro. Perde il giocatore che rimane senza carte.

a) Il gioco è sempre finito?
b) Supponiamo che il gioco sia finito e che Alessia e Cesare inizino a giocare appena saliti sull'autobus e smettano esattamente alla fine del viaggio, senza pause. Qual è la probabilità che la partita sia terminata, considerato che entrambi ci mettono $1$ secondo a girare la prima carta del mazzo e a porla sul tavolino, e che Cesare ci mette $3$ secondi a fare la mossa X mentre Alessia, avendo la mano fasciata, ne impiega $5$?

Ringrazio Alessia per l'idea e per avermi tenuto compagnia durante il viaggio.

Io il problema non l'ho risolto... l'unica partita fatta è durata $33$ minuti, non so se rendo l'idea...

Se non si capisce chiedete pure chiarimenti eh

Un annetto fa avevo effettivamente provato, ma dopo solo un paio d'ore di tentativi mi ero convinto a rinunciare, chiunque proverà ne capirà il motivo. Comunque mi fa piacere vedere qualcuno che abbia trovato la voja e la sfrontatezza di postarlo spacciandolo per problema

RiccardoKelso ha scritto:Un annetto fa avevo effettivamente provato, ma dopo solo un paio d'ore di tentativi mi ero convinto a rinunciare, chiunque proverà ne capirà il motivo. Comunque mi fa piacere vedere qualcuno che abbia trovato la voja e la sfrontatezza di postarlo spacciandolo per problema

Ahahhah io non ci ho neanche provato, quando Alessia mi ha chiesto "Tu che sei bravo in matematica, sai se questo gioco finisce sempre?" ho risposto una cosa tipo "Sì sì finisce sempre perché ad un certo punto ci si annoia" così l'ho fatta ridere e l'ho distolta dalla domanda. Perfido, eh?

Dai dai Riccardo provaci ancora! A chi lo risolve offro una piadina, facciamo così

Vale scrivere un programma che lo risolva (ammesso che esista)?

Sirio ha scritto:Vale scrivere un programma che lo risolva (ammesso che esista)?

Scrivi pure... sono ignorantissimo di informatica quindi poi devi spiegarlo bene

D'accordo, vediamo un po'...

Sirio ha scritto:Vale scrivere un programma che lo risolva (ammesso che esista)?

Scrivere un programma che lo risolva non è difficile, basta fare un simulatore che prova tutti i casi possibili e fa andare avanti il gioco fino a che non finisce oppure quando una situazione già avvenuta si ripresenta (ciò è possibile perché il numero di situazioni è finito [credo, cioè sono abbastanza sicuro ma non ho voglia di vedere i dettagli di questa cosa]); comunque, anche ammettendo che il programma prima o poi finisca, ci sono un bel po' di casi da controllare, e secondo i miei conti ci vorrebbero circa 10 milioni di miliardi di miliardi di miliardi di anni per farlo girare se usasse una sola operazione per ogni caso possibile, cosa assurdamente ottimistica. Se anche avessi sbagliato la stima, ma anche di tanto eh, sarei propenso a dire che anche un solo milione di anni sarebbe troppo (ma anche solo mille anni sono troppi, cioè capisci che margine di errore mi sono potuto permettere nella mia stima? E dire che sono stato un pochino ottimista quando l'ho fatta), e quello ce lo impiega sicuramente (e si scopri invece che ho cannato tutti i conti...). Quindi, o aspetti che finisca tutti i casi o aspetti l'era dei computer quantici.
In ogni caso, in bocca al lupo!

PS: ovviamente le stime sono fatte sulla base dei computer in commercio e delle conoscenze livello scuola/gare, do per scontato che siano queste le risorse a tua disposizione; cioè, mi immagino che tu non abbia a disposizione un supercomputer né conoscenze universitarie molto avanzate, come ogni studente delle superiori, e comunque, considerando sempre il margine che la mia stima si può permettere (stima che ho ripetuto per sicurezza), non credo la situazione sia ottimistica nemmeno per chi ha le sopracitate risorse.

Talete, credo che dovresti offrire ben più di una piadina (per quanto buona possa essere)

Gerald Lambeau ha scritto:quando una situazione già avvenuta si ripresenta

Eh sì, ma memorizzale tu tutte le situazioni. Nel senso, se controlli che partendo dalla situazione $A$ non si torni mai in $A$, il caso (che non so se esista) $A\rightarrow B\rightarrow C\rightarrow D\rightarrow\cdots\rightarrow C$ o un caso simile ti frega.

Comunque sì, effettivamente ci metterebbe troppo, lascio stare (e addio piadina )

Sirio ha scritto:

Gerald Lambeau ha scritto:quando una situazione già avvenuta si ripresenta

Eh sì, ma memorizzale tu tutte le situazioni. Nel senso, se controlli che partendo dalla situazione $A$ non si torni mai in $A$, il caso (che non so se esista) $A\rightarrow B\rightarrow C\rightarrow D\rightarrow\cdots\rightarrow C$ o un caso simile ti frega.)

Sì lo so, quello intendevo, ma lasciamo perdere, abbiamo constatato che i problemi di un programma che risolva il quesito sono ben altri.

Però, dico io, se mettessimo ogni computer della mia scuola a cercare se tot partite sono finite (senza che $2$ o più computer cerchino sulla stessa partita) direi che in tempi ragionevoli otteniamo un risultato...

Dico, ma hai visto quanto tempo ci vuole? Se anche la tua scuola avesse 10 milioni di miliardi di computer ci vorrebbero comunque 1 miliardo di miliardi di anni. E ripeto, anche se la stima fosse sbagliata, pure mille anni sono troppi!

C'è una cosa che non ho detto però: il tempo stimato è quello che impiegherebbe il programma a verificare che il gioco sia effettivamente finito. Se non lo fosse, il programma finirebbe prima. In tal caso, basterebbe un controesempio e possiamo provare solo quello, per vedere se quella partita prima o poi entra in un ciclo. Quello si può fare (credo, non ne sono sicuro).
Se il gioco finisce sempre, invece, la soluzione informatica è da abbandonare, e l'unica via è quella della dimostrazione matematica.

Ad ogni modo, da quello che dice Drago sospetto che, qualunque sia la soluzione, esiste una dimostrazione!

Comunque il tempo si riduce wloggando (termine brutto che però non ho coniato io) le carte dal 4 in su (nel senso che non fa differenza in nessun caso se esce un 4 o un K)

Talete ha scritto:...se invece nel girare $n$ carte giunge anche una carta di segno $n\le3$, il turno passa all'altra persona.

Altra persona che però non fa la mossa X giusto?

Sirio ha scritto:Comunque il tempo si riduce wloggando (termine brutto che però non ho coniato io) le carte dal 4 in su (nel senso che non fa differenza in nessun caso se esce un 4 o un K)

Provo a rifare la stima contando anche questa cosa, ti dico come andrà.