Esercizio di allenamento per le gare olimpioniche
Salve a tutti, ho preso questo esercizio da un libro "Dispense di matematica olimpionica" trovato sul web, es.1 pagina 11 per essere precisi:
"Ci sono \(\displaystyle n \) persone. Dimostrare che durante la festa almeno 2 persone hanno stretto lo stesso numero di mani."
Nel caso in cui si supponga che ciascuno ha stretto la mano solo una volta alla stessa persona, è abbastanza facile dimostrarlo. Sono partito per assurdo ammettendo che ciascuno ha stretto un numero di volte diverso la mano, numero che in questo caso va da \(\displaystyle 0 \) a \(\displaystyle n-1 \). Ora, poiché quello che l'ha stretta \(\displaystyle n-1 \) volte deve averla stretta a tutti gli \(\displaystyle n \) presenti tranne che a sé stesso, dovrebbe averla stretta anche a quello che l'ha stretta \(\displaystyle 0 \) volte, il che si contraddice.
Invece nel caso in cui si ammette la possibilità della stretta di mano più di una volta alla stessa persona ho provato a dimostrarlo però non mi convince molto la spiegazione che ho fornito...
Grazie mille e auguri di buon Natale e buone feste a tutti
"Ci sono \(\displaystyle n \) persone. Dimostrare che durante la festa almeno 2 persone hanno stretto lo stesso numero di mani."
Nel caso in cui si supponga che ciascuno ha stretto la mano solo una volta alla stessa persona, è abbastanza facile dimostrarlo. Sono partito per assurdo ammettendo che ciascuno ha stretto un numero di volte diverso la mano, numero che in questo caso va da \(\displaystyle 0 \) a \(\displaystyle n-1 \). Ora, poiché quello che l'ha stretta \(\displaystyle n-1 \) volte deve averla stretta a tutti gli \(\displaystyle n \) presenti tranne che a sé stesso, dovrebbe averla stretta anche a quello che l'ha stretta \(\displaystyle 0 \) volte, il che si contraddice.
Invece nel caso in cui si ammette la possibilità della stretta di mano più di una volta alla stessa persona ho provato a dimostrarlo però non mi convince molto la spiegazione che ho fornito...
Grazie mille e auguri di buon Natale e buone feste a tutti
Risposte
ma visto che la successione 0,1,....,n-1 è da escludere,ad ognuna delle n persone bisogna associare un numero appartenente all'insieme {1,2,..,n-1}
giocoforza si ottiene una funzione non iniettiva
giocoforza si ottiene una funzione non iniettiva
Se non ho capito male, questo è il ragionamento che funziona se si ammette al massimo una stretta alla stessa persona, ma se si considera che una persona può stringere più volte la mano alla stessa persona, l'insieme del numero delle strette di mano non è \(\displaystyle {1,2,...,n-1} \) perché l'\(\displaystyle n-esimo \) può averla anche stretta più volte di \(\displaystyle n-1 \) volte. Mi spiego. Sotto questa ipotesi è anche possibile che l'\(\displaystyle n-esimo \) l'abbia stretta \(\displaystyle 3 \) volte a tutti, oppure tre volte a tutti e a due persone \(\displaystyle 4 \) volte, ecc... Grazie mille
Dato un insieme di $n$ persone possiamo avere due casi:
I) Almeno una persona ha fatto $n-1$ "strette di mano"; in tal caso nessuna persona ha $0$ "strette di mano", quindi la gamma di possibili valori che può assumere la variabile "strette di mano" sarà da $1$ a $n-1$ e perciò per il "Pigeonhole's Principle" (che non so come si dica in italiano, sorry), avremo più persone che "strette di mano" (intese come possibili valori della variabile), ed in conclusione, almeno due persone avranno stretto lo stesso numero di mani.
II) Nessuna persona ha fatto $n-1$ "strette di mano"; la gamma di possibili valori che può assumere la variabile "strette di mano" sarà da $0$ a $n-2$; come prima, avremo più persone che "strette di mano" (intese come possibili valori della variabile), ed in conclusione, almeno due persone avranno stretto lo stesso numero di mani.
Cordialmente, Alex
P.S.: quello che ho scritto vale se $n>=2$ e se nessun ha stretto le mani più di una volta alla stessa persona; perciò sarebbe interessante se postassi il testo completo, per capire se ci sono altre condizioni.
I) Almeno una persona ha fatto $n-1$ "strette di mano"; in tal caso nessuna persona ha $0$ "strette di mano", quindi la gamma di possibili valori che può assumere la variabile "strette di mano" sarà da $1$ a $n-1$ e perciò per il "Pigeonhole's Principle" (che non so come si dica in italiano, sorry), avremo più persone che "strette di mano" (intese come possibili valori della variabile), ed in conclusione, almeno due persone avranno stretto lo stesso numero di mani.
II) Nessuna persona ha fatto $n-1$ "strette di mano"; la gamma di possibili valori che può assumere la variabile "strette di mano" sarà da $0$ a $n-2$; come prima, avremo più persone che "strette di mano" (intese come possibili valori della variabile), ed in conclusione, almeno due persone avranno stretto lo stesso numero di mani.
Cordialmente, Alex
P.S.: quello che ho scritto vale se $n>=2$ e se nessun ha stretto le mani più di una volta alla stessa persona; perciò sarebbe interessante se postassi il testo completo, per capire se ci sono altre condizioni.
grazie per la risposta
purtroppo il testo completo è questo, e non specificando se è ammesso o meno stringere più volte la mano alla stessa persona, volevo dimostrarlo anche in quel caso
purtroppo il testo completo è questo, e non specificando se è ammesso o meno stringere più volte la mano alla stessa persona, volevo dimostrarlo anche in quel caso
Scusa leggi qua:
Siamo in 4 (a,b,c,d). $a$ stringe 100 volte la mano a $b$, 50 volte a $c$ e 25 volte a $d$.
Totale
$a$ 175
$b$ 100
$c$ 50
$d$ 25
Credo che "massimo una stretta per coppia" sia un must
Siamo in 4 (a,b,c,d). $a$ stringe 100 volte la mano a $b$, 50 volte a $c$ e 25 volte a $d$.
Totale
$a$ 175
$b$ 100
$c$ 50
$d$ 25
Credo che "massimo una stretta per coppia" sia un must
esattamente
quindi per più di una stretta alla stessa persona non è vero
ok, grazie
quindi per più di una stretta alla stessa persona non è vero
ok, grazie
"Lcdg96":
"Ci sono \(\displaystyle n \) persone. Dimostrare che durante la festa almeno 2 persone hanno stretto lo stesso numero di mani."
Dice "lo stesso numero di mani", ogni mano è diversa da un altra se la persona è diversa, ma qui si contano le mani diverse strette.
è come se \(\displaystyle a \) stringe la mano a \(\displaystyle b \) 2 volte. Ad un certo punto arriva \(\displaystyle c \) e chiede ad \(\displaystyle a \) "quante mani hai stretto?". Una sola chiaramente.
è vero, cavolo, non l'avevo letto attentamente 
grazie
grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo