permutazioni livello cese

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

permutazioni livello cese

Messaggio da jordan »

In una sequenza di lunghezza 101 sono stati messi in ordine casuale tutti i numeri da $ 1 $ a $ 101 $.
Dimostrare che è sempre possibile cancellarne 90 in modo tale che i rimanenti 11 termini formino una sequenza monotona (cioè crescente o decrescente).
The only goal of science is the honor of the human spirit.
Avatar utente
Desmo90
Messaggi: 160
Iscritto il: 17 lug 2007, 16:23
Località: sulla retta critica a nord di 1/2

Messaggio da Desmo90 »

scusa, forse non ho capito bene il problema, ma
i 90 numeri devono essere consecutivi? altrimenti il problema
mi sembra abbastanza ovvio
Avatar utente
mod_2
Messaggi: 726
Iscritto il: 18 ago 2007, 20:26
Località: In fondo a destra

Messaggio da mod_2 »

penso di si, jordan :?:
comunque, se hai voglia postaci la dimostrazione con i 90 numeri non consecutivi...
Appassionatamente BTA 197!
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

desmo90 davvero ti sembra cosi ovvio?? :?:

se ne elimino 90 consecutivi a caso la tesi è banalmente FALSA
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

up raga..assicuro una bella soluzione :)
The only goal of science is the honor of the human spirit.
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...

Messaggio da pic88 »

Segue banalmente dal teorema di Dilworth o dal suo duale... :P
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

mmm io non so chi sia dilwoth (anche se parecchi l'hanno usato al test della galileiana st'anno), eppure (come in tale test) c'è chi è riuscito senza strani teoremucci :lol:
The only goal of science is the honor of the human spirit.
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...

Messaggio da pic88 »

Comunque il duale si dimostra facilmente, e sulla falsariga della dimo metto la soluzione del problema.... ovviamente metto n^2+1 al posto di 101 e n+1 al posto di 11.

Diciamo a>b se a è più avanti di b nella sequenza e a>b. In quest'ipotesi, una catena è data da elementi a_1<a_2<...<a_k, un'anticatena è data da elementi inconfrontabili tra loro. Sia S(i) l'insieme degli x tali che T(x)=i, ogni S(i) è un'anticatena per ovvii motivi: se potessimo dire che x>y con x,y in S(i) allora prendo la catena a_1<...<y, aggiungo ad essa x>y e ho che T(x)>i, assurdo. Quante anticatene ho? Ovviamente k, dove k è la massima catena. Inoltre gli S(i) partizionano l'insieme in anticatene. Quindi il minimo numero di anticatene in cui potevo partizionare è <=k, ma è anche >=k, per pigeonhole, e ho concluso.
Avatar utente
matemark90
Messaggi: 67
Iscritto il: 03 nov 2006, 20:02
Località: la città del carnevale (RE)

Messaggio da matemark90 »

Credo che un mese sia abbastanza per un problema... Jordan puoi postare la soluzione bella? Grazie :D
Hasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

Giusto per sapere, questo era citato sul libro di Giaquinta come teorema di Erdos-Szekeres (un classico del mio primo anno, he he)
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 »

jordan ha scritto:mmm io non so chi sia dilwoth (anche se parecchi l'hanno usato al test della galileiana st'anno), eppure (come in tale test) c'è chi è riuscito senza strani teoremucci :lol:
A dire il vero penso che nessuno ne abbia fatto uso, visto, a parte il nome altisonante, nessuno si ricordava l'enunciato... (catene? anticatene? si mangiano?) :oops:
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan »

ki si risente...ma davvero?a me qualcuno appena uscito affermava di averlo scritto..comunque il principio è lo stesso, supponi per assurdo che tale situazione esista..
The only goal of science is the honor of the human spirit.
Rispondi