Per chi volesse diventare matto leggendo la vecchia soluzione:
Testo nascosto:
TESTO:
Un giornalista deve fare un articolo su una classica isola di furfanti e cavalieri, in cui tutti gli abitanti o mentono sempre (e sono furfanti) o dicono sempre la verità (e sono cavalieri) e tutti si conoscono reciprocamente. Supponiamo che il giornalista intervisti una e una sola volta tutti gli abitanti ed ottenga nell'ordine le seguenti risposte:
[tex]A_1[/tex]: “Sull'isola c'è almeno [tex]1[/tex] furfante.”.
[tex]A_2[/tex]: “Sull'isola ci sono almeno [tex]2[/tex] furfanti.”.
. . .
[tex]A_{n-1}[/tex]: “Sull'isola ci sono almeno [tex]n-1[/tex] furfanti.”.
[tex]A_n[/tex]: “Sull'isola ci sono [tex]n[/tex] furfanti.”.
Può il giornalista stabilire se sull'isola ci sono più furfanti o più cavalieri?
SOLUZIONE:
Per capire come funzionano le due notazioni, quella del testo e quella che ho impostato io, usate allo stesso tempo, ecco una breve legenda: [tex]A_g=A_{n_{n-g+1}}[/tex] nella mio sistema di notazione è uguale ad [tex]A_{n-g+1}[/tex] nella notazione del testo.
Sia [tex]k[/tex] il numero di furfanti.
Numero gli abitanti dell'isola in ordine inverso, cioè pongo [tex]A_m=A_{n-m+1}[/tex], inoltre ogni qualvolta venga indicato un [tex]A_{n_i}[/tex] indicherà [tex]A_i[/tex] secondo la notazione fornita dal problema, al fine di non confondere le due notazioni.
Se [tex]A_1[/tex] dicesse la verità dovrebbe essere un furfante e mentire, allora mente e [tex]k \le n-1[/tex].
Se [tex]A_2[/tex] dicesse la verità dovrebbero mentire tutti quegli [tex]A_{n_j}[/tex] prima di lui, ma se [tex]a \ge b[/tex] allora [tex]A_{n_a}[/tex] dice il vero implica [tex]A_{n_b}[/tex] dice il vero, dunque [tex]A_2[/tex] mente.
Supponendo di essere arrivati a un punto sufficientemente avanzato fino al quale questo ragionamento funziona, diciamo la metà, distinguiamo due casi:
a) [tex]n=2x, m=x[/tex] con [tex]x[/tex] intero positivo, cioè devo controllare la veridicità della parola di [tex]A_m[/tex].
So che [tex]A_{m-1}=A_{x-1}[/tex], che affermava l'esistenza di almeno [tex]n-(m-1)+1=2x-(x-1)+1=x+2[/tex] furfanti, mentiva, cioè [tex]k \le x+1[/tex].
[tex]A_m[/tex] afferma [tex]k \ge n-m+1=2x-x+1=x+1[/tex], ma allora se dicesse la verità ci dovrebbe essere qualche [tex]A_{n_h}[/tex] prima di lui che mente, che come detto prima è impossibile.
Allora [tex]A_m=A_x[/tex] mente, abbiamo [tex]x[/tex] furfanti e [tex]x[/tex] abitanti e, considerando tutte le affermazioni di chi non abbiamo ancora controllato, e cioè basta considerare solo quella di [tex]A_{m+1}=A_{n_x}[/tex] che afferma [tex]k \ge x[/tex], notiamo che in effetti al momento è vero perciò rende tutte le altre vere. Se uno solo di loro mentisse, avremmo [tex]x+1[/tex] furfanti e tutte le frasi di chi non abbiamo ancora controllato vere, anche quella del presunto furfante, perciò non è possibile e dobbiamo interrompere qui il nostro ragionamento: i cavalieri sono tanti quanti i furfanti.
b) [tex]n=2x+1[/tex] e [tex]m=x[/tex] con [tex]x[/tex] intero, come sopra devo controllare la veridicità della parola di [tex]A_m[/tex].
Vale di nuovo la falsità di [tex]k \ge n-(m-1)+1=2x+1-(x-1)+1=x+3[/tex], cioè [tex]k \ge x+2[/tex].
[tex]A_m[/tex] afferma [tex]k \ge n-m+1=2x+1-x+1=x+2[/tex], ma io so che quegli [tex]x-1[/tex] che ho controllato mentono, perciò ci devono essere ben [tex]x+2-(x-1)=3[/tex] abitanti dell'isola [tex]A_{n_h} < A_{n_{x+2}}[/tex] che mentono, che abbiamo ormai capito che non ha senso! Allora [tex]A_m[/tex] mente.
Provo [tex]A_{m+1}=A_{x+1}[/tex].
Sempre con i soliti ragionamenti ho falso [tex]k \ge n-m+1=2x+1-x+1=x+2[/tex], di nuovo [tex]k \ge x+1[/tex].
Ma questo abitante afferma [tex]k \ge n-(m+1)+1=n-m=2x+1-(x+1)+1=x+1[/tex].
Vedo cosa succede se [tex]k=x+1[/tex]:
so già che almeno [tex]x[/tex] abitanti dell'isola mentono e ho supposto che [tex]A_{n_{x+1}}[/tex] dice il vero, quindi mente qualcuno di quelli che devo ancora controllare, ma è impossibile, perciò [tex]A_{m+1}[/tex] mente.
Ma ora ho [tex]x[/tex] furfanti, perciò [tex]A_{m+1}[/tex] dice la verità.
Sono giunto a un paradosso: non posso tornare indietro poiché è da lì che sono partito, e se vado più avanti ho contraddizioni sempre maggiori e banalmente ovvie che seguono da questa.
Ne deriva che [tex]n[/tex] non può essere dispari e da quanto detto sopra i furfanti sono uguali ai cavalieri, ed è quello che il giornalista può concludere, come richiesto.