OliForum Matematico

Sia n un intero maggiore o uguale a 2. Ci sono n persone in fila indiana, ognuna delle quali `e o un furfante
(e mente sempre) oppure un cavaliere (e dice sempre la verità). Ogni persona, eccetto la prima, indica una
delle persone davanti a lei e dichiara “Questa persona `e un furfante” oppure “Questa persona `e un cavaliere”.
Sapendo che ci sono strettamente pi`u furfanti che cavalieri, dimostrare che assistendo alle dichiarazioni `e
possibile determinare per ognuna delle persone se si tratta di un furfante o di un cavaliere.

Volevo chiedervi se la mia soluzione, diversa da quella ufficiale, vi sembra corretta e abbastanza rigorosa.

SOLUZIONE: Partendo dall'ultima persona della fila(quella che indica la penultima) ho 2 casi: o è cavaliere o è furfante. In ognuno di questi 2 casi potrò con certezza, sapendo la sua affermazione e il suo tipo, sapere con certezza di che tipo è la persona davanti a lui, e questo vale per ogni altra persona fino alla seconda che mi darà la possibilità di sapere di che tipo è la prima. A questo punto noto che le due possibili configurazioni(fissando il primo come furfante o come cavaliere) saranno simmetriche, infatti se una persona è cavaliere(o furfante) in una configurazione, questa sarà furfante(o cavaliere) nell'altra, perchè cambiando il tipo del primo, cambia la veridicità della sua affermazione, e quindi cambia il tipo del secondo, e cosi via. A questo punto ho 2 configurazione, nella prima ho m furfanti e n cavalieri, nella seconda m cavalieri e n furfanti, ma so che furfanti>cavalieri e quindi la corretta sarà quella con più furfanti.

Attenzione, "Ogni persona, eccetto la prima, indica una delle persone davanti a lei": non necessariamente è quella subito di fronte a lei! In particolare, l'ultima persona della fila non è affatto costretta ad indicare la penultima. Potresti provare a riscrivere la tua soluzione (magari in modo un po' più formale...) tenendo conto di questo fatto...

SOLUZIONE: Partendo dalla seconda persona della fila(che indicherà per forza la prima) ho 2 casi: o è cavaliere o è furfante. Prendendo per buono una qualunque di queste 2 possibilità, potrò con certezza, tramite la sua affermazione e il suo tipo, sapere di che tipo è la prima. Avrò a questo punto fissato sia il tipo della prima che della seconda.Andando a studiare la terza, so che indicherà o il primo o il secondo, ma io so già conosco già i loro tipi, e potrò quindi anche dedurre quello della terza. Generalizzando, partendo a ritroso dalla seconda persona e studiando la sua affermazione, arrivato alla persona k saprò già il tipo di ogni persona p, con 0<p<k e tramite la sua affermazione saprò di che tipo è la persona k. A questo punto noto che le due possibili configurazioni(fissando il primo come furfante o come cavaliere) sono simmetriche, infatti se una persona è cavaliere(o furfante) in una configurazione, questa sarà furfante(o cavaliere) nell'altra, perché cambiando il tipo della seconda persona, cambia la veridicità della sua affermazione, e quindi cambia il tipo del primo, ma a questo punto cambierà anche la veridicità del terzo e di tutti le altre persone. Ora ho 2 configurazioni, nella prima ho m furfanti e n cavalieri, nella seconda m cavalieri e n furfanti, ma so che furfanti>cavalieri e quindi la corretta sarà quella con più furfanti.