Strette di mano tra pari

[Lasker]

Ci sono $2n$ persone ad una festa, e si sa che ogni persona ha stretto la mano ad un numero pari di invitati. Dimostrare che esiste una coppia di invitati tale che, se consideriamo l'insieme $A$ delle persone alle quali entrambi hanno stretto la mano, la cardinalità di $A$ è pari.

NB= ovviamente non ci si può stringere la mano da soli (sarebbe piuttosto imbarazzante come cosa da fare ad una festa di gran classe!).

[RiccardoKelso]

Ad onta delle batoste che prendo ogni volta che appoggio i polpastrelli sulla tastiera, sono ancora qua a provarci! Autoesaltazioni (o commiserazioni) a parte: iniziamo col dire che tutti stringono la mano ad almeno 2 persone, altrimenti la dimostrazione finirebbe lì (considerando la cardinalità dell'insieme vuoto come pari). Ergo il signor G stringe la mano a K persone, con K pari. Inoltre, ognuno di questi K stringe la mano ad un numero dispari di componenti di questo gruppo K, in quanto in caso contrario colui che fa diversamente potrebbe essere preso in considerazione con il signor G e far finire la dimostrazione. Notiamo che qui le strette che ognuno fa sono in numero pari, tutto ok quindi. A questo punto prendiamo i "non K" (e nemmeno G ovviamente): ognuno di loro deve stringere la mano ad un numero dispari di persone appartenenti a K, per evitare di essere preso in considerazione con G e far finire lì la cosa. Tuttavia, così facendo, essendo i "non K" in numero dispari, almeno un K dovrebbe fare un numero dispari di strette di mano, il che è impossibile. Dovrebbe bastare, vado a prendere l'ombrello per gli insulti. (Che attendo ferventemente, sia chiaro)

[remat7]

RikkardoKelso il tuo ragionamento mi sembra abbastanza corretto anche se diciamo che potevi scriverlo un po' meglio, ma non ho capito la conclusione.
Provo a riscriverlo per vedere se ho capito e intanto aggiungo qualcosa che completa un po' quello che dici:
Osservazioni di base:
$ A. $Se qualcuno non ha stretto nessuna mano posso considerare la cardinalità dell'insieme vuoto pari e quindi il problema è risolto.
$ B. $Una cosa "divertente" da notare, ovvero che se qualcuno ha stretto la mano a tutti tranne che ad una persona, quindi a $ 2n - 2 $ persone, lui e quella persona rappresentano la soluzione del problema.
Ora diamo dei nomi alle persone, chiamandole con $ p_i $ con $ 1 \leq i \leq 2n $
_ La p-esima persona $ p_i $ ha stretto la mano a $ 2k $ persone con $ 2 \leq 2k \leq 2n - 4 $ per i punti $ A $ e $ B $
Nota: In questo gruppo ognuno ha stretto sicuramente la mano alla persona $ p_i $.
Chiamiamo $ G $ il gruppo delle $ 2k $ persone (senza $ p_i $), $ G $ contiene ovviamente un numero pari di persone.
Chiameremo $ G_1 $ il gruppo delle persone a cui $ p_i $ non ha stretto la mano, $ G_1 $ contiene un numero dispari di persone.
_Ogni membro di $ G $ ha stretto la mano ad un numero dispari di persone del gruppo $ G $, altrimenti la dimostrazione sarebbe finita.
_Segue che ogni membro di $ G $ deve aver stretto la mano ad un numero pari di membri del gruppo $ G_1 $, poichè ogni persona stringe la mano ad un numero pari di persone.
_I membri del gruppo $ G_1 $ devono aver stretto la mano ad un numero dispari di persone del gruppo $ G $, altrimenti la dimostrazione sarebbe finita.
_Segue che ogni membro del gruppo $ G_1 $ ha stretto la mano ad un numero dispari di membri del gruppo $ G_1 $, poichè nessuno di loro ha stretto la mano a $ p_i $
Ora? Non riesco a vedere l'assurdo di cui parli.
Secondo me per risolvere il problema basta fare qualche osservazione del tipo "teorema dei piccioni", ma a me personalmente non sono venute in mente.

[RiccardoKelso]

$G$ ha cardinalità pari e $G_1$ dispari; se ogni elemento di $G_1$ stringe la mano ad un numero dispari di elementi di $G$ allora il numero totale di strette tra questi insiemi è dispari. Per far sì che queste si distribuiscano tra gli elementi di $G$ almeno uno di loro deve stringere un numero totale di mani dispari.

[phyknight]

C'è una soluzione molto breve e elegante a questo problema che usa in modo elementare le matrici (sperando sia corretta e scritta nel modo più semplice possibile)

Testo nascosto:

Considero la matrice $ A=a_{ij} $ $ 2n\times2n $ tale che se il tizio $ i $ e il tizio $ j $ si stringono la mano allora $ a_{i,j}=1 $ e altrimenti $ 0 $ (d'ora in poi considero sempre le matrici con elementi modulo 2)
$ {}^\mathrm{t}A $ è la trasposta di $ A $
$ v $ è la matrice $ 1\times2n $ (oppure se volete il vettore) i cui elementi sono tutti $ 1 $
Ora, prendo il prodotto $ v(A{}^\mathrm{t}A)=(vA){}^\mathrm{t}A $
Supponiamo per assurdo che per tutte le coppie di persone il numero di tizi che ha stretto le mani a entrambi sia dispari, allora $ A{}^\mathrm{t}A $ è la matrice $ 2n\times2n $ con la diagonale tutti 0 e il resto 1, perché moltiplicare $ A $ per la trasposta significa che l'elemento $ ij $ della matrice prodotto è dato dal prodotto della riga $ i $$ \times $ riga $ j $ di $ A $ che da una somma di numeri che sono $ 0 $ se $ i $ e $ j $ non stringono la mano a un tizio e $ 1 $ se stringono la mano allo stesso tizio.
Ma per assurdo il numero di tizi che stringe la mano a ogni coppia è dispari, quindi modulo $ 2 $ tutti gli elementi della matrice prodotto sono $ 1 $ tranne la diagonale che ha tutti $ 0 $ perché sarebbe le righe di $ A $ al quadrato.
Allora $ v(A{}^\mathrm{t}A) $ è il vettore $ v $ perché in ogni colonna di $ A{}^\mathrm{t}A $ ci sono un numero dispari di uni.
Tuttavia, $ vA $ è la matrice $ 1\times2n $ nulla: ha tutti gli elementi $ 0 $ in quanto su ogni colonna di $ A $ ci sono un numero pari di uni (ogni persona stringe un numero pari di mani), e quindi $ (vA){}^\mathrm{t}A $ è ancora la matrice nulla $ 1\times2n $
Quindi, abbiamo dimostrato che la matrice riga $ (1,1,1,1,...,1) $ è uguale alla matrice $ (0,0,0,0,...,0) $, il che è assurdo