Galileiana 2007-2008/6

[pic88]

In un insieme di $ {n^2+1} $ persone ne esistono sempre $ {n+1} $ che, se ordinate per altezza, sono anche ordinate per età (crescente o decrescente).

[tiamat88]

io ho provato per induzione

n = 0

n = 1

n= 2

e poi mi sono fermato!!

tu?

ps: cavoli difficilissimo quest'anno il test di mate e fisica della galileiana nè??

[piever]

Se solo aveste seguito la lezione mia e di enomis di combinatoria

Comunque e' un problema decisamente bellino, proviamo a farlo in maniera buffa (in realta' esiste sicuramente una soluzione per induzione, ma voglio fare un po' il figo..).

Definiamo la relazione d'ordine a>b sulle persone. Diciamo che a>b se e solo se l'altezza di a e' maggiore o uguale all'altezza di b e l'eta' di a e' maggiore o uguale all'eta' di b. La tesi diventa: dato un insieme parzialmente ordinato con $ n^2+1 $ elementi esiste una catena di cardinalita' n+1 oppure un'anticatena di cardinalita' n+1.

Duale del teorema di Dilworth: ogni insieme parzialmente ordinato e' partizionabile in h anticatene, dove h (talvolta diverso da 7, chi ha orecchie per intendere faccia finta di niente) e' la cardinalita' della piu' lunga catena.

Corollario di Dilworth: sia H la piu' grande catena e W la piu' grande anticatena di un insieme S, allora $ |H|\cdot |W|\ge |S| $

Se per assurdo la tesi fosse falsa avremmo: $ n\cdot n\ge n^2+1 $, evidentemente falso.

[mitchan88]

Se solo aveste seguito la lezione mia e di enomis di combinatoria

Si deduce che enomis non ha seguito la propria lezione

[enomis_costa88]

Già..e mi è costato carissimo..scherzi a parte mi ero imposto di guardare quel problema SOLO dopo avere fatto gli altri 5 cosa che non è mai successa (1 fatto 2 impostato 3 fatto con lagrange + induzione 4 fatto in analitica 5 letto male e 6 non fatto risultato niente orali e l'anno prossimo starò a casa a brescia).