Sinceri e bugiardi a volontà

[3m0o]

https://www.youtube.com/watch?v=GCyMUQv8gLQ


... ma sei sicuro che non c'era scritto bugiardo prima?

[axpgn]

Non fare così, che si rompe

[axpgn]

Penso di aver trovato un modo per trovare in due normali con 13 domande ...

Premetto che sarò sintetico quindi se volete dettagli chiedete

Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.

(motivo: avevo scritto un papiro dettagliatissimo, pensavo di averlo postato ed invece ... puff ... non c'è più, sparito ovviamente nel frattempo avevo cancellato anche una copia di backup che avevo fatto ...
Spero di ricordare ancora tutto

Testo nascosto, fai click qui per vederlo

Scelgo 17 isolani, chiede ad un altro, fuori lista, per esempio Alfio se sono tutti sinceri. Dice "Sì"
Chiedo ad un altro fuori lista, diciamo Bruno. Anch'egli dice "Sì".
Allora i 17 sono tutti sinceri.
Faccio tre liste da 16 dei 48 rimanenti e chiedo ad uno dei 17.
I due normali o sono nella stessa lista o sono in due diverse; in quest'ultimo caso bastano 4 domande per ciascun gruppo da 16 (bisezione, dimezzamento o binary search ) per individuare i due normali; se sono nello stesso gruppo ne bastano meno.
In totale 13 domande

Supponiamo che Alfio dica "Sì" e Bruno invece dica "No": uno dei due è normale.
Allora prendo un terzo fuori lista, per esempio Carlo e gli chiedo se un quarto fuori lista, diciamo Dario, è sincero.
Se Carlo dice "Sì", Dario è sincero e quindi chiedo a Dario se Alfio è sincero, così stabilisco chi è sincero tra Alfio e Bruno.
Mi bastano le altre 9 domande per trovare l'altro normale tra gli altri 63.
Se Carlo dice "No" allora lui o Dario sono normali quindi tutti gli altri sono sinceri e bastano poche domande per stabilire chi sono i normali tra i 4.

Supponiamo che Alfio dica "No". Ne consegue che almeno uno tra Alfio e i suoi 17 è normale.
Faccio un'altra lista di 17 diversi dai sunnominati e chiedo a Carlo se questi 17 sono sinceri.
Se Carlo dice "Sì" sono sinceri e si prosegue come all'inizio (con i 48 rimanenti).
Se Carlo dice "No" allora almeno uno tra Carlo e i suoi 17 è normale.
Perciò gli altri 29 sono sinceri.
E undici domande sono sufficienti ad uno di questi sinceri per determinare i due normali tra i due gruppi da 18 (5 domande per gruppo al massimo sempre dimezzando)

Che ne dite?

Cordialmente, Alex