I 7 nani e la strega cattiva

doppiaGGi · Inviato: Ven Mar 23, 2007 10:26 am Oggetto:

Ok e' rimasto fermopertroppo tempo ecco la mia soluzione per due colori:

Innanzitutto matematizziamo un po' il problema.
al posto del colore dei cappelli ci mettiamo un numero che va da 0 a k-1 (dove k è il numero di colori).
Quindi nel caso di due colori parlero' d'ora in poi solo in termini di 0 o 1 (a volte parlero di cappello che c'e' -1- o cappello che non c'e' -0-)

In secondo luogo bisogna trovare un modo per rappresentare una strategia.

Noi(e questa e' un'idea di Ipazia) abbiamo scelto di rappresentarla con una matrice le cui colonne rappresentano gli n nani e le righe(numerate da 0 a n-1) il numero di cappeli (diciamo rossi, indicati con 1) che i nani vedono. Gli elementi della matrice saranno 0 o 1. In particolare l'elemento ai,j corrisponderà alla risposta che il j-mo nano darà ogni qual volta vedrà i cappelli col numero 1.

In questo senso la strategia usata per il caso in cui i nani sono in numero pari sarà una matrice del tipo

|1 2 3 4 5 6 7 8 <- nani
0 |0 0 0 0 0 0 0 0
1 |1 1 1 1 1 1 1 1
2 |0 0 0 0 0 0 0 0
3 |1 1 1 1 1 1 1 1
4 |0 0 0 0 0 0 0 0
5 |1 1 1 1 1 1 1 1
6 |0 0 0 0 0 0 0 0
7 |1 1 1 1 1 1 1 1
^
| numero di cappelli(col colore 1) visti

Oss. La matrice precedente non va bene nel caso dispari perche' la prima ed ultima riga coinciderebbero e quindi i nani darebbero la stessa risposta (tutti 0) sia nel caso in cui i cappelli siano tutti 0 sia nel caso in cui i cappelli siano tutti 1.

Ora si tratta di dimostrare che non esiste una matrice siffatta che sia injettiva.

Supponiamo ora n(numero dei nani)=2k+1 con k>1 (il caso particolare con n=3 si puo' risolvere manualmente)

senza ledere la generalità posso scegliere che una riga sia formata da tutti zeri (se compare un uno basta invertire gli zeri e gli uni di tutta la colonna).

Scegliamo che la riga k sia formata da tutti zeri.

Come risponderanno i nani nel caso siano disposti sulle loro teste k cappelli con 1?

k nani sceglieranno (che hanno il cappelo con l'1) vedranno k-1 cappelli (d'ora in poi per comodita con vedono n cappelli intendo che vedono n cappelli con l'1, quelli con lo 0 nonli considero) e sceglieranno la loro risposta dalla riga k-1. gli altri (k+1) la sceglieranno dalla k-esima riga.

Tutte le volte che avrò una configurazione di k cappelli dovro' scegliere k risposte dalla riga k-1 e k+1 risposte dalla k-esima riga.

Questo già mi induce a dire che la k-esima riga e la precdente non possono avere due "colonne" uguali:

(ex con n=9 => k=4)
3| 111011101
4| 000000000
non andrebbe bene perché potrei scegliere
111011101
000000000 corrispondente al caso in cui i cappelli siano 111100000
oppure
111011101
000000000 corrispondente al caso in cui i cappelli siano 111000010

quindi la riga k-1 sarà formata da tutti 1 tranne al piu' uno 0: senza perdita di generalita (a meno di una permutazione dei nani) supponiamo che il numero indeterminato sia il primo della riga.

Ora considerando il caso in cui ci sono k+1 cappelli si possono dimostare in maniera analoga che:
1) se ho k+1 cappelli allora dovro' scegliere k+1 soluzioni dalla k-ma riga e k dalla riga k+1
2) questo implica che (analogamente a prima )la riga k+1 puo' avere solo un elemento uguale alla k (senza perdita di generalita o il primo o il secondo)

quindi la strategia deve essere necessariamente del tipo

(ex con n=13 => k=6)
.........................
4| ......................
5| x111111111111
6| 0000000000000
7| xx11111111111
8| .......................
.....................

In questa maniera pero' non riesco a distinguere
due configurazioni del tipo

5| x111111111111
6| 0000000000000
7| xx11111111111 corrispondente alla configurazione 0000000111111

da

5| x111111111111
6| 0000000000000
7| xx11111111111 corrispondente alla configurazione 1111111000000

Perche' dotto riceverebbe la stessa risposta: 0000000111111.

nel caso n=3 dovrei avere

0| x11
1| 000
2| xx1

ma anche qui non distinguerei le due configurazioni di cappelli date da 110 e 001.

Spero di essere stato abbastanza chiaro, purtroppo per mail non è semplicissimo esprimersi.
_________________
doppiaGGi Linguaccia

____________
"Il y a des esprits qui vont à l'erreur par toutes les vérités; il en est de plus heureux qui vont aux grandes vérités par toutes les erreurs"
J. Joubert

Ipazia · Inviato: Ven Mar 23, 2007 10:59 am Oggetto:

Trovo che questa soluzione sia molto bella... forse così per iscritto sembra molto più complicata di quello che è davvero. Quello che mi piace di questa soluzione è che era molto difficile da trovare (io per esempio non ci ho dormito per settimane), ma che una volta trovata è piuttosto semplice da capire, e non fa assolutamente uso di concetti o teoremi complicati, che sono alla portata di pochi. Insomma, con un po' di pazienza la si potrebbe spiegare anche ad un bambino! Temo che non ci sia niente di analogamente "semplice" per il caso con k colori, e forse è per questo che ho perso interesse al problema generale... Triste

ma non si sa mai!
_________________
Ciao!

.:Ipazia:.