Simulazione 2015 3

[Rho33]

Ci sono $3$ scuole ed ognuna con $n$ studenti. Ogni studente ha esattamente $n+1$ amici complessivamente nelle altre due scuole. Dimostrare che si possono scegliere tre studenti, uno per scuola,in modo che si conoscano tutti.

[alex00]

Essendo il numero di amici per ogni studente pari a \(n+1\) ci sarà almeno un amico per ogni scuola. Quindi posso prendere uno studente ed essere sicuro che egli conosca altri \(2\) delle altre \(2\) scuole. Ora affinchè anche gli altri e due si conoscano si fa lo stesso ragionamento in quanto anche in questo caso abbiamo un amico (almeno) per ogni scuola. Sintetizzando tutti gli n studenti della prima scuola conoscono almeno \(1\) studente della seconda scuola e almeno \(1\) della terza. Ogni studente della seconda conosce almeno uno studente della prima e della terza. Infine ogni studente della terza conosce almeno uno della prima e della seconda. Quindi c'è almeno una terna in cui si conoscono tutti.

[Rho33]

Allora, se non sto sbagliando di grosso, la tua soluzione è abbastanza errata (il problema non è così semplice come potrebbe sembrare)! Cioè, chi ti assicura che la terna esista veramente ? Tu hai sostanzialmente completato le ipotesi: conoscere $n+1$ persone significa conoscere almeno una persona in ognuna delle altre due scuole, ma da ciò non segue affatto la tesi.

Un hint un po' pesante ( da guardare solo dopo averci pensato):

Testo nascosto:

Extremal principle

[carlotheboss]

La mia è un po' più lunga ma non è troppo difficile:

Testo nascosto:

palesemente ogni studente ha almeno un amico nelle altre due scuole. Prendiamo un tipo a caso della scuola 0 e supponiamo che conosca tutti gli $n$ studenti della scuola 1 e uno della scuola 2: quest'ultimo, avendo almeno un amico nella scuola 1, conosce per forza uno degli $n$ ragazzi che anche il primo conosce quindi ho il ciclo cercato. Ora supponiamo che se esiste uno studente della scuola 0 che conosce $n - a$ dalla scuola 1 e $a+1$ dalla 2 si formi sempre un ciclo e dimostriamo per induzione che allora anche se esiste uno studente che conosce $n - (a+1)$ da una parte e $a+2$ dall'altra si forma un ciclo: ora se tra gli amici del tipo esiste già un ciclo va bene, sennò considero uno degli $a+2$ studenti della scuola 2, che conosce $x$ studenti della scuola 1, con $1 \leq x \leq a+1$ e vedo che, qualunque sia $x$, se considero questo studente, egli conosce $x$ studenti da una parte e $n - (x-1)$ dall'altra, ma essendo $x-1 \leq a$ vale $n - (x-1) \geq n - a$ e quindi ricapito in una situazione in cui so che si forma un ciclo per ipotesi induttiva, dunque in ogni caso si forma il ciclo e ho dimostrato la tesi.
P.S: le scuole sono numerate per non creare confusione tra i vari $tipi$ e $studenti$, il problema è simmetrico chiaramente