Sinceri e bugiardi a volontà

[axpgn]

1)
Un viaggiatore è arrivato su un'isola, dove ogni residente o dice sempre la verità o mente sempre.
Cento isolani stavano in cerchio rivolti verso il centro ed ognuno di loro diceva al viaggiatore se il proprio vicino di destra fosse una persona sincera.
Basandosi su queste affermazioni, il viaggiatore fu in grado di stabilire quante volte gli avessero mentito.
Puoi fare lo stesso?

2)
Ti trovi su un'isola con $65$ abitanti.
Tu sai che $63$ abitanti sono persone sincere, che dicono sempre la verità, mentre gli altri due sono normali ovvero mentono o dicono la verità a piacere.
Tu hai la possibilità di fare un solo tipo di domanda cioè questa: "Tutte le persone su questa lista sono sincere?".
La domanda presuppone una lista, che puoi crearti personalmente anzi puoi crearti tutte le liste differenti che vuoi.
Puoi porre la domanda a qualsiasi isolano quante volte tu voglia.

Il tuo obiettivo è quello di individuare le due persone normali.
"The easy task" è ottenerlo con $30$ domande.
"The medium task" è ottenerlo con $14$ domande.
"The hard task" è immaginare se sia possibile ottenerlo con meno di $14$ domande.

3)
Ti trovi su un'isola con $999$ abitanti.
Il governatore dell'isola ti dice: "Ciascuno di noi o è una persona sincera che dice sempre la verità o è un bugiardo che mente sempre".
Tu giri per tutta l'isola facendo la stessa domanda ad ogni persona: "Quanti bugiardi ci sono sull'isola".
Le risposte sono le seguenti.
Prima persona, il governatore: "C'è almeno un bugiardo sull'isola".
Seconda persona: "Ci sono almeno due bugiardi sull'isola".
Continua in questo modo fino alla $999$-esima persona che dice: "Ci sono almeno $999$ bugiardi sull'isola".

Cosa puoi dire riguardo al numero dei bugiardi e dei sinceri sull'isola?


Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

1)

Sì, 50! Infatti ogni combinazione di risposta che ricevo la posso ottenere anche invertendo i ruoli, cioè rimpiazzando ogni onesto con un bugiardo e ogni bugiardo con un onesto ottengo le stesse identiche risposte, pertanto l'unico modo che ha di capire quante volte gli è stato mentito è che il numero di bugiardi sia uguale al numero di onesti.

2) Medium (che per me è stato più difficile della hard)

Alla medium:
Numero i 65 isolani da 1 a 65. Divido i 65 isolani in tre gruppi: gruppo A \([1,21] \), il gruppo B \( [22,43] \) e il gruppo C \( [44,65]\).

Possono succedere 2 scenari: lo scenario 1 \(S_1\) è che i due isolani bugiardi si trovano in due gruppi distinti, e lo scenario 2 \(S_2\) in cui i due bugiardi si trovano nello stesso gruppo.

Domanda 1 posta al isolano \(1\) con la lista che contiene il gruppo \(A\)
Domanda 2 posta al isolano \(22\) con la lista che contiene il gruppo \(B\)
Domanda 3 posta al isolano \(44\) con la lista che contiene il gruppo \(C\)


Caso 1:
Se ottengo come risposte un sì e due no accade soltanto se ci troviamo nello scenario \(S_1\) e tutti e tre gli isolani sono onesti. Ne scelgo uno a caso di questi e poi nei due gruppi distinti in cui si trovano i due bugiardi (quelli in cui mi hanno detto no) - con al più \(5\) domande per gruppo - gli individuo facilmente. Totale domanda in questo caso: 3+5+5=13.

