permutazioni livello cese
permutazioni livello cese
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).
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.
-
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
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.
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.
- matemark90
- Messaggi: 67
- Iscritto il: 03 nov 2006, 20:02
- Località: la città del carnevale (RE)
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
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?)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
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]
Membro del fan club di Ippo_
Membro del fan club di Ippo_