Galileiana 2007-2008/6
-
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
Galileiana 2007-2008/6
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).
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.
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.
"Sei la Barbara della situazione!" (Tap)
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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).
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.