sabato 25 novembre 2017

Quesito con la Susi n. 946

Susi si ritrova, non si sa bene come, di fronte ad una cattedra dietro cui stanno sedute quattro persone — saranno i soliti amici di Gianni che si prestano ai suoi giochetti per fargli fare bella figura con la Susi.

Ognuno di loro ha di fronte una targa con su scritto il proprio nome.

«Io sono più alto di Giovanni», dice Marco.

«Io sono più basso di Simone», dice Giovanni.

«Giovanni è il più basso di noi quattro», aggiunge Simone.

Ed Elisa ricorda che non tutti gli amici di Gianni sono affidabili: «Solo uno di loro tre mente.»

Gianni, onde fugare ogni dubbio sull'affermazione dell'amica, ci tiene a precisare che Elisa è sempre sincera. Poi chiede a Susi se sa dire chi sia il più basso dei quattro amici.

Soluzione automatica

Le tre affermazioni sono:

  • Marco è più alto di Giovanni: h(Marco) > h(Giovanni) (f1)
  • Giovanni è più basso di Simone: h(Giovanni) < h(Simone) (f2)
  • Giovanni è il più basso dei quattro, ovvero non esiste nessuno degli altri tre che sia più basso di Giovanni (∄X | h(X) < h(Giovanni), X ∈ {Elisa, Marco, Simone}) (f3)

Procediamo come al solito in modo becero: codifichiamo le tre affermazioni e costruiamo tre diversi controlli, ogni volta negando una diversa affermazione (per simulare il bugiardo). Poi applichiamo questi controlli a tutte le possibili permutazioni dei quattro soggetti (immaginando che quello che si trova in prima posizione sia il più basso) e scriviamo la permutazione quando i controlli passano.

Una volta compilato ed eseguito il codice emette due righe:

Elisa Giovanni Marco Simone 
Elisa Giovanni Simone Marco

Non c'è nessun problema visto che Elisa è sempre in prima posizione, e quindi dei quattro amici il più basso è il soggetto che porta il nome di Elisa.

Il codice

Ne esiste anche un'altra versione in cui ho abusato un altro po' delle lambda e ho rimosso la necessità di passare il vector della permutazione dei nomi.1

Soluzione manuale

Se non è Simone il bugiardo, allora la risposta di Susi deve essere proprio Giovanni. Vediamo se è compatibile con il fatto che o l'affermazione di Marco o l'affermazione di Giovanni sono false. Marco dice di essere più alto di Giovanni, e questo è ovviamente vero visto che Giovanni è il più basso. Quindi il bugiardo deve essere proprio Giovanni; però Giovanni dice una cosa vera, cioè di essere più basso di Simone.

Quindi il bugiardo deve essere proprio Simone.

Visto che Simone mente, sappiamo per certo che il più basso non può essere Giovanni. Allo stesso tempo sappiamo che è vero che Marco è più alto di Giovanni ma è anche vero che Giovanni è più basso di Simone. Quindi il loro ordine relativo (altezze crescenti da sinistra a destra) deve essere uno di questi due:

G M S
G S M

Giovanni rimane il più basso tra Marco e Simone… Ma non può essere più basso anche di Elisa, altrimenti sarebbe il più basso e Simone direbbe la verità (ma sappiamo che non è possibile, essendo proprio lui il bugiardo). Perciò il più basso dei quattro deve essere proprio Elisa.


  1. Esiste std::not1 ma non esiste std::not0, a quanto pare. (Comunque sembra che dal C++17 siano stati marcati come obsoleti, per cui…) Perciò ho implementato not0. Senza l'argomento esplicito del vettore contenente le permutazioni, l'altezza di un soggetto viene espressa in modo più naturale come h(‧).

Nessun commento:

Posta un commento

Sii educato, costruisci con cura le frasi, rifletti prima di pubblicare, evita parolacce e offese dirette, non uscire dal tema, cerca di non omettere la punteggiatura, evita errori ortografici, rileggi quel che hai scritto.