Dato che sarà la 4 o 5 volta che mi capita questo esercizio sotto varie forme (strette di mano ecc.)e stranamente non son riuscita a trovarlo sul forum lo ripropongo.
In un asilo ci sono $ 2n+1 $ bambini.Per ogni insieme $ B $ di
$ n $ bambini c'è almeno un bambino tra gli altri n+1 che conosce ogni bambino in $ B $.Mostrare che almeno un bambino conosce tutti gli altri.
[Si assume che se un bambino a conosce b allora necessariamente b conosce a ]
Conoscenze
Isolando un bambino quante configurazioni esistono, tali che si formino due insiemi di $ n $ bambini ciascuno? $ \displaystyle \binom{2n}{n} $
Il numero di insiemi del tipo $ B $ è $ \displaystyle \binom{2n+1}{n} $.
I bambini sono $ 2n+1 $. Quindi o a ciascun bambino è associato lo stesso numero di insiemi cioè $ \displaystyle \binom{2n}{n} $ oppure ne esiste almeno uno che ne ha più di $ \displaystyle \binom{2n}{n} $.
Nel primo caso tutti si conoscono, il secondo va anche bene, tanto a noi ne interessa uno solo.
Il numero di insiemi del tipo $ B $ è $ \displaystyle \binom{2n+1}{n} $.
I bambini sono $ 2n+1 $. Quindi o a ciascun bambino è associato lo stesso numero di insiemi cioè $ \displaystyle \binom{2n}{n} $ oppure ne esiste almeno uno che ne ha più di $ \displaystyle \binom{2n}{n} $.
Nel primo caso tutti si conoscono, il secondo va anche bene, tanto a noi ne interessa uno solo.
Eucla, perdonami ma non ho capito la tua soluzione (sono terribilmente arrugginito in combinatoria, me ne sono accorto con i problemi del Winter). Potresti rispiegare l'ultimo passaggio per favore? Da quel che ho capito io sembra che tu stia assumendo quest'identita': $ \displaystyle\binom{2n}{n}(2n+1)=\binom{2n+1}{n} $ (questo per farti vedere quanto poco ho capito la tua soluzione... 
)
thx
(comunque bell'avatar)
)thx
(comunque bell'avatar)
"Sei la Barbara della situazione!" (Tap)
Carino il problema!
La mia prima soluzione è ... quella (credo) di Eucla.
Ma visto che Piever mette i bastoni tra le ruote (ma come si fa... cosa vuoi che ne sappiano i bambini dell'asilo di binomiali?) e ci abbassa la stima a "esiste un bambino che conosce almeno 2 o 3 altri bambini", son stato costretto a cercarne un'altra...
Iniziamo costruendo induttivamente una n+1-clique (adoro sto termine, ma qualcuno sa come si pronuncia? come click?) così:
parto da un bambino A e ne aggiungo n-1 a caso. Così trovo un bambino B che li conosce tutti ed n, in particolare conosce A.
prendo A,B e ne aggiungo n-2 a caso. Trovo un bambino C che conosce A e B.
prendo A,B,C,... avete capito no?
Ora che ho una n+1-clique (cioè n+1 bambini che si conoscono), considero gli altri n e trovo un bambino Ù che conosce questi n. Inoltre Ù non appartiene a questi n, quindi appartiene alla clique e quindi conosce anche gli altri n che rimangono. Quindi Ù conosce tutti.
La mia prima soluzione è ... quella (credo) di Eucla.
Ma visto che Piever mette i bastoni tra le ruote (ma come si fa... cosa vuoi che ne sappiano i bambini dell'asilo di binomiali?) e ci abbassa la stima a "esiste un bambino che conosce almeno 2 o 3 altri bambini", son stato costretto a cercarne un'altra...
Iniziamo costruendo induttivamente una n+1-clique (adoro sto termine, ma qualcuno sa come si pronuncia? come click?) così:
parto da un bambino A e ne aggiungo n-1 a caso. Così trovo un bambino B che li conosce tutti ed n, in particolare conosce A.
prendo A,B e ne aggiungo n-2 a caso. Trovo un bambino C che conosce A e B.
prendo A,B,C,... avete capito no?
Ora che ho una n+1-clique (cioè n+1 bambini che si conoscono), considero gli altri n e trovo un bambino Ù che conosce questi n. Inoltre Ù non appartiene a questi n, quindi appartiene alla clique e quindi conosce anche gli altri n che rimangono. Quindi Ù conosce tutti.
