Ci sono tre scuole con esattamente n studenti ciascuna. Ogni studente di ogni scuola conosce almeno n+1 dei 2n studenti delle altre due scuole. Fai vedere che c\'e\' un gruppo di tre studenti (uno per scuola) in cui ognuno conosce gli altri due. La conoscenza e\' reciproca.
<BR>
<BR>
Conoscenza reciproca
Moderatore: tutor
Ohhh... me le ricordavo questo problema... Mi pareva che fosse stato postato...
<BR>Mi pare che in altre sedi siano state proposte soluzioni piuttosto complesse.
<BR>Eccone qua una abbastanza veloce.
<BR>
<BR>Siano A,B,C le scuole.
<BR>Sia Aldo l\'alunno che, fra i suoi n+1 conoscenti, ha il maggior numero di alunni appartenenti ad una stessa scuola. Sia r questo numero.
<BR>Aldo conosce r persone nella scuola A e (n+1)-r persone nella scuola B (n+1-r > 1, ovviamente). Poniamo che, in particolare, della scuola B conosca Giovanni.
<BR>Allora Giovanni deve conoscere almeno (n+1)-r persone della scuola A, altrimenti conoscerebbe almeno r+1 nella scuola di Aldo, assurdo.
<BR>Ma allora per il Pigeonhole Aldo e Giovanni, oltre a conoscersi, hanno almeno un conoscente in comune nella scuola A, poniamo Giacomo.
<BR>
<BR>
<BR>Abbiamo anche formato un trio di cabaret, ben più di quanto ci chiedeva la tesi del problema.
<BR>
<BR>Ciao<BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: lordgauss il 2002-07-14 18:52 ]</font>
<BR>Mi pare che in altre sedi siano state proposte soluzioni piuttosto complesse.
<BR>Eccone qua una abbastanza veloce.
<BR>
<BR>Siano A,B,C le scuole.
<BR>Sia Aldo l\'alunno che, fra i suoi n+1 conoscenti, ha il maggior numero di alunni appartenenti ad una stessa scuola. Sia r questo numero.
<BR>Aldo conosce r persone nella scuola A e (n+1)-r persone nella scuola B (n+1-r > 1, ovviamente). Poniamo che, in particolare, della scuola B conosca Giovanni.
<BR>Allora Giovanni deve conoscere almeno (n+1)-r persone della scuola A, altrimenti conoscerebbe almeno r+1 nella scuola di Aldo, assurdo.
<BR>Ma allora per il Pigeonhole Aldo e Giovanni, oltre a conoscersi, hanno almeno un conoscente in comune nella scuola A, poniamo Giacomo.
<BR>
<BR>
<BR>Abbiamo anche formato un trio di cabaret, ben più di quanto ci chiedeva la tesi del problema.
<BR>
<BR>Ciao<BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: lordgauss il 2002-07-14 18:52 ]</font>