Il ragionamento di bar simpson è sicuramente corretto. Vorrei proporne un altro che per noi informatici è un po' più immediato ed intuitivo e si basa sulla teoria dei grafi.
Possiamo rappresentare le nostre persone come vertici di un grafo non orientato $G = (V, E), E \subseteq V \times V$. I vari vertici li possiamo denotare con delle lettere maiuscole rappresentanti le iniziali dei nomi delle persone (in questo caso di fatto i nomi noti sono soltanto quelli di Alberto e Delia poiché Benito e Corinna da come abbiamo modo di capire hanno solo ascoltato il racconto di Delia).
Si ha dunque:
\[
V = \{A, B, C, D, E, F, G, H\}\\
\text{deg}(u) = \{0, 1, 2, 3, 4, 5, 6, x\}, u \in V, x = \text{deg}(D), \text{deg}(u) \leq 6 \text{ } \forall u \in V\]
Da notare che uno dei vertici sarà isolato (quello avente grado $0$) ergo senza nessun collegamento agli altri vertici. Inoltre dal fatto che ciascun persona stringe la mano al più una volta alle altre e mai al proprio coniuge ed a sé stesso risulta che ogni vertice non può avere grado superiore a $6$.
Ora per il lemma della stretta di mano deve risultare che $\sum_{u \in V} \text{deg}(u) = 2 |E|$. Questo fatto si può esprimere in un'altra maniera dicendo che in un grafo non orientato il numero di vertici con grado dispari deve essere pari (di fatto è un corollario del lemma precedente). Questa considerazione è molto importante per la nostra analisi poiché ci permette di affermare che $\text{deg}(D)$ sarà per forza dispari in quanto il numero di vertici con grado dispari diversi da $x$ è pari. Pertanto dobbiamo avere sicuramente $x = 1 \vee x = 3 \vee x = 5$. Vediamo quale di questi casi si può realmente verificare o meno:
- $x = 1$: questo vuol dire che nel grafo vi sono due vertici di grado $1$. In tal caso è possibile creare il vertice di grado $6$ ma "salta" poi di conseguenza quello di grado pari a $5$ (considerando che questi non potrà essere collegato né a sé stesso, né a quello che rappresenta il coniuge né agli appena determinati vertici aventi grado $6$ ed $1$). Tale valore per $x$ va dunque scartato;
- $x = 5$: una volta che collego $D$ a cinque altri vertici, poi scelgo un altro vertice e lo collego ad altri cinque (sempre tenendo presenti i nostri vincoli summenzionati). Successivamente devo scegliere il vertice che ha sei collegamenti. Tuttavia una volta effettuata questa scelta è evidente che non ho più il vertice isolato nel mio grafo e pertanto anche tale alternativa è da scartare.
L'unica possibilità è dunque che Delia abbia stretto la mano ad esattamente tre persone. Ora dobbiamo analizzare le affermazioni degli amici di Delia ed Alberto per "scovare" l'unica veritiera. Abbiamo dunque:
- "Corinna: No beh, in realtà conoscendo Alberto me lo immaginavo a stringere la mano a tutti."
L'affermazione è falsa poiché $\text{deg}(A) = 6$ implica che $\text{deg}(D) = 0$ (ergo l'unico vertice che potrebbe essere isolato è $D$) ma abbiamo visto prima come ciò non possa accadere; - "Delia: In effetti Alberto ricordi male, secondo me l'avevi stretta solo a due persone."
L'affermazione è falsa poiché considerando che $\text{deg}(A) = 2$ e $\text{deg}(D) = 3$ risulta che vi è un altro vertice diverso da $A$ e $D$ avente grado $3$ (e questo va bene) ma anche un altro (sempre diverso da $A$ e $D$) con grado $2$. Questo però non può accadere poiché tutti i vertici diversi da $D$ devono avere gradi diversi, come visto prima; - "Alberto: Se ricordo bene, quella sera strinsi quattro mani."
L'affermazione è falsa poiché considerando che $\text{deg}(A) = 4$ e $\text{deg}(D) = 3$ risulta che vi è un altro vertice diverso da $A$ e $D$ avente grado $3$ (e questo va bene) ma anche un altro (sempre diverso da $A$ e $D$) con grado $4$. Questo però non può accadere poiché tutti i vertici diversi da $D$ devono avere gradi diversi, come visto prima.
L'unica affermazione veritiera è dunque quella di Benito ed un grafo che permetta di rispettare tutti i vincoli stabiliti avente $\text{deg}(A) = 3$ e $\text{deg}(D) = 3$ può essere costruito. Pertanto Alberto ha stretto la mano esattamente a tre persone quella sera.
