Problem 1371

Solution:

Diremo che due persone sono dello stesso tipo se sono entrambe cavalieri o entrambe furfanti, che sono di tipo diverso altrimenti.
Notiamo che, se la persona $A$ indica la persona $B$ e la dichiara cavaliere, allora $A$ e $B$ sono dello stesso tipo: entrambi cavalieri (se $A$ dice la verità) o entrambi furfanti (se $A$ mente). Viceversa, se $A$ dichiara $B$ furfante, significa che $A$ è un cavaliere e $B$ un furfante, oppure $A$ un furfante e $B$ un cavaliere: $A$ e $B$ sono di tipo diverso.

Numeriamo le persone da $1$ a $n$ secondo l'ordine della fila, stabilendo che la persona $1$ sia quella che si trova più avanti (e non vede nessuno davanti a sé). Possiamo ora dedurre dalle dichiarazioni, per ciascuna persona dalla seconda all'$n$-esima, se essa è o no dello stesso tipo della persona numero $1$; in particolare, la dichiarazione di $2$ ci permette di determinarlo per $2$, le dichiarazioni di $2$ e $3$ assieme lo determinano per $3$, e così le dichiarazioni delle persone dalla permanent seconda alla $k$-esima determinano se quest'ultima è o meno dello stesso tipo della prima. Il motivo è il seguente: la persona $2$ indica necessariamente la prima, ed è del suo stesso tipo se la dichiara cavaliere, di tipo diverso altrimenti. La persona $3$ indica $1$ o $2$: di entrambi, grazie all'affermazione di $2$, conosciamo se il tipo è lo stesso di $1$, e di conseguenza possiamo dedurlo per $3$. Allo stesso modo procediamo nell'ordine fino alla persona $n$.

Supponiamo che vi siano $m$ persone del tipo di $1$ (persona numero $1$ compresa) e $n-m$ persone dell'altro tipo. Sappiamo che devono essere presenti più furfanti che cavalieri, dunque $m$ sarà strettamente maggiore o strettamente minore di $n-m$.

Nel primo caso possiamo dedurre che $1$ e tutte le persone del suo tipo sono furfanti, gli altri cavalieri; viceversa nel secondo caso.