Caso 2:
Se ottengo come risposte un no e due sì allora ci troviamo nello scenario \(S_2\) e tutti coloro che mi hanno risposto dicono il vero, in particolare anche colui che mi ha detto no. Oppure ci troviamo nello scenario \(S_1\) e chi mi ha detto no dice sicuramente il vero. Wlog diciamo che l'isolano 1 mi ha riposto di no allora dice il vero. A questo punto domando (la quarta domanda)al 1 (cioè colui che dice il vero) con la lista B+C e qui capisco se mi trovo in \(S_2\) o in \(S_1\) a dipendenza di cosa mi risponde.

Se dice no allora siamo nel caso \(S_1\) quindi vado a domandare

Quindi
Domanda 5 posta al isolano \(23\) con la lista che contiene il gruppo \(B\)
domanda 6 posta al isolano \(45\) con la lista che contiene il gruppo \(C\)

A questo punto chi cambia risposta so che quello che aveva risposto prima era bugiardo. E poi mi bastano 5 domande per capire chi è il bugiardo nel gruppo A. Totale domande \(6+5=11\).

Se invece alla quarta domanda siamo nel caso \(S_2\) con al più 5+5 domande fatte nel gruppo A capisco chi sono i due bugiardi. Pertanto abbiamo totale domande \(4+5+5=14 \).

Caso 3:
Ottengo come risposta 3 sì allora potremmo avere che mi hanno risposto due falsi ed un vero e trovarci nello scenario \(S_1\) oppure che mi abbiano risposto due veri ed un falso e trovarci nello scenario \(S_2\). A questo punto basta domandare
Domanda 4 posta al isolano \(2\) con la lista che contiene il gruppo \(A\)
Domanda 5 posta al isolano \(23\) con la lista che contiene il gruppo \(B\)
domanda 6 posta al isolano \(45\) con la lista che contiene il gruppo \(C\)

Nel primo caso ottengo la risposta di tre veri. Dopodiché so già chi sono i falsi siccome erano coloro che avevano risposto si. Totale domande : \(3+3=6\).
Nel secondo caso - ovvero scenario \(S_2\) - sicuramente ottengo le risposte di due veri. Se ottengo la risposta da parte di 3 veri uno dirà no, capiamo in quale gruppo si trovano i falsi e con 5 domande trovo il bugiardo mancante (il primo era colui che aveva risposto sì alla domanda precedente sul suo gruppo).
Totale domande: \(3+3+5=11\)
Infine se ottengo ancora 3 sì, allora basta fare le domande:

Domanda 7 posta al isolano \(3\) con la lista che contiene il gruppo \(A\)
Domanda 8 posta al isolano \(24\) con la lista che contiene il gruppo \(B\)
domanda 9 posta al isolano \(46\) con la lista che contiene il gruppo \(C\)

a questo punto sicuramente mi rispondo 3 veri, e capisco quale degli isolani che mi hanno risposto in precedenza è un bugiardo. Totale domande: 9

2) Hard

Hard:

Sì! Numero gli isolani tra 1 e 65.
Domanda 1: Posta al 65-esimo isolano la domanda con tutta la lista: [1,65]
Se dice sì allora mente e mi bastano poi 6 domande, infatti so che l'altro si trova tra \(1\) e \(64\), \(2^6=64\). So che il 65-esimo isolano mente quindi mi basta fare il contrario.
Se dice di no allora dice il vero e quindi mi bastano 6+6 domande sempre tra \(1\) e \(64\). Totale \(1+6+6=13\)

Minimo: Con 12 domande

Sicuro un bugiardo è tra [1,64], quindi basta fare 6 domande individuare il primo bugiardo e poi sostituendo il 65 con il numero del primo bugiardo individuato qualora necessario ripetendo le 6 domande e trovare l'altro.

3)

