2) Spiegazione di Medium task
Testo nascosto, fai click qui per vederlo
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
)
