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]

[_L_]

[Taifu]

[Salmastro]

il perfido tiranno, inteneritosi, ha deciso di dare una possibilità a Primo (siamo nel caso di numeri qualsiasi scritti sulle spalle dei condannati) e gli fa svolgere un preliminare.
Così scrive su 10 foglietti (ovviamente adesivi) 10 numeri, fra loro diversi. Li mescola, li pone a faccia in giù, poi Primo li scopre uno alla volta e sospende quando ritiene che l'ultimo numero scoperto sia il maggiore della serie. Non può prenderne uno precedente e se si scoprono tutti i foglietti il numero scelto è l'ultimo.
Se Primo indovina, quelli saranno i dieci numeri attaccati sulle spalle dei condannati, lui compreso, altrimenti il maligno despota scarta il numero indicato da Primo, attacca gli altri nove agli altri nove sodali e a Primo ne attacca un ulteriore altro (reale qualsiasi, scelto a caso), ritornando in sostanza alla vecchia situazione di partenza.
Poichè Primo è persona onesta, per cui se sbaglia nel preliminare continuerà a seguire nel prosieguo la corretta strategia, ma, se invece nel preliminare ci azzecca, l'istinto di conservazione umanamente prevarrà, qual è la probabilità che i Nove si salvino?

Salmastro

[Taifu]

[Salmastro]

...già...MG la chiamava, anche, "il gioco del Googol".
Ma come diceva Ulisse, MG ha esplorato (quasi) tutti i possibili enigmi...
Per cui chi sa la risposta, come me e come te, perchè l'ha letta, dia solo dritte!
Salmastro
P.S.: l'uso del "Googol" (un 1 seguito da 100 zeri) risolve i tuoi "problemi" di spazio, legati alla finitezza dei foglietti

[Taifu]

[Salmastro]

in che senso?

Salmastro

P.S.: in una delle due opzioni hai comunque ragione.

[Taifu]

[Salmastro]

geniale! perchè, giustamente, Secondo farebbe le veci di Primo, se questo superasse il preliminare.
Il problema, e qui è l'ulteriore malizia del despota, sta nel fatto che l'esito del preliminare è ignoto ai Nove! (prego i forumisti di considerare tale precisazione parte integrante del quesito)

Comunque, Taifu meglio di un hacker!

Salmastro

[ulisse]