Galileiana 2007-2008/6

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
pic88
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

Messaggio da pic88 » 12 set 2007, 16:49

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
Messaggi: 21
Iscritto il: 22 nov 2006, 14:24

Messaggio da tiamat88 » 12 set 2007, 19:14

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
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 12 set 2007, 19:51

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

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)

Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 » 14 set 2007, 17:59

piever ha scritto:Se solo aveste seguito la lezione mia e di enomis di combinatoria :P
Si deduce che enomis non ha seguito la propria lezione :P
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 18 set 2007, 22:46

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.

Rispondi