Chi trova un amico lo ordini secondo larghezza

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Chi trova un amico lo ordini secondo larghezza

Messaggio da kalu »

Ho $n^2+1$ amici di altezze e larghezze diverse. Dimostrare che posso sceglierne $n+1$ tali che, disposti in ordine di altezza, sono anche in ordine di larghezza (non importa se in modo crescente o decrescente).
Pota gnari!
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Chi trova un amico lo ordini secondo larghezza

Messaggio da <enigma> »

Un fatto che ogni olimpionico serio dovrebbe conoscere: http://en.wikipedia.org/wiki/Dilworth%27s_theorem!
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Rispondi