OliForum Matematico

Marco ha scritto:Ma allora, il caso k=2, n dispari è dimostrato o no?

Si. Da li in poi, molto poco...
Per la tabella ti do uno sketch spero comprensibile.
Ogni nano può rispondere 0 o 1. Se n è dispari esiste una riga "centrale" che puoi supporre formata da tutti 0. A questo punto, perchè non ci siano "collisioni", si vede che sulla colonna precedente alla centrale non possono esserci 0, tranne al più in una posizione. Analogamente sulla successiva non possono esserci più di due 0 (supponi n=2h+1 e vedi quello che succede per h e h+1 cappelli dello stesso tipo).
A questo punto però è facile vedere che ci sono almeno due configurazioni (l'una "opposta" all'altra) che producono la stessa risposta.
Si capisce?

Si capisce, ma non mi torna.

E siccome sono duro, provo a scrivere per benino il caso n=5.

C'è un "riga centrale", ma suppongo sia un lapis freudiano per "colonna centrale".

..0..
..0..
..0..
..0..
..0..

So far, so good.

Poi mi dici:

perchè non ci siano "collisioni", si vede che sulla colonna precedente alla centrale non possono esserci 0, tranne al più in una posizione.

Ecco, questo mi sfugge. Supponi sia

.10..
.10..
.10..
.00..
.00..

Quali sarebbero le collisioni presunte?

No io intendevo proprio riga... nelle colonne ci vanno i nani, nelle righe il numero di cappelli di un tipo che vedono. Due post fa avevo scritto il contrario, l'ho visto adesso, ma quando ho scritto l'ultimo post non ho riguardato il precendente convinto di aver usato questa notazione... sorry.
Così ti torna?

No. Allora, nani sulle colonne e numero di cappelli bianchi visti sulle righe.
Siccome ogni nano può eventualmente scambiare la propria codifica dei cappelli, diciamo wlog che ogni nano decide di rispondere "0" se vede esattamente due cappelli bianchi, ossia la matrice è Bene.

Ad un certo punto scrivevi

sulla colonna precedente alla centrale non possono esserci 0, tranne al più in una posizione.

Se qui "colonna" vuol dire proprio colonna (=il nano Mammolo), allora è falso. Quindi suppongo voglia dire "riga", quindi è la riga sopra la centrale, vale a dire la riga "vedo un cappello bianco". Situazione: Again: quali sono le collisioni?

Doh.. ho fatto un bordello allucinante con la notazione... vediamo di riprendersi.
Si colonna era riga. Se i cappelli sono bianchi e neri, le configurazioni:
NNBNB e NNBBN producono la stessa sequenza di risposte, indistinguibile per Dotto, il nano corettore

Got it!

So, wlog we can suppose we have four 1s in the second row. The same is true for the 4th row. At least three 1s must be in common between 2nd and 4th row, so wlog we can suppose: Now, it is easy to verify that WWBBB and BBWWW give the same answer string "11000", so are indistinguishable. Thus, the case n=5 k=2 is settled. []

Yep! Sorry for notation panic!
So now that 2 colors and odd dwarves is settled, have you got any idea on how to merge the two approaches to the problem....
I didn't think too much about that because of some exams and it's a lot of time that i don't mess with the problem, but main cases i'd like to develop are: prime colors (i hope it works iff colors $ \nmid $ dwarves) or even colors and odd dwarves (i hope it never works).
Do you think we have to talk in getto slang to find a solution?

Edit: fancy face added

Maybe it is easier if we switch back to Italian.

...

Ci ho lavorato su un altro po'. Se vedo bene, la tua idea si generalizza ogni qualvolta esiste una "riga centrale", ovvero al caso $ k | n-1 $, ma solo a patto che $ n $ sia abbastanza grande.

Intanto lo provo per $ n=13, k=3 $, giusto per far capire le cose.