Se fossero tutti bugiardi allora direbbero tutti il vero cosa non possibile pertanto c'è almeno un vero, quindi l'ultimo mente perché ci sono al più 998 bugiardi. Pertanto il primo sta dicendo la verità siccome l'ultimo è un falso. Il secondo dice il vero se e solo se c'è almeno un altro che mente, e questo implicherebbe che pure il penultimo mente. Se il penultimo dicesse la verità allora il secondo pure ma questo sarebbe assurdo! Pertanto il penultimo mente e dunque il secondo dice il vero. Così via e deduciamo che l'abitanti \(k \) dice il vero se e solo se l'abitante \(999-(k-1)\) mente. Ma questo è assurdo perché l'abitante \(500 \) deve dire sia la verità che mentire.
Il governatore non può nemmeno mentire sulla composizione degli abitanti perché se mentisse starebbe dicendo il vero affermando che c'è almeno un bugiardo. A meno che un terzo tipo di abitanti non possa sia dire il vero che anche mentire. E in tal caso non posso dire nulla perché sarebbero indistinguibili un sincero e un terzo tipo che dice il vero e/o un bugiardo e un terzo tipo che mente

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Correzione 2) hard task

Il minimo non è 12 ma 13, perché ho bisogno un bit per capire se chi mi risponde dice il vero o il falso e poi 12 bit per trovare i due bugiardi qualora il primo dica la verità

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Per 3)

Il mio ragionamento precedente è corretto ma credo la conclusione sia sbagliata! Infatti deduciamo dal mio precedente ragionamento che ci sono almeno 3 tipi di abotanti, se il governatore sta dicendo il falso alla prima domanda allora non potrebbero esserci veri. Quindi sono 999 abitanti di cui nessuno vero o falso. Se il governatore stesse dicendo il vero c'è almeno un bugiardo. Credo ma non ho troppo tempo ora che si possa dimostrare che numero di veri = numero di falsi, ma che non si possa determinare questo numero

[axpgn]

La 2) me la devo leggere (e rileggere ) con calma poi ti dirò (io ho usato un altro metodo, senza averlo ancora verificato dettagliatamente, quindi non so se ho risolto solo il medium o anche l'hard )

Per la 1)

Per la 3) anche

Non ho le soluzioni comunque per la 3) penso semplicemente che sia un'isola "normale" ovvero il governatore mente quando dice che ci sono solo sinceri o bugiardi e poi potrebbe mentire anche dopo così come tutti gli altri ma ciò non dimostra che lui o gli altri siano dei bugiardi (che vale anche per l'ultimo, il quale mente di sicuro ma non sappiamo se sia bugiardo oppure no )

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Per la 2) medium task posso aggiungere dettagli se preferisci.

[/spoiler]

Per la 2) hard task è semplice:
[spoiler]Chiedo al 65-esimo (solo perché mi piace di più così ma posso chiedere a chiunque altro)


Domanda 1: Lista che contiene tutti dal \(1\) al \(65\), quindi so che il vero mi risponde di no alla domanda "tutte le persone su questa lista sono sincere?" e il falso risponde si. Un bit per capire se dice il vero o il falso il mio interlocutore

Caso 1: Il 65 esimo dice il vero
Mi risponde no e so che i due bugiardi sono tra \(1\) e \(64\)

Faccio le seguenti liste:

Domanda 2: Lista che contiene tutti dal \(1\) al \(32\). Se risponde sì sono entrambi tra \(33\) e \(64\). Se risponde no almeno uno è tra \(1\) e \(32\).
Domanda 3: Se alla due ha risposto no domando con la lista \(1\) a \(16\). Altrimenti con la lista da \(33\) a \(48\). E così via
Domanda 4: Con la lista da \(1\) a \(8\) oppure con la lista da \(17\) a \(24\). Nell'altro caso \(33\) a \(40 \) oppure da \(49\) a \(56\).
Domanda 5: Con la lista da \( 1\) a \(4 \), etc.
Domanda 6: Con la lista da \(1\) a \(2\), etc.
Domanda 7: Con la lista \(1\), etc.


Ora ho individuato un bugiardo, wlog il numero \(1\). Mi basta ripetere la stessa strategia delle domande 2,3,4,5,6,7 solo che escludo da tutte le lista che lo contengono il numero \(1\). Totale domande \(13\)!

Caso 2: Il 65 esimo dice il falso.

