Problema 21 della gara a squadre

Esercizi sulla verità delle proposizioni e problemi che non sembrano rientrare in nessun'altra categoria.

Problema 21 della gara a squadre

Messaggioda ercolete » 06/05/2013, 18:23

Nella fortezza vi sono ben 2013 guardie, e due tipi di guardie: ciascuna di esse o dice sempre la verità o mente sempre. Disposte le guardie in cerchio, possiamo solo sceglierne tre e chiedere a una delle tre se le altre due sono del suo stesso tipo–le risposte vengono date alla fine di tutte le domande. Qual è il minimo numero di domande necessario per stabilire con certezza per ognuna delle 2013 guardie di che tipo è?
ercolete
 
Messaggi: 12
Iscritto il: 24/04/2013, 9:09

Re: Problema 21 della gara a squadre

Messaggioda gabrimoros 1 » 10/08/2015, 13:41

Se la guardia a cui facciamo la domanda mente:

a)E dice SÌ abbiamo:
$\bullet$ che le altre due non mentono;
$\bullet$ che una delle due mente e l'altra no.

b)E dice NO abbiamo
$\bullet$ che le altre due mentono.

Se la guardia a cui facciamo la domanda non mente:

a)E dice SÌ abbiamo:
$\bullet$ che la seconda e la terza non mentono.

b)E dice NO abbiamo:
$\bullet$ che le altre due mentono;
$\bullet$ che una delle due mente e l'altra no.


A questo punto vediamo che con una domanda per ogni gruppo di tre guardie risulta certo se ogni guardia menta o meno, infatti:

1)(SÌ,SÌ,SÌ) tre guardie non mentono
2)(SÌ,SÌ,NO) due guardie mentono e una no
3)(SÌ,NO,NO) una guardia mente e due no
4)(NO,NO,NO) tre guardie mentono

$\Longrightarrow$ abbiamo una soluzione con $2013$ domande.

Ora dimostriamo che non ne sono possibili di meno:

Guardando questo caso (SÌ,NO,X) [in cui X è l'unica guardia delle 3 a cui non abbiamo fatto la domanda] notiamo che X può essere sia una guardia che mente che una che dice la verità, infatti se gli avessimo posto la domanda e lui avesse risposto SÌ sarebbe stato una guardia che mente e se avesse risposto NO sarebbe stato una guardia che dice la verità, quindi non possiamo sapere di che tipo sia X, allo stesso modo non possiamo sapere che tipo di guardia sia ciascuna guardia a cui non facciamo una domanda, quindi il minimo di domande totali è inequivocabilmente $2013$.

Scrivendo la soluzione mi son venuti molti dubbi, me la controllate/correggete? :D
gabrimoros 1
 
Messaggi: 47
Iscritto il: 05/03/2015, 21:26


Torna a Logica e Matematizzazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite