Simplicidad

octubre 14, 2009

alas, it is my vice, my fault:
Whiles others fish with craft for great opinion,
I with great truth catch mere simplicity

William Shakespear, Troilus and Cressida, Acto 4, Escena 4. Habla Troilo.

Una lista de n^2+1 números reales distintos contiene una sublista de n+1 elementos que es o creciente o decreciente. Por ejemplo, la lista 3,1,4,2,5 tiene a 3,4,5 como sublista ordenada.

2 comentarios to “Simplicidad”

  1. martingrupofundamental said

    Tenemos una lista a(1), a(2),…, a(n^2+1) de números reales distintos.
    Supongamos que ninguna sublista de n+1 números es creciente o decreciente. Construyo una función
    f:{1,…,n^2+1} –> {1,…,n} donde f(i) es el largo de la mayor lista creciente de números que empieza en el i-ésimo número. La preimágen de algún k contiene por lo menos n+1 elementos. Por hipótesis esta sublista de números no es decreciente y por la tanto existen i,j en la preimágen de k tal que i<j y a(i)<a(j). Pero entonces puedo tomar una lista creciente de k+1 números empezando por a(i) y sigiuendo por los k números crecientes que se que hay a partir de j. Esto contradice que la lista creciente de largo máximo a partir de a(i) es k.

  2. Juan Domingo Petruzza said

    http://en.wikipedia.org/wiki/Dilworth%27s_theorem
    (o su dual, que es mas facilongo)

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: