Olimpo Informatico

[Salmastro]

Smjert!
dacci una dritta meno criptica

Salmastro

[ulisse]

In attesa che l'amico di Smjert (che Smjert riesce a contattare in meno di 19 minuti!) si sbottoni un po' di più, propongo una generalizzazione.

Stessa situazione, stesse regole, stesse persone, stesso boia.
Insomma tutto uguale con una sola variante: i colori dei cappelli non sono solo 2 ma ben 10...

[Salmastro]

no, proprio non mi riesce!!!
...avevo pensato che, essendo dieci i condannati dieci fosse il max di colori per i quali fosse possibile trovare una soluzione. E che la generalizzazione fosse legata a: N condannati, N colori.
Per semplicità invece di colori ho usato nel mio ragionamento i numeri, anzi le cifre: è più facile scrivere le configurazioni!, che per inciso sarebbero
n^(n-1)
(se vale N cond. x N colori)
Per cui 2 cond. e 2 colori: 2 configurazioni (quelle viste dal primo)
per 3 si hanno 9 configurazioni, per 4 ben 64 e così via fino a 10^9.
Come fa il primo a dare una dritta disambigua a tutti?
Avevo pensato alle classi di resti modulo N. E cioè che comunicasse, con lo stabilito codice dei colori, la classe di appartenza della configurazione.
(per esempio: se bianco=0; nero=1; rosso=2
quando il 1° vede rosso-rosso-bianco, "legge" come 220, dice "nero", cioè 1, perchè 1 è il resto della divisione di 220 per il modulo 3
(mi scuserete la notazione assai carente)
E funziona per n=1 (sic); per n=2 e per n=3.
Il teorema di induzione ridotta (detto anche di minima astuzia), mi faceva ben sperare, ma già con n=4 crollava miseramente...
A meno che, non sia necessaria un'astuzia (grande) nel disporre le "matrici" delle configurazioni....
Cosa che, al momento, non sono in grado.
E' una strada percorribile? Vale la pena continuare?
Salmastro

[ulisse]

Prova a risolvere questa variante.
Dovrebbe illuminarti.

Il direttore di un carcere ogni giorno si reca nel braccio della morte e fa uscire i condannati mettendoli in fila in modo che ogni condannato veda la schiena di tutti i condannati davanti a sè.
Poi fa incollare sulla schiena di ogni condannato un numero (tutti diversi, tutti uguali, interi, decimali, non importa; basta che siano numeri) e propone il giochino secondo le regole già enunciate.

Chi indovina il proprio numero sopravvive gli altri... scossaaaaa!
Quale strategia garantisce la sopravvivenza a tutti i condannati tranne al primo (che, in questa variante, ha probabilità nulla di azzeccare il suo numero)?

[_L_]

[ulisse]

E il caso N = 2

[ulisse]

[Taifu]

[_L_]

[Taifu]