In questo caso abbiamo già individuato un bugiardo. A questo punto adotto la stessa strategia delle domande 2,3,4,5,6,7 del caso 1, solo che faccio il contrario di prima e individuo anche l'altro in sole \(7\) domande!
Per contrario intendo dire che siccome mente se risponde si vuol dire che mente e quindi la risposta sarebbe stata no. Quindi

Domanda 2: Lista che contiene tutti dal \(1\) al \(32\). Se risponde sì è tra \(1\) e \(32\). Se risponde no è tra \(33\) e \(64\).
Domanda 3: Se alla due ha risposto si domando con la lista \(1\) a \(16\). Altrimenti con la lista da \(33\) a \(48\). E così via

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

2) Spiegazione di Medium task

Siccome ho diviso i 65 isolani in 3 gruppi, il gruppi \([1,22],[22,43],[44,65]\), che chiamerò rispettivamente \(A,B,C\). I bugiardi sono 2, per cui sicuramente ho un gruppo che contiene solo persone sincere. I bugiardi potrebbe capitare che gli ho divisi nello scenario \(S_1\) (in due gruppi distinti) o nello scenario \(S_2\) (entrambi nello stesso gruppo).

Nelle prime 3 domande quando se la lista contiene un gruppo soltanto, ad esempio il gruppo \(A\), faccio la domanda a qualcuno del gruppo \(A\). In questo modo uno vero dirà si o no in base al fatto se in quel gruppo c'è un bugiardo oppure no. Se c'è almeno un bugiardo risponderà no alla domanda: "Sono tutti sinceri?" mentre se non c'è nessun bugiardo mi risponderà sì! Un falso, per contro, siccome è presente nel gruppo, quindi sulla lista c'è almeno un bugiardo siccome la domanda è posta ad una persona che fa parte della lista presente in quel gruppo, mi dirà per forza di cose si mentendo.

Voglio capire in quale gruppo stanno i bugiardi: Quindi faccio le domande inserendo le liste \(A\), \(B\), \(C\) rispettivamente ad un membro \(a \in A\), \(b\in B\) e \(c \in C\).

Gli scenari possibili:
Scenario \(S_1\), diciamo per semplicità esplicativa che un bugiardo è nel gruppo \(B\) e un bugiardo è nel gruppo \(C\):

-Potrei beccarmi \(a,b,c\) tutti e tre veri e in questo caso mi diranno rispettivamente si,no,no. In questo caso capisco subito in quali gruppi si trovano i falsi, ovvero quelli corrispondenti alle persone che mi hanno detto no i quali dicono il vero (vedi sopra perché).
-Potrei beccarmi che \(a\) è vero e solo uno tra \(b,c\) è falso e in questo caso mi diranno rispettivamente si e in qualche ordine no,si. Il no per forza di cosa vuol dire che in quel gruppo c'è un bugiardo perché chi mi ha risposto dice il vero.
- Potrei beccarmi che \(a\) è vero e \(b,c\) sono entrambi falso. In questo caso ricevo come risposte si,si,si. Non capisco ne chi è falso ne in che gruppo si trovano. Ma so che mi ha risposto almeno un falso

Scenario \(S_2\), diciamo entrambi i bugiardi nel gruppo \(C\):
- Potrei beccarmi che \(a,b,c\) sono tutti e tre veri e in questo mi diranno si,si,no. Capisco che nel gruppo \(C\) c'è almeno un bugiardo e so chi mi dice il vero.
- Potrei beccarmi che \(a,b\) sono veri e \(c\) falso e in questo caso ottengo come risposte si,si,si. Non capisco nulla senonché mi ha risposto almeno un falso.

Un altra combinazione non è possibile!


Strategia per capire lo scenario siamo:

