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!).
Strette di mano tra pari
Strette di mano tra pari
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
Re: Strette di mano tra pari
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)
Re: Strette di mano tra pari
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.
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.
Re: Strette di mano tra pari
$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.
Re: Strette di mano tra pari
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:
$ \mathcal{L}=-\dfrac{1}{4}F^{ij}F_{ij}+\dfrac{1}{c}J^iA_i $