Correggere i nani

[moebius]

Posto questo problema trovato altrove, perchè sinceramente non riesco a trovare una soluzione generale per quanto mi sforzi... chi sa che non possiate aiutarmi. La storiellina era molto bella, ma io ve lo metto direttamente nella forma generale, per vari motivi...
Ci sono n nani, ciascuno con un cappello sulla testa, colorato con uno tra k colori possibili. C'è anche un n+1-esimo nano che avrà il ruolo di correttore. Questi n+1 nani devono accordarsi per una strategia che gli permetta di fare quanto segue.
Ognuno dei nani con il cappello sa solamente quanti cappelli ci sono di ogni colore oltre al suo.
Con tale informazione, scrive su un foglietto il proprio nome ed un colore e lo deposita in un contenitore, senza dire niente agli altri nani.
Quando tutti i nani hanno fatto ciò, il contenitore viene portato al nano correttore che non sa assolutamente niente di come erano disposti i cappelli sulle teste dei nani e che dovrà associare ad ogni nano il colore esatto del cappello che aveva in testa.
La domanda è: per quali valori di n e k esiste una tale strategia?

[Nonno Bassotto]

Posto questo problema

Sono troppo scarso in italiano per usare parole con la c o la q

[moebius]

E' una vaga allusione al fatto che non si capisce niente o cosa?

[Nonno Bassotto]

E' una vaga allusione al fatto che non si capisce niente o cosa?

No no, il problema si capisce benissimo, è scritto molto chiaramente

[julio14]

Vista la mia statura, mi sento direttamente interessato. Dalla mia bassezza, ho trovato una strategia che credo sia giusta (?) indipendentemente da n e k.
Prima di tutto, i nani si accordano associando ogni colore ad un numero m compreso tra 0 e k-1. Quando poi i nani vedono i capelli degli altri li "sommano" in base al numero associato al loro colore, e scriveranno come colore quello associato al numero cui è congrua la somma ottenuta modulo k. Il correttore può quindi sommare i colori di tutti i foglietti, ottenendo un numero r che sarà congruo mod k alla somma s di tutti i cappelli per k-1 (infatti ogni cappello è stato contato k-1 volte). Da questo numero è facile risalire al numero s a cui è congrua la la somma di tutti i cappelli: infatti per s=0 (uso = per le congruenze) r=0, s=1 r=k-1, s=2 r=2k-2.... Trovato s ormai è fatta: basta sottrarre il colore di ogni foglietto a s per trovare il colore del cappello del nano.

[MindFlyer]

Ognuno dei nani con il cappello sa solamente quanti cappelli ci sono di ogni colore oltre al suo.

Non sono sicuro di aver capito questa cosa. Per esempio, se ci sono 3 cappelli bianchi e 7 cappelli neri, ogni nano con un cappello nero sa che tra gli altri vi sono 3 cappelli bianchi e 6 cappelli neri? E' l'unica interpretazione che abbia dato che non renda il problema banalmente risolubile o banalmente insolubile.

[julio14]

Non sono sicuro di aver capito questa cosa. Per esempio, se ci sono 3 cappelli bianchi e 7 cappelli neri, ogni nano con un cappello nero sa che tra gli altri vi sono 3 cappelli bianchi e 6 cappelli neri?

Credo e spero di si, altrimenti la mia dimostrazione non ha senso!!!

[moebius]

Il correttore può quindi sommare i colori di tutti i foglietti, ottenendo un numero r che sarà congruo mod k alla somma s di tutti i cappelli per k-1 (infatti ogni cappello è stato contato k-1 volte).

Forse volevi dire n-1 invece di k-1... Infatti questo prova che se (n-1,k)=1 una strategia esiste... Putroppo n-1 non è sempe invertibile modulo k... Al momento la congettura è che tale strategia non esista se (n-1,k)!=1...

Edit: comunque l'interpretazione è quella giusta.

[julio14]

Forse volevi dire n-1 invece di k-1...