Affrontiamo i caso 1 e nel caso 2 con una strategia differente dal caso 3. Nei primi due casi infatti abbiamo già determinato almeno un gruppo in cui c'è un bugiardo. Dobbiamo capire lo scenario per capire se entrambi i bugiardi stanno nel gruppo già determinato oppure se c'è un altro bugiardo in un altro gruppo e in caso di risposta affermativa capire in quale gruppo. Inoltre nel caso 1 non c'è molto lavoro da fare, anzi nessuno, conosco già in base alla risposta, lo scenario e in quali due gruppi distinti si trovano i due bugiardi.

Caso 1:
Se ottengo come risposte si,no,no conosco automaticamente in quali gruppi stanno i bugiardi perché si trovano nel gruppo di chi mi ha risposto di no, poiché dice il vero, pertanto conosco anche in quale scenario siamo, i.e. \(S_1\).

Totale domande poste fin'ora: \(3\)

Caso 2:
Se ottengo come risposte si,si,no ho un indecisione tra scenario \(S_1\) e \(S_2\) ma sicuramente che chi ha detto no è vero. Mi basta una domanda per determinare in quale scenario sono. Diciamo che \(I =[1,65]\) è la lista con tutti gli isolani e che \(G \in \{A,B,C\}\) è il gruppo associato a chi mi ha detto no, che chiameremo \(g \in G \), in particolare \(g\) dice il vero e in \(G\) c'è almeno un falso. A questo punto domando a \(g\) con la lista \(I\setminus G\).

Caso 2.1:
Se mi dice di sì allora vuol dire che \( I \setminus G \) sono tutti sinceri e quindi siamo nel caso in cui entrambi i bugiardi sono in \(G\), ovvero nel caso \(S_2\).

Totale domande poste fin'ora: \(4\)

Caso 2.2:
Altrimenti se dice di no vuol dire che in \(G\) c'è un bugiardo e in \(I \setminus G \) un altro bugiardo. Quindi siamo nello scenario \(S_1\). Conosco un gruppo \(G\) e l'altro mi manca ma posso capirlo ponendo due domande soltanto.
Ora siano \(G_1,G_2 \in \{ A,B,C\} \) tale che \(G_1 \sqcup G_2 = I \setminus G \). Domandando a \(g_1 \in G_1 \) e rispettivamente a \(g_2 \in G_2\) - dove con \(g_1 ,g_2 \not\in \{a,b,c\} \) - le domande con la lista \(G_1 \) e rispettivamente \(G_2\). A questo punto so che siccome siamo nello scenario \(S_1\), un bugiardo si trova in \(G_1\) oppure in \(G_2\), e nel altro gruppo sono tutti sinceri. Quindi siccome prima avevo ricevuto due sì come risposta significa che uno dei due mi aveva mentito precedentemente. Siccome l'altro bugiardo si trova in \(G \neq G_1,G_2\) allora cambiando interlocutore rispetto alle prime 3 domande, e scegliendoli in \(I \setminus G\), è garantito che mi risponderanno due persone sincere. Per cui riceverò sicuramente come risposte sì, no in qualche ordine. Sì significa che in quel gruppo sono tutti sinceri e no che c'è un falso in quella lista.
Per cui scopro anche il restante gruppo contenete un bugiardo, e non solo capisco pure chi tra \( \{a,b,c\} \) è bugiardo, ovvero quello che sta nel gruppo \(G_j \), dove \(g_j \) è l'unico tra \(g_1,g_2\) ad avermi detto no, infatti nelle prime tre domande avrebbe dovuto rispondermi no invece mi aveva risposto sì.

Totale domande poste fin'ora: \(6\).

Abbiamo determinato lo scenario e i gruppi in tutti i casi. Per il caso 3 invece usiamo un approccio differente. Infatti in questo caso non sappiamo ne chi mi ha detto il vero, chi il falso, ne in quali gruppo ci sono i bugiardi, non sappiamo nemmeno lo scenario in cui ci troviamo. L'unica cosa che sappiamo è che ci ha risposto almeno un falso! Se ci ha risposto un solo falso allora ci troviamo nel caso \(S_2\) altrimenti se ci hanno risposto due falsi allora siamo nel caso \(S_1\). In questo caso scoprendo in quale scenari ci troviamo, scoviamo almeno un bugiardo se non addirittura entrambi.

