OliForum Matematico

Babbo Natale si fa aiutare da un gran numero di elfi buoni, che dicono sempre la verità quando gli viene posta una domanda.
Il suo rivale nel tentativo di ostacolarlo riesce ad imbucare tra gli elfi di Babbo Natale un certo numero di elfi malvagi che possono mentire o dire la verità a loro piacimento (uno stesso elfo malvagio può anche essere sincero per alcune domande e mentire per altre).
Supponiamo che adesso il numero complessivo di elfi sia $n$ (buoni+malvagi) e che gli elfi malvagi infiltrati siano in numero $m$. (Ovviamente minore di $n$)
Babbo Natale, ad occhio, nota che gli elfi sono un po' troppi e decide di mandare un ispettore per selezionare gli elfi autentici.
Chiaramente l'ispettore vuole selezionare tutti e soli gli elfi autentici, per cui gli elfi malvagi possono essere rimossi solo se vengono sgamati tutti. Anche un solo elfo malvagio infiltrato può compromettere l'intero lavoro di Babbo Natale!
L'ispettore può fare domande di qualunque tipo a qualunque elfo.

Per quali valori di $m$ (in funzione di $n$) gli elfi malvagi possono trovare una strategia per non essere sgamati tutti?
Per quali valori di $m$ invece, l'ispettore riuscirà a trovare tutti gli elfi malvagi?


PS: si suppone che gli ispettori del Polo Nord siano pro, per cui se l'ispettore ha la possibilità di sgamare qualcuno in modo logico, ci riesce sicuramente!

PPS: ah dimenticavo di dire, che ovviamente Babbo Natale ricorda bene il numero di elfi autentici, quindi lo comunica all'ispettore che sarà subito in grado di capire quanti sono quelli in eccesso
(In alternativa, per giustificare un problema mal modificato ( ) si può anche suppore che l'ispettore grazie alla sua proaggine ha qualche illuminazione divina con cui capisce all'istante il numero di elfi corrotti (senza però saperli individuare)).

Che genere di domanda risposta possono esserci? si/no? quantitative? cos'hai fatto ieri alle tre del pomeriggio? Indicami gli elfi che pensi essere cattivi?
quali informazioni hanno gli elfi? possono parlare tra di loro dopo che l'investigatore ha fatto una domanda?

Haiperso non ci avevo proprio pensato... Facciamo che possono rispondere solo "si" o "no"
mentre il fatto di parlare fra loro non dovrebbe essere troppo influente e forse non è influente nemmeno il tipo di domanda/risposta purchè non porti a paradossi xD

Allora premetto che non sono sicuro di aver capitp il problema, comunque avevo pensato che se gli elfi buoni sono più degli elfi cattivi allora basta raggrupparli ogni volta in gruppi diversi di $ m-n $ elfi; a questo punto basta chiedere ad ogni elfo di ogni gruppo se in quel gruppo sono tutti buoni. L'unico caso in cui le risposte saranno tutte affermative sarà quello in cui gli elfi sono tutti buoni da cui la tesi però non so se si può dimostrare che nel caso contrario si salvano!

Forse $n-m$ xD
Comunque sì, funziona (A patto che chiarisci bene come mai l'insieme dove tutte le risposte sono affermativa è unico).
C'è un altro modo che in molti casi è più veloce ma va bene pure così.

Si può dimostrare anche che in caso contrario gli elfi malvagi possono trovare un modo per salvarsi.

Si naturalmente intendevo $ n-m $ comunque la risposta tutta affermativa è unica perchè in tutti questi gruppi c'è sempre un elfo buono e quindi questo risponderà $ si $ se e solo se saranno tutti buoni altrimenti ci sarà sempre almeno un $ no $!
Un hint per la seconda parte?

Ok, quindi in pratica quell'insieme è unico perchè gli elfi buoni sono $n-m$, quindi non ci possono essere due insiemi con solo elfi buoni (sarebbero lo stesso) e non ci può manco essere un insieme con solo elfi cattivi perchè altrimenti sarebbero più di metà. ($n-m > m$)

Per l'hint: hai già provato il caso in cui gli elfi buoni sono tanti quanti quelli cattivi?

Ci avevo ragionato un po' solo che non so come dirlo, per me se gli elfi malvagi si comportano in maniera "$ simmetrica $" a quelli buoni non dovrebbero farsi sgamare, ma una dimostrazione precisa non la so dare

LOL Ma allora era solo un problema di pignoleria!
Dai, ora a parte il rigore... è chiaro che se gli elfi cattivi sono tanti quanti quelli buoni e si comportano simmetricamente, non posso essere sgamati
Gli elfi malvagi rispondono a qualunque domanda come se loro fossero buoni e gli altri fossero cattivi (imitando esattamente i buoni ma in modo speculare).
Entrambi si comportano allo stesso identico modo ma specularmente, quindi al massimo l'ispettore vedrà due fazioni diverse che si scannano a vicenda ma non ha nessun elemento per distinguere i buoni dai cattivi.

Supponendo per assurdo che con una serie di domande a diversi elfi riesca a distinguere i buoni dai cattivi, allora facendo la stessa serie di domande ma invertendo le parti (cioè le domande che prima ha fatto ad una fazione le fa identiche all'altra fazione), allora lo stesso identico ragionamento con cui prima aveva distinto i buoni dai cattivi adesso lo porterà a dinstinguere i buoni dai cattivi ma in modo opposto rispetto a prima (visto che le domande e le risposte saranno dello stesso tipo), il che è assurdo.. (E accontentiamoci! )


Però resta il caso in cui i cattivi sono più dei buoni eh xD

Credo di esserci allora: nel caso $ m>n-m $ allora gli elfi malvagi possono ricondursi al caso $ m'=m-n $ comprtandosi $ m-n $ in maniera buona e gli altri cattiva! Una volta sgamati i "cattivissimi" il gioco è fatto

Ok va bene!