OliForum Matematico

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).

scusa, forse non ho capito bene il problema, ma
i 90 numeri devono essere consecutivi? altrimenti il problema
mi sembra abbastanza ovvio

penso di si, jordan
comunque, se hai voglia postaci la dimostrazione con i 90 numeri non consecutivi...

desmo90 davvero ti sembra cosi ovvio??

se ne elimino 90 consecutivi a caso la tesi è banalmente FALSA

up raga..assicuro una bella soluzione

Segue banalmente dal teorema di Dilworth o dal suo duale...

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

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.

Credo che un mese sia abbastanza per un problema... Jordan puoi postare la soluzione bella? Grazie

Giusto per sapere, questo era citato sul libro di Giaquinta come teorema di Erdos-Szekeres (un classico del mio primo anno, he he)

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

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?)

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..