Caso 3:

Se ottengo come risposta 3 si, ho un indecisione tra scenario \(S_1\) e \(S_2\) ma sicuramente cambiando interlocutore, i.e. \(a',b',c'\) e ponendo loro le stesse prime 3 domande, capisco in quale scenario siamo.

Caso 3.1:
Se ci trovassimo nello scenario 1 vuol dire che alle prime tre domande mi hanno risposto due falsi allora significa che \(a',b',c'\) saranno tutti veri e due di loro mi diranno "no" e capisco chi tra \(a,b,c\) è vero e chi falso e non devo porre ulteriori domande (avendo trovato tutti i bugiardi).
Totale domande caso 3.1: \(6\).

Alla luce di quanto detto deduciamo che se ottengo una qualunque altra combinazione di risposte differenti da questa ci troviamo nello scenario 2, ovvero due bugiardi nello stesso gruppo.

Caso 3.2:
Quindi se ottengo un solo no e due sì siamo nello scenario \(S_2\) e come prima chi ha detto no dice il vero e automaticamente conosco chi tra \(a,b,c\) mi ha detto il falso! Inoltre nel gruppo corrispondente a chi mi ha detto no c'è anche l'altro bugiardo.
Totale domande poste fin'ora: 6

Caso 3.3:
Come prima se ottengo tre sì siamo nello scenario \(S_2\), sicuramente ho già trovato chi erano i due bugiardi perché ho ottenuto due volte si,si,si! Due tra \(a,b,c\) dicono il vero, così come due tra \(a',b',c'\) dicono il vero poiché siamo in \(S_2\). Pertanto come prima cambiamo interlocutore ponendo le stesse tre domande ad \(a'',b'',c''\) otterrò sicuramente come risposta in qualche ordine si,no,no. Poiché è garantito che almeno uno tra \(a,a',a''\), almeno uno tra \(b,b',b''\) e almeno uno tra \(c,c',c''\) sia vero, capisco chi tra \(a,b,c,a',b',c'\) mi ha detto il falso e ho finito.

Totale domande caso 3.3: \(9\)


Fino ad ora abbiamo già risolto il problema solo nei casi 3.1 e3.3. Per capire i bugiardi restanti vediamo come procedere

Strategia per capire, dato un gruppo in cui si sa che contiene almeno un bugiardo, trovarlo:
Fino ad ora abbiamo capito in quali gruppi si trovano i due bugiardi e almeno l'identità di un isolano (se vero o falso)

Due gruppi sono formati da 22 elementi mentre un gruppo da 21. Entrambi i numeri sono più piccoli di \(32=2^5\) ma più grandi di \(2^4=16\). Quindi con \(5\) domande, anche se potrebbero essere sufficienti \(4\) domande, individuiamo sicuramente un bugiardo dimezzando con ogni domanda la lista delle possibilità.
Supponiamo che il gruppo sia \([1,21]\). Potremmo fare ad esempio la serie di domande

Domanda 1: con la lista \([1,10] \)
Domanda 2: con la lista [ \([1,5] \) ] oppure [ \([16,21] \) ]
Domanda 3: con la lista [ ( \([1,3] \) ) oppure ( \([6,8] \) ) ] oppure [ ( \([13,15] \) ) oppure ( \([19,21] \) ) ]
Domanda 4: e così via con range di numeri
Domanda 5: così via con range di numeri

Esempio: supponiamo che i bugiardi siano il \(1\) e il \(15\). E pongo le domande ad uno vero
Domanda 1: con la lista \([1,10] \) e mi dice di sì
Domanda 2: con la lista \( [1,5] \) e mi dice di sì
Domanda 3: con la lista \( [1,3] \) e mi dice di sì
Domanda 4: con la lista \( [1,2] \) e mi dice di sì
Domanda 5: con la lista \( 1 \) e mi dice di sì.
E so chi è il un bugiardo

Poi
Domanda 1: con la lista \([2,10] \) e mi dice di no
Domanda 2: con la lista \( [16,21] \) e mi dice di no
Domanda 3: con la lista \( [13,15] \) e mi dice di sì
Domanda 4: con la lista \( [13,14] \) e mi dice di no
E so chi è il un bugiardo.

Queste domande ci garantisce di trovare un bugiardo che vive in questo particolare gruppo. Inoltre queste domande funzionano siccome conosciamo l'identità di qualcuno, cioè se ci dice il vero o il falso, allora sappiamo sempre quale lista di numeri mettere! Qualora vi siano due bugiardi nello stesso gruppo, una volta individuato uno basta eliminarlo dalle liste se necessario e ripetere le 5 domande di cui sopra!

Totale domanda caso 1: \(3+10=13\)
Infatti dopo \(3\) domande sappiamo i due gruppi distinti in cui ci sono i due bugiardi e con \(5\) domande in un gruppo e \(5\) nel altro capiamo chi sono.

Totale domanda caso 2.1: \(4+10=14\)
Infatti dopo \(4\) domande ho scoperto che i due bugiardi vivono nello stesso gruppo e quindi dopo \(5+5\) poste nello stesso gruppo abbiamo che scopriamo chi sono i due bugiardi.

Totale domanda caso 2.2: \(6+5=11\)
In questo conosco già un bugiardo e conosco il gruppo in cui c'è l'altro bugiardo. Quindi mi bastano \(5\) domande per scoprire l'ultimo bugiardo.

Totale domande caso 3.1: \(6\). Già risolto!

Totale domanda caso 3.2: \(6+5=11\).
Siccome conosco già un bugiardo e conosco anche il gruppo in cui c'è l'altro bugiardo, come nel caso 2.2 mi bastano \(5\) domande per scoprire l'ultimo bugiardo.

Totale domande caso 3.3: \(9\). Già risolto!


Commento ulteriore:
Numerando in modo casuale gli abitanti da 1 a 65 vediamo inoltre che l'unico caso in cui necessitiamo di \(14\) domande è il caso 2.1, e questo caso si verifica quando siamo nello scenario \(S_2\) che ha circa \( 1/2\) di probabilità di verificarsi (in realtà non è esattamente \(1/2\) perché i gruppi non sono tutti con lo stesso numero di abitanti). Inoltre per far sì che siamo nel caso 2.1 dobbiamo avere che domandiamo a tre veri. Questo capita con \( \approx 20/22\) di probabilità (in realtà in un gruppo sarebbe \(19/21\)). Pertanto la probabilità che necessito \(14\) domande è circa
\[ \approx \frac{1}{2} \cdot \frac{20}{22} = \frac{5}{11} \approx 0.45\]

Ps: ho fatto approssimazioni molto brutali

[axpgn]

Ti ho detto che voglio pensarci con calma (non ho tempo ora) e tu mi triplichi la risposta

Comunque ... chi ha detto che puoi numerare gli isolani o ordinare le liste in qualche modo?

...
...
...
...
...
...
...
...
...
...
...


Non penso che serva a qualcosa numerarli o ordinarli in qualche modo (dovrei rifletterci ma mi pare proprio di no, io ne ho fatto a meno) ma non credo che il quesito originale lo vietasse: l'ho scritto solo perché tu mi hai vietato di far camminare i miei nanetti

Scherzo, ovviamente

Cordialmente, Alex

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Gli ho numerati per dargli un nome, puoi benissimo sostituire i numeri con i loro nomi di battesimo, ma diventava lunga spiegare la strategia

[axpgn]

Aspetta, aspetta, che forse ho trovato un inghippo per il 2.

C'era qualcosa che non mi tornava ma non capivo cosa: i due isolani che stiamo cercando non sono bugiardi ma normali quindi possono sia mentire che dire la verità e questo cambia le cose

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

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 [ot](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 [/ot]

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