La venganza será terrible

agosto 30, 2008

Sea S una colección de n intervalos cerrados en la recta real. Llamamos altura enS a una función biyectiva a:S\longrightarrow\{1,2,\dots ,n\}. Dada una altura en S, decimos que s\in S puede ver a s'\in S si a(s)<a(s') y existe un punto p\in s\cap s' tal que p \notin t para todo t\in S con a(s)<a(t)<a(s'). Probar que existe una altura en S para la cual cada intervalo en S puede ver a lo sumo a otros tres.

c.f: Competencia Matemática Ernesto Paenza – 23va realización – 28 de agosto de 2008

5 comentarios to “La venganza será terrible”

  1. Ivan S said

    Sea S_1 un subconjunto de S con la mínima cantidad posible de elementos y con la propiedad de cubrir S. Ahora definimos S_{k} como un subconjunto de S-\bigcup_{i=1}^{k-1}S_i con la mínima cantidad posible de elementos y con la propiedad de cubrir S-\bigcup_{i=1}^{k-1}S_i. Como S es finito este procedimiento termina en algun momento.
    Obtuvimos una partición de S en subconjuntos S_1, S_2,\ldots , S_T.

    Vamos a construir una altura a, pidiendo que si x\in S_m e y\in S_n con m  a(y)

    Decimos que un conjunto de intervalos x_1,\ldots, x_k es una cadena si ningun intervalo esta contenido dentro de otro y x_m\cap x_{n} es no vacío si y solo si \left|m-n\right|\leq 1.
    Es facil ver que S_i es union de cadenas disjuntas.

    Lema 1: Un intervalo x\in S_i puede ver solamente intervalos de S_i y de S_{i-1}.

    En lo que sigue x_1, \ldots, x_k es una cadena maximal de intervalos de S_i.

    Definimos v(x_k) como el máximo numero de intervalos de S_{i-1} que puede ver x_k. Por definición de S_{i-1} tenemos 1\leq v(x_k)\leq 3.

    Lema 2: Si v(x_m)=v(x_n)=3 existe un t entre m y n tal que v(x_t)=1
    Demostración:
    Si el lema es falso llegamos a un absurdo.
    Para todo i existe un unico intervalo r_i\in S_{i-1} tal que x_i y x_{i+1} ven a r_i. Además los r_i son todos distintos.
    Tenemos una cadena de intervalos m_1, m_2, r_m,\ldots, r_{n-1}, n_1, n_2 \in S_{i-1} (x_m ve a los primeros tres y x_n a los ultimos tres).
    Pero esta cadena es mas larga que m_1, x_m,\ldots, x_n, n_2, lo que contradice la minimalidad de \# S_{i-1}.

    Decimos que x_j es máximo relativo de a sii a(x_j)>a(x_{j-1}) y a(x_j)>a(x_{j+1}). Analogamente definimos mínimo relativo.

    En cada cadena de cada S_i vamos a pedir que los máximos relativos de a coincidan con los intervalos en donde v vale 3.
    El Lema 2 muestra que podemos encontrar un mínimo relativo entre cada par de máximos relativos.

    Los máximos relativos de a no ven intervalos de S_i, los mínimos ven a lo sumo dos y los demas a lo sumo uno. Por el Lema 1 una altura con estas características cumple lo pedido.

    Existe una altura en S que cumpla estas condiciones (porque el orden parcial en S que definimos se puede “totalizar”‘). Esto completa la demostración.

    • Ivan S said

      Hay una parte que quedó mal, debería decir:

      Vamos a construir una altura a, pidiendo que si x\in S_m e y\in S_n con ma(y).

    • Ivan S said

      No se por que no queda bien, es:

      Vamos a construir una altura a, pidiendo que si x\in S_m e y\in S_n con
      ma(y)

    • Ivan S said

      No entiendo que pasa, no es el latex, wordpress debe filtrar caracteres

      Vamos a construir una altura a, pidiendo que si x pertenece a S_m e y pertenece a S_n con m menor a n entonces a(x) es mayor a a(y)

  2. julianhaddad said

    quise editarlo pero me pasa lo mismo. que bizarro

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: