2021 carte

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Considerate 2021 carte, ciascuna delle quali da un lato è bianca e dall'altro è nera che stanno tutte parallele lungo un tavolo. Inizialmente tutte le carte mostrano il loro lato bianco. Ci sono due giocatori che giocano alternandosi le mosse. Ciascuna mossa consiste nel scegliere un blocco di 50 carte consecutive, di cui la prima (quella più a sinistra) mostra il lato bianco e girare tutte, in questo modo le carte che mostravano il lato bianco ora mostrano il lato nero e viceversa. L'ultimo giocatore che può fare una mossa legale vince.

a) Il gioco termina necessariamente?
b) Esiste una strategia vincente per il primo giocatore?

[Folpo13]

È più qualitativa che quantitativa come dimostrazione, ma dovrebbe aver senso

Intanto si può dire che se una carta da nera torna bianca, necessariamente una carta alla sua sinistra è diventata da bianca a nera. Questo ha due conseguenze:
•La carta nera posta più a sinistra non potrà mai "muoversi" verso destra
•Quando la carta in posizione 1 è nera, questa rimane tale (e in generale quando le prime $n$ carte sono nere, queste rimangono tali)

Ora, se la carta nera più a sinistra (chiamerò $N_s$) non si "sposta" verso sinistra è perché c'è almeno una carta bianca alla sua destra, e $N_s$ si trova tra le prime $1971$ carte.

Consideriamo quindi le carte dal primo spazio bianco a destra di $N_s$ in poi. Questo si comporta proprio come il nostro insieme globale di carte: in questo nuovo set di carte la carta nera più a sinistra può muoversi solo a sinistra, e se non è mossa è perché c'è una carta bianca alla sua destra, e così avanti. Ad un certo punto ci sarà necessariamente una carta nera che non ha più carte bianche a "disposizione" (se ce ne sono si può considerare come prima il set di carte bianche come quello di partenza).

Si arriverà quindi sempre ad un punto tale che $N_s$ si dovrà muovere a sinistra. Arriverà quindi in posizione $1$ e a questo punto si rifà lo stesso gioco ma semplicemente considerando le 2020 carte rimaste. Ad un certo punto la "nuova" $N_(s2)$ arriverà in posizione $2$, poi un'altra in posizione $3$ e così via... Quando la prime $1972$ carte saranno tutte nere a quel punto non saranno più possibili altre mosse




Forse è poco chiara la spiegazione, utilizza un approccio quasi "ricorsivo" e forse ho dato qualcosa per scontato che non avrei dovuto, ma almeno nella mia testa ha senso .

Non ho ancora provato a vedere se esiste una strategia vincente per uno dei due giocatori

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Premesso che faccio fatica a capire cosa dici, ma è molto più semplice di così

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Folpo13 ciao, ho riletto e capito cosa volevi dire, è giusto

Si può fare anche così per a)

Per semplicità associamo \(1 \) ad una carta bianca e un \(0\) ad una carta nera. Iniziamo con un numero intero formato da duemilaventuno \(1\), chiamiamo questo numero \(k_0 \). Il gioco termina quando non ci sono più mosse legali o quando (se possibile) si raggiungono duemilaventuno \(0\). Se indichiamo con \(k_n \) l'intero associato prima del \(n\)-esima mossa, abbiamo che \(k_n > k_{n+1} \) per ogni \(n \geq 0 \). Pertanto il gioco termina dopo un numero finito di step poiché ci sono solo un numero finito di interi compresi tra \(k_0 \) e \(0\).

[Folpo13]

"3m0o":Folpo13 ciao, ho riletto e capito cosa volevi dire, è giusto

Devo migliorare in chiarezza, lo so

"3m0o":
Se indichiamo con \(k_n \) l'intero associato prima del \(n\)-esima mossa, abbiamo che \(k_n > k_{n+1} \) per ogni \(n \geq 0 \).

Non sono sicuro di questo passaggio. Alla prima mossa hai sicuramente 50 carte nere, alla mossa dopo puoi averne 2 o 100.
Forse ho capito male cosa intendi dire

Edit: penso di aver capito cosa intendi
Il tuo metodo è più semplice e intuitivo in effetti. Vedo se riesco a lavorarci per il punto 2

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Supponi che il tuo numero \(k_n\) sia
\[ k_n=\sum_{j=1}^{2021} a_j 10^{2021-j} \]
dove \( a_j \in \{0,1 \} \) per ogni \(j\). O non ci sono mosse possibili e il gioco termina, oppure se ci sono vuol dire che c'è una carta bianca ad un certo \( j \leq 1972 \) seguito da 50 carte, diciamo \( j= x \). Quindi hai \( a_x = 1 \). Ora hai
\[ k_{n+1} = \sum_{j=1}^{x-1} a_j 10^{2021-j} + 0 \cdot 10^{2021-x} + \sum_{j=x+1}^{x+49} b_j 10^{2021-j} + \sum_{j=x+50}^{2021} a_j 10^{2021-j} \]
dove \( b_j = 1 \) se \( a_j = 0 \) e viceversa, per \( x+1 \leq j \leq x + 49 \). Ora chiaramente hai
\[ k_{n+1} < k_n \]
perché in posizione \( 10^{2021-x} \) in \(k_{n+1} \) c'è uno zero mentre in \( k_n \) c'è un \(1\), di quelli dopo te ne freghi.