Sia n un intero maggiore o uguale a 2. Ci sono n persone in fila indiana, ognuna delle quali è 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 è un furfante” oppure “Questa persona è un cavaliere”.
Sapendo che ci sono strettamente più furfanti che cavalieri, dimostrare che assistendo alle dichiarazioni è
possibile determinare per ognuna delle persone se si tratta di un furfante o di un cavaliere.
Fila di furfanti e cavalieri
Re: Fila di furfanti e cavalieri
Tutto sta nello "strettamente".
Innanzitutto osserviamo che tutti: o dicono un'affermazione o sono soggetti ad almeno un'affermazione (e questo equivale a dire che sono "determinabili", dopo aver stabilito se l'ultimo è cavaliere o furfante).
Come si procede per determinare se ognuno è "$C$" o "$F$"? Semplice, guardiamo come sono rispetto all'ultimo (appunto), stabilendo che una persona è concorde ad un'altra se la proposizione che li mette in relazione è "questo è un cavaliere" mentre sono discordi se la proposizione che li mette in relazione è "questo è un furfante". A questo punto se chiamo l'ultimo abitante di tipo $0$ e uno a lui discorde di tipo $1$ otterrò una sequenza di $0$ e di $1$ lunga $n$. Adesso è fatta! So che gli $0$ non possono essere tanti quanto sono gli $1$ ma necessariamente una delle due quantità è maggiore del' altra (per ipotesi, è lo "strettamente" che ci dice questo), quindi posso concludere che la quantità maggiore fra le due è furfante, e così facendo li posso identificare tutti.
Innanzitutto osserviamo che tutti: o dicono un'affermazione o sono soggetti ad almeno un'affermazione (e questo equivale a dire che sono "determinabili", dopo aver stabilito se l'ultimo è cavaliere o furfante).
Come si procede per determinare se ognuno è "$C$" o "$F$"? Semplice, guardiamo come sono rispetto all'ultimo (appunto), stabilendo che una persona è concorde ad un'altra se la proposizione che li mette in relazione è "questo è un cavaliere" mentre sono discordi se la proposizione che li mette in relazione è "questo è un furfante". A questo punto se chiamo l'ultimo abitante di tipo $0$ e uno a lui discorde di tipo $1$ otterrò una sequenza di $0$ e di $1$ lunga $n$. Adesso è fatta! So che gli $0$ non possono essere tanti quanto sono gli $1$ ma necessariamente una delle due quantità è maggiore del' altra (per ipotesi, è lo "strettamente" che ci dice questo), quindi posso concludere che la quantità maggiore fra le due è furfante, e così facendo li posso identificare tutti.