Ordinate per età e per altezza

[Fedecart]

Dimostrare che in ogni insieme di $ n^2+1 $ persone esiste un sottinsieme di $ n+1 $ persone che, una volta ordinate per statura, sono anche ordinate per età (crescente o decrescente).

Da un test di ammissione alla Galileiana.
Ho solo un idea vaga di come farlo, si vuole cimentare qualcuno?
(Se è nella sezione sbagliata spostatelo per cortesia!)

[Tibor Gallai]

E' uno dei più classici e noti problemi di Erdős, vedo che anche la Galileiana raschia il fondo del barile...

Ti linko solo la prima delle sue numerosissime apparizioni sul forum:
viewtopic.php?p=369

Comunque sì, è nella sezione sbagliata perché sarebbe Combinatoria.

[Anér]

Consideriamo questo ordinamento parziale sulle persone: date due persone dai nomi casuali come Alberto e Barbara, diciamo che Barbara è maggiore di Alberto se è più alta e più anziana di Alberto. Si vede facilmente che una catena è un insieme di persone che, in ordine crescente rispetto all'età, sono in ordine crescente anche rispetto all'altezza, mentre un'anticatena è un insieme di persone che, in ordine crescente rispetto all'altezza, sono in ordine decrescente rispetto all'età. Resta da dimostrare che in un insieme di n^2+1 elementi parzialmente ordinati esiste una catena oppure un'anticatena di lunghezza almeno n+1, e questo si fa considerando le anticatene dei minimali, dei "secondi" minimali (ovvero dei minimali dell'insieme privato dei veri minimali), dei terzi minimali (i minimali dell'insieme privato dei veri minimali e dei secondi minimali), e così via, e vedendo fino a che ordine di minimali si arriva se tutte le anticatene contano al massimo n elementi.
Generalizzando, possiamo dire che in un insieme di mn+1 persone ordinate crescentemente secondo l'altezza esiste una successione di m+1 persone in ordine crescente secondo l'età oppure una successione di n+1 persone in ordine decrescente secondo l'età.