Le "righe" restano righe. Le colonne, invece diventano a forma di simplesso (per k=3, un triangolo). Denoto le possibili righe (i.e., l'informazione in mano ad ogni nano), con le terne di naturali a somma $ 12 $, che chiamerò coordinata. La riga centrale è chiaramente $ (4, 4, 4) $ [= vedo 4 cappelli di ogni colore]

Dico che due righe sono adiacenti se le corrispondenti coordinate coincidono in tutte le posizioni, tranne due, in cui la differenza è $ \pm 1 $.

Vale il seguente:

Lemma: I set di risposte dei nani in due righe vicine possono coincidere al massimo per una sola risposta.

[generalizza il fatto che due righe consecutive possono avere solo un simbolo in comune]

Wlog, posso supporre che la riga centrale $ r_0 $ abbia come set di risposte solo "0".

Considero la riga $ r_1 = (5, 4, 3) $. Per il Lemma, ha almeno 12 simboli diversi da "0". Eventualmente cambiando la codifica dei nani, possiamo supporre abbia 12 "1".

Considero la riga $ r_2 = (5, 3, 4) $. Considero le risposte dei 12 nani che rispondono "1" a $ (5, 4, 3) $. Tra di essi, ce ne sono almeno 11 che non rispondono "0" (riga adiacente a $ r_0 $), e almeno 11 che non rispondono "1" (riga adiacente a $ r_1 $). Ne segue che ce ne sono almeno 10 che rispondono "2".

Stesso ragionamento con $ r_2' = (4, 5, 3) $ (adiacente a $ r_0 $ e $ r_1 $). Deve avere almeno 10 "2" in comune con i 12 "1" di $ r_1 $.

Considero ora $ r_1' = (3, 5 ,4) $ (ad. a $ r_0 $ e $ r_2' $). Considero i 10 nani che rispondono "2" ad $ r_2' $. Devono esserci almeno 9 risposte non "0" e 9 risposte non "2". Quindi deve avere almeno 8 "1" tra quei 10 nani.

Oh, ora ci siamo. Piglio 4 nani tra questi ultimi 8 e li coloro di verde. I nani verdi rispondono "1" a $ r_1 $ e ad $ r_1' $.

Considero i nani che rispondono "2" sia a $ r_2 $ che a $ r_2' $, ma che non ho colorato di verde. Dico che sono almeno 4. Infatti tali nani rispondono tutti "1" a $ r_1 $, quindi sono due insiemi con almeno 10 elementi, la cui unione ha alpiù 12 elementi. Ne segue che l'intersezione ha almeno 8 elementi, di cui al più 4 sono verdi. Coloro 4 di tali nani di violetto.

Infine i restanti 5 nani li coloro di celeste.

Se ai nani verdi metto cappelli del terzo colore, ai nani violetti cappelli del secondo colore e ai nani celesti cappelli del primo colore, ottengo risposte "1" dai nani verdi, "2" dai nani violetti "0" dai nani celesti.

Se invece metto ai verdi il primo colore, ai violetti il terzo e ai celesti il secondo, di nuovo ottengo risposte "1", "2" e "0" rispettivamente. Le due configurazioni di cappelli solo pertanto indistinguibili. []

La cosa funziona anche per tutti gli $ n=13 + 3h $, dato che l'intersezione finale risulta avere $ 8 + 3h $ elementi, mentre per colorare i nani ne bastano $ 8 + 2h $. Non escludo che rifacendo il ragionamento con altre adiacenze, si possa migliorare il 13.

Non dubito che lo stesso ragionamento si faccia in qualunque dimensione del simplesso di risposte, a patto che $ n \equiv 1 \pmod k $, e a patto di calcolare per benino l'$ n $ migliore per cui le intersezioni via via trovate sono abbastanza "grasse". Se vuoi divertirti a provarci...

Che in effetti è come dire che se n è abbastanza grande la dimostrazione si estende a tutti i primi (e oltre).
Il fatto è che quanto grande debba essere n dipende da p e comunque ci sono casi che vanno comunque controllati "by hand" ... e quindi non basta per concludere che vale per ogni p, perchè i casi da controllare "a mano" rimangono infiniti...
Per questo cercavo un'altra "visione" del problema, pechè ho paura che da questa si sia spremuto già il più possibile.

up