Il viaggio infinito (ispirato ad una storia vera)

[Gerald Lambeau]

La prima stima non era sbagliata, ma questa qui è decisamente migliore, cioè se ne va una quantità pazzesca di tempo!
Un solo computer ce la farebbe in 276 giorni (si considera sempre però che ogni caso venga fatto istantaneamente)!
Senti, facciamo una cosa: ci si organizza scuola mia e scuola tua, occupiamo le rispettive aule di informatica e in un mese abbiamo la risposta!

[Gerald Lambeau]

Talete, in media quanti turni dura una partita?

[Sirio]

@Gerald guarda che la mia scuola è parecchio grande, mi sa che basta

[fph]

Vi consiglio di partire a scrivere un codice bovino che simula il gioco; secondo me finirà che qualche esempio che va in loop lo trovate. Il metodo che userei è ricordarsi degli hash delle posizioni passate, giusto per vedere (in modo non rigoroso) se ne reincontrate una già trovata.

[Drago96]

Facciamo che vi lascio un link utile xD
https://sites.google.com/site/alessandr ... -neighbour

Lo script in python ci mette circa 0.14ms per mazzi random, mentre per le partite più lunghe finora trovate circa 2ms

[fph]

Molto interessante. In particolare sembra che il problema per mazzi di 40 carte o 52 carte sia ancora aperto, e che per 20 carte le partite infinite ci sono ma sono solo 16. Dov'è lo script Python? Vedo solo un programma in C++ nel tuo link.

[Sirio]

@Gerald ho notato che se tutte le carte A, 2, 3 ce le ha lo stesso giocatore la partita è già finita...

[Gerald Lambeau]

@Gerald ho notato che se tutte le carte A, 2, 3 ce le ha lo stesso giocatore la partita è già finita...

Noi vogliamo sapere se finisce sempre, quindi questo non vale come controesempio, ne serve uno dove dura all'infinito.

[Sirio]

Vale per ridurre il tempo del computer, zucca!

[Gerald Lambeau]

Vale per ridurre il tempo del computer, zucca!

Sì vabbè, te li salvi come già risolti quei casi, ma tanto ci hanno già informato su quanto veloce può essere il programma, è inutile mettersi a cercare ogni sottogruppo di casi che possiamo evitare di controllare, a questo punto tanto vale risolverlo normalmente.

PS: poi non vuoi scriverlo sul serio il programma, vero? Cioè, siamo in un forum di matematica, preserviamo lo spirito matematico delle dimostrazioni pure

[Sirio]

dimostrazioni pure

Chi è capace le fa, chi sta ancora imparando si arrangia come può

[Gerald Lambeau]

dimostrazioni pure

Chi è capace le fa, chi sta ancora imparando si arrangia come può

In realtà, non so se la soluzione puramente matematica di questo problema esista (fph ci ha detto che è ancora un problema aperto), quindi vai tranquillo, magari quello che hai pensato non sarà il modo più elegante, ma sicuramente è il più fattibile, almeno per ora.

[Sirio]

$\Rightarrow$ avrò a disposizione un computer a Cesenatico Q.E.D. (Talete questa è per te)

[Sirio]

...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?

Talete per favore rispondimi!!! Ho provato a giocare con mio fratello e le partite duravano tre minuti mi sa che ho capito male le regole

[Drago96]

@fph: basta seguire un po' di link e si giunge a https://github.com/matthewmayer/beggarmypython

Comunque in C++, creando le giuste strutture (es: un mazzo può occupare 80 bit, dato che interessano solo i numeri 0-3) secondo me si può ottimizzare abbastanza.
Però servirebbe in ogni caso un'enorme quantità di risorse (non infattibile, ma comunque tante)