Zugzwang!

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
Rispondi
Veritasium
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Zugzwang!

Messaggio da Veritasium »

[tex]n \ge k \ge 2[/tex] sono interi positivi.

Adalberone è stato ammesso al Senior 2016 (ha contatti ai piani alti e lo sa già), ma viene catturato da un Genio Maligno che lo lascerà libero se e solo se il giovane matematico riuscirà a batterlo al seguente gioco: il GM possiede $2n$ carte, numerate con gli interi $1, 2,..., n$ in modo che ci siano esattamente $2$ carte numerate $i$ per ogni $1 \le i \le n$. Inizialmente le dispone in fila, coperte, in un certo ordine, ignoto ad Adalberone.
Adalberone può fare delle mosse: una mossa consiste nello scegliere $k$ carte e scoprirle: se ce ne sono $2$ la cui numerazione coincide, il gioco finisce. Altrimenti, il GM prende le $k$ carte e le riposiziona coperte nei $k$ posti vuoti in un certo ordine, sempre ignoto ad Adalberone (che quindi sa solo che in qui $k$ posti ci sono quele $k$ carte, ma non quale carta in quale posto). Dopodichè, tocca di nuovo muovere ad Adalberone.
Diciamo che Adalberone vince il gioco se può forzare la fine del gioco, ovvero se esiste un intero $m$ (dipendente da $n, k$) tale che, indipendentemente da come giochi il GM, Adalberone ha una strategia che gli consente, dopo al più $m$ mosse, di scoprire con assoluta certezza una coppia di carte con la stessa numerazione.

Determinare tutti i valori di $n, k$ che consentono ad Adalberone di partecipare al Senior
Rispondi