C***o.... non mi puoi smontare così in due parole!!! no, cmq è vero, mi ero confuso, in effetti era strano che valesse per tutti gli n e i k.

[moebius]

Idee?

[Marco]

Mmmm.... ha l'aria di essere un problema tosto, nel caso generale.

Ho studiato in particolare il caso con due colori (k=2, n dispari). Lì, di sicuro, ogni numero di nani dispari <49 non ammette strategia di correzione vincente.

Ho provato che non esiste strategia nei seguenti casi:

- n primo dispari
- n-1 = 2p, con p primo dispari
- n-1 potenza di 2
- n-1 della forma p(p-1), con p primo dispari.

Questi criteri permettono di scartare quasi tutti i dispari bassi (con eccezioni in corrispondenza di 25, 45, 49, ...). 25 e 45 si scartano, 49 non saprei ancora e lì mi sono fermato.

Inoltre sono certo che n = 4, k = 3 non ammette strategia di correzione, mentre ho il forte sospetto che n = 5, k = 4 sia correggibile, anche se non ho ancora la strategia in mano...

[moebius]

Ho provato che non esiste strategia nei seguenti casi:

- n primo dispari
- n-1 = 2p, con p primo dispari
- n-1 potenza di 2
- n-1 della forma p(p-1), con p primo dispari.

Scusa Marco, ma non ho capito... Questo sempre per il caso k=2 o in generale? Per quello che è stato detto (nei post precedenti) credo tu ti riferisca al caso k=2. Giusto?

Inoltre sono certo che n = 4, k = 3 non ammette strategia di correzione, mentre ho il forte sospetto che n = 5, k = 4 sia correggibile, anche se non ho ancora la strategia in mano...

Guarda io ai tempi avevo fatto un pò di simulazioni... Se la congettura è vera (e sarebbe bello che lo fosse perchè così la soluzione è bella ) per k=4 ed n=5 non ci dovrebbe essere correzione possibile. Però l'unica cosa a converma di ciò è che così la soluzione è bella

P.S. In ogni caso mi piacerebbe conoscere l'approccio usato, che visti i risultati potrebbe essere diverso da quello che abbiamo "sempre" usato noi, magari anche via mp se ti interessa discuterne...

[Marco]

Mah, l'idea è di sfruttare il numero di combinzazioni possibili.

Dimostro il caso n=3, k=2, a mò di esempio.

Tre nani, due colori le configurazioni possibili sono 8. Le risposte possibili sono parimenti 8, quindi se c'è una strategia vincente, deve assegnare una corrispondenza biunivoca tra le terne di risposte e le configurazioni.

Ogni nano può dare due risposte e ogni risposta individua un sottoinsieme di configurazioni a cui corrisponde. Se una risposta di un nano corrispondesse a meno di 4 configurazioni, la risposta contraria ne dovrebbe coprire almeno 5. Dato però che i restanti nani possono dare 4 risposte diverse, per il Principio dei Cassetti, ci sono almeno due configurazioni corrispondenti allo stesso set di risposte, e quindi il correttore, se si presentasse tale terna di risposte non sarebbe in grado di distinguere tra le configurazioni.

Ogni nano perciò può dare risposte che corrispondano esattamente a 4 configurazioni.

Ogni nano però è in possesso della seguente informazione:
- vedo due cappelli neri [2 configurazioni]
- vedo un cappello nero e uno bianco [4 configurazioni]
- vedo due cappelli bianchi [2 configurazioni]

Ne segue che l'unica possibile strategia di reazione è accordarsi con gli altri sul codificare con la sua risposta:
- vedo un cappello bianco e uno nero, ovvero,
- vedo due cappelli dello stesso colore

