Pagina 1 di 1

Chi trova un amico lo ordini secondo larghezza

Inviato: 03 ago 2013, 21:15
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).

Re: Chi trova un amico lo ordini secondo larghezza

Inviato: 03 ago 2013, 21:37
da <enigma>
Un fatto che ogni olimpionico serio dovrebbe conoscere: http://en.wikipedia.org/wiki/Dilworth%27s_theorem!