Ancora cavalieri e furfanti a Cesenatico.

[Giovanni98]

Sia $n $ un intero maggiore o uguale a 2. Ci sono $n $ persone in fila indiana, ognuna delle quali o é un furfante (che mente sempre) o un cavaliere (che 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.

[Bucco]

Ci provo, però non sono nemmeno molto sicuro del metodo che sto utilizzando...

Testo nascosto:

Dimostro per induzione sul numero delle persone in fila [tex]n[/tex].
Verifico che se [tex]n=2[/tex] allora per i dati forniti dal testo ci saranno di sicuro 2 furfanti e 0 cavalieri; quindi qualunque cosa dicano sono assolutamente sicuro i stabilire di che tipo essi siano.
Quindi, a partire dalla base dell'induzione, prendo per vero che se ho [tex]n[/tex] personein fila sarò sempre in grado di stabilire di che tipo siano.
Adesso provo a dimostrare per [tex]n+1[/tex].
Se ho [tex]n+1[/tex] persone in fila, poiché posso stabilire di che tipo siano le prime [tex]n[/tex] persone della fila per ipotesi di induzione, posso stabilire di che tipo è l'ultima (la [tex]n+1[/tex]esima), in quanto se mente (dice che uno che sappiamo essere un cavaliere è un furfante o viceversa) è un furfante; se dice la verità (dice che uno che sappiamo essere un furfante è proprio un furfante o un cavaliere è un cavaliere) è un cavaliere.
E quindi essendo dimostrato per [tex]n+1[/tex] è dimostrato per [tex]n>=2[/tex].

Può andare come dimostrazione?

[Lasker]

Attento con il passo induttivo, non sempre tutte le ipotesi necessarie si verificano (controlla in particolare il fatto che ci siano strettamente più furfanti che cavalieri); diciamo che il problema non è così semplice come sembra.

[Bucco]

Ok, grazie mille, ero abbastanza certo che qualcosa non andasse bene, ma ci volevo provare comunque.

[Lasker]

Hai fatto bene a provarci! Comunque il problema non è proprio impossibile, se ci lavori ancora un po' ci arrivi di sicuro (inoltre ricordo che pure io mi ero incasinato con l'induzione, al primo tentativo su questo problema in una simulazione di cesenatico )

[xXStephXx]

Questo problema penso che lo ricorderò per sempre come quello che mi ha fatto esultare più di tutti Interpretandolo come "ognuno indica quello immediatamente davanti a sè" si prendevano miracolosamente $5$ punti inaspettatissimi xD