[il che, by the way, è esattamente la strategia della somma in un'altra riformulazione]

A questo punto è ovvio che il set di risposte non cambia se si inverte il colore di ogni cappello, e quindi il correttore non è in grado di distinguere tra la configurazione vera e la sua opposta. []

------------------------

Nel caso più generale k=2, n dispari, la stessa tecnica dimostra:

Lemma: Condizione necessaria affinché esista una strategia di correzione è che sia possibile spartire l'insieme
$ \left\{ \binom{n-1}{0}, \binom{n-1}{1}, \dots, \binom{n-1}{n-1} \right\} $
in due sottoinsiemi con la stessa somma, tali per cui
$ \binom{n-1}{0} $ e $ \binom{n-1}{n-1} $
stiano in parti diverse.

A questo punto, ti resta in mano un problema di Teoria dei Numeri. Con un po' di aritmetica modulare, si dimostrano i criteri del post precedente [n primo, ecc...] Ma da lì, a generalizzare a tutti i dispari, ce ne passa...

Inoltre, sfortuna premagna, la condizione è solamente necessaria. Ma non è affatto detto che, anche trovati i sottoinsiemi del Lemma, le informazioni contenute nei sottoinsiemi siano comunque in grado di fornire una strategia di correzione valida.

Con lo stesso trucco fai fuori anche k=3, n=4. In quel caso, devi spartire i coefficienti trinomiali della forma
$ \binom{3}{k_1, k_2, k_3} $
in tre parti dalla stessa somma [9]. Ma i tre coefficienti estremi
$ \binom{3}{3, 0, 0} $, $ \binom{3}{0, 3, 0} $, $ \binom{3}{0, 0, 3} $
devono per forza di cose capitare nella stessa parte, il che è male.

Con k=4, n=5, invece la spartizione potrebbe esistere.
Infatti esistono 35 coefficienti quadrinomiali corrispondenti:
$ \binom{4}{k_1, k_2, k_3, k_4} $

Di questi, ve ne sono:
- 4 che valgono 1
- 12 che valgono 4
- 6 che valgono 6
- 12 che valgono 12
- 1 che vale 24.

La somma fa la cosa giusta, che è $ 4^4 = 256 $ e dobbiamo spartirli in 4 parti con somma 64, in modo che gli "1" non siano tutti nella stessa parte.

E stavolta di tali partizioni ne esitono un fottìo, presempio:
1+1+4+4+6+6+6+6+6+24
1+1+4+4+6+12+12+12+12
4+4+4+4+12+12+12+12
4+4+4+4+12+12+12+12

Quindi, che ne so, un nano potrebbe avere una strategia di risposte fancy del tipo
"Se i cappelli bianchi + i cappelli neri sono 0, allora dico bianco,
se sono 1, allora dico nero
se sono 2, e i cappelli bianchi + i cappelli rossi sono pari, allora dico bianco
se sono 2, e i cappelli bianchi + i cappelli rossi sono dispari, allora dico rosso
se sono 3, allora dico verde
se sono 4, allora dico rosso"

[se fai il conto, questa corrisponde alla partizione scritta sopra]

Ora alzi la mano chi è in grado di dire o smentire che montando 5 (una per ogni nano) di queste o altre strategie di partizione non sia possibile distinguere effettivamente tutte le 1024 configurazioni...

[moebius]

Noi l'avevamo presa decisamente da un altro punto di vista...
La mia idea era stata quella di identificare una strategia, per il caso k=2, con una tabella nxn (o matrice chiamala come vuoi) in cui le righe rappresentano il numero del nano e le colonne il numero di cappelli di un colore fissato che vede da 0 a n-1.
A questo punto si tira fuori, ragionando sulla tabella, che per n dispari ci sono almeno due configurazioni che producono lo stesso set di risposte.
Il problema è che questa cosa si estende malissimo al caso k>2 (praticamente non si estende....)
Prova a pensarci, io provo a pensare alla tua visione e chi sa che mescolando le due non ne esca qualcosa di buono...
c u!

[Marco]

Ma allora, il caso k=2, n dispari è dimostrato o no?

Confesso di non aver capito. Fino a fare la tabella, ci arrivo. Poi però...

Chiariscimi questo:

A questo punto si tira fuori, ragionando sulla tabella, che per n dispari ci sono almeno due configurazioni che producono lo stesso set di risposte.

Perché la "ciccia" del metodo sta nascosta sotto quel "ragionando sulla tabella".