Olimpiada Matemática Española 2013 – Problema 3: Coloración

Tercer problema, último del primer día, de la Olimpiada Matemática Española 2013 celebrada en Bilbao. El enunciado es el siguiente:

Sean k y n enteros, con n \geq k \geq 3. Se consideran n+1 puntos en el plano, no alineados entre sí tres a tres. A cada segmento que une entre sí dos de esos puntos se le asigna un color de entre k colores dados.

Se dice que un ángulo es bicolor si tiene por vértice uno de los n+1 puntos, y por lados dos de los segmentos anteriores que sean de distinto color.

Demuestra que existe una coloración tal que el número de ángulos bicolores es estrictamente mayor que

n \; \left \lfloor \cfrac{n}{k} \right \rfloor ^2 \; \displaystyle{{k \choose 2}}

OBSERVACIÓN: Se denota por \lfloor t \rfloor la parte entera del número real t. Es decir, el mayor entero n \leq t.

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

19 Comentarios

  1. Tiene pinta de ser bastante complicado. Quizá pueda salir por principio del palomar. Unas cuentas así breves, pero que pueden ser indicativas:

    Hay n+1 puntos. Entonces como cada recta es la unión de dos puntos las rectas las obtenemos como:
    Tomamos un punto (n+1 posib) y luego otro distinto (n posib) y consideramos dicha recta. Claro está que cada recta será considerada dos veces. Luego el número de rectas es: n*(n+1)/2

    En cada vértice pasan n rectas combínandolas de 2 en 2 obtengo ángulos luego el número de ángulos por vértice es n(n-1)/2 y en total hay (n+1)n(n-1)/2 ángulos.

    Publica una respuesta
  2. Daniel cao,

    de acuerdo con tus comentarios excepto (y no es discrepancia sino duda) en que el método a usar sea el del palomar.

    Estoy revisando inducción completa para k y n separadamente, que en un principio me parece mas adecuado

    Publica una respuesta
  3. Veo que si añado un punto, y escojo adecuadamente el color de cada segmento tomando uno diferente del que mas tenga en el punto destino, genero en cada punto un mínimo de mod(n/k) ángulos bicolores en el punto destino, y en total un mínimo de n*mod(n/k) nuevos ángulos bicolores

    Publica una respuesta
  4. Sea V=\{0,1,\dots,n\} el conjunto formado por los n+1 vértices, sea C=\{0,1,\dots,k-1\} el conjunto formado por los k colores y sea \mathscr{V}_2 el conjunto formado por subconjuntos de dos elementos de V (conjunto formado por todos los segmentos). Consideremos la siguiente coloración:

    \begin{matrix} \mathscr{V}_2 & \longrightarrow & C \\ \{r,s\} & \longmapsto & r+s\mod k\end{matrix}

    Esta coloración está “bien definida”, pues el color asignado al lado r,s es igual al asignado a s,r, pues r+s\equiv s+r\mod k.

    Consideremos el vértice 0 y el segmento \{0,r\} entonces otro segmento \{0,s\} está

    pintado del mismo color, si y sólo si, r\equiv s\mod k, es decir, s=r+t k con t entero

    no negativo y r+tk\leq n, es decir, 0\leq t\leq\dfrac{n-r}{k}. Luego por el vértice 0, hay

    q_r=\left\lfloor\dfrac{n-r}{k}\right\rfloor+1 segmentos pintados del mismo color que el segmento \{0,r\}.

    Dando lugar a

    {\displaystyle\binom{q_r}{2}=\frac{q_r(q_r-1)}{2}=\frac{\left\lfloor\dfrac{n-r}{k}\right\rfloor\left(\left\lfloor\dfrac{n-r}{k}\right\rfloor+1\right)}{2}} ángulos unicolor en el vértice 0, de color igual al segmento \{0,r\}.

    Por tanto, el número total de ángulos bicolor asociados al vértice 0 es:

    {\displaystyle\binom{n}{2}-\sum_{r=1}^k\binom{q_r}{2}} y como hay n+1 vértices, en total habrá

    {\displaystyle T=(n+1)\left(\binom{n}{2}-\sum_{r=1}^k\binom{q_r}{2}\right) }

    Ahora queda la cuestión, ¿ {\displaystyle  T>n\left\lfloor\frac{n}{k}\right\rfloor^2\binom{k}{2}} ?

    Publica una respuesta
  5. En mi comentario anterior, no es correcto el cálculo de T

    Contemos los ángulos unicolor para la coloración definida en mi comentario anterior:

    Si dos vértices r y s son congruentes módulo k, entonces el ángulo formado por estos dos vértices y cualquier otro vértice t, es unicolor. En efecto, los segmentos \{t,r\} y \{t,s\} estarán pintados del mismo color, pues t+r\equiv t+s\mod k. Por tanto, para cada pareja de vértices congruentes módulo k hay (n+1)-2=n-1 ángulos unicolor, y el total de ángulos unicolor será:
    U=(n-1)N, donde N es el total de parejas de vértices equivalentes módulo k.

    Determinemos N: Sea u\in\{0,1,\dots,k-1\}. Si v es un vértice congruente módulo k con u, entonces v=u+mk, m\in\mathbb{Z}. Puesto, que v es un vértice, debe verificarse que 0\leq u+mk\leq n, luego

    m\leq\dfrac{n-u}{k} y puesto que 0<u<k, se tiene que m\geq 0. Por tanto, u se repite

    \left\lfloor\dfrac{n-u}{k}\right\rfloor+1 veces módulo k. Luego

    {\displaystyle N=\sum_{u=0}^k\binom{\left\lfloor\frac{n-u}{k}\right\rfloor+1}{2} }

    y el número total de ángulos bicolor será:

    {\displaystyle T=(n+1)\binom{n}{2}-(n-1)\sum_{u=0}^k\binom{\left\lfloor\frac{n-u}{k}\right\rfloor+1}{2}}

    Publica una respuesta
  6. Un trabajo muy parcial:

    Se cumple para n=k=3 que NVB(3,3)= número de vértices bicolor = 12 > 9 = 3*mod(3/3)^2 *(3,2) = 9 ((3,2) es 3 sobre 2, o sea = 3).

    x 1 2 3 4
    1 x 3 2 1
    2 3 x 1 2
    3 2 1 x 3
    4 1 2 3 x

    donde abcisas y ordenadas son los puntos y su cruce es el color asociado

    Si k=3 y se cumple para n, NVB(n,3)= número de vértices bicolor) mayor 3n*mod(n/3)^2 y teniendo en cuenta mi comentario anterior,

    NVB(n+1,3) mayor o = NVB(n,3) + n*mod(n/3) mayor que 3n*mod(n/3)^2+n*mod(n/3).

    Para n= 3a +b, con bmenor que 3, y solo para b={0,1},
    3n*mod((n+1)/3)^2+3*n*mod((n)/3)/3 = 3n*mod((n+1)/3)^2+3*mod(n/3)^2 =
    3n*mod((n+1)/3)^2*3*mod((n+1)/3)^2 = 3*(n+1)*mod((n+1)/3)^2,

    con lo que falta el caso b=2 para demostrar que NVB(n,3) cumple la condición para todo n, y posteriormente hacer lo mismo para k (que me aprece aun mas difícil)

    Publica una respuesta
  7. Imaginemos que coloreamos de tal forma que la distribución para cada vértice es lo más equitativa posible. De cada color habrá, como mínimo,  \lfloor\frac{n}{k}\rfloor rectas. Entonces, para cada una de las  \binom {k} {2} parejas de colores habrá, al menos,  \lfloor\frac{n}{k}\rfloor^2 ángulos bicolor, y si multiplicamos por los n+1 vértices tendremos un número total:

     T\geq(n+1)\lfloor\frac{n}{k}\rfloor^2\binom {k} {2}>n\lfloor\frac{n}{k}\rfloor^2\binom {k} {2}

    ¿Es siempre posible distribuir los colores así? Para n impar (n+1 par) está claro que sí. Es lo mismo que organizar un campeonato entre n+1 equipos que juegan todos contra todos. A cada pareja se le puede asignar un número entre 1 y n (que en el campeonato representaría el número de jornada en la que juegan entre ellos). Después se calcula el módulo k del número asignado para calcular el color.

    Para n par tengo que pensarlo.

    Publica una respuesta
  8. Golvano

    Muy bueno como llegas a la fórmula.

    en la construcción, no veo como tienes en cuenta que k puede ser menor que n, de hecho lo que dices para n+1 par es cierto para n=k (mi ejemplo de n=k=3 es un caso particular, y existe método constructivo para cualquier nº de elementos par)

    Publica una respuesta
  9. De forma gráfica:

    https://www.dropbox.com/s/35pjke34usjyo0k/Olimpiada.jpg

    Al hacer los n+1 puntos, como dice Golvano ya está demostrado si n es impar. Si es par se resuelve para n puntos y el último punto se une a todos los demás sin buscar la solución óptima: con tener solo un ángulo bicolor en el último punto ya está demostrado.

    Cuando pueda lo subo de forma analítica, aunque es similar a la de Golvano.

    Publica una respuesta
  10. Tenemos n+1 puntos. De cada punto salen n aristas. En cada punto hay \frac{n^2-n}{2} ángulos. Hay k colores. De un punto salen n_i aristas de color i, de modo que n_1+n_2+…+n_k=n. El número de ángulos monocolores es \frac{n_1^2-n_1}{2}+\frac{n_2^2-n_2}{2}+…+\frac{n_k^2-n_k}{2}=\frac{n_1^2+n_2^2+…+n_k^2}{2}-\frac{n}{2}.

    El número de ángulos bicolores es \frac{n^2-n}{2}-\frac{n_1^2+n_2^2+…+n_k^2}{2}+\frac{n}{2}=\frac{n^2-n_1^2-n_2^2-…-n_k^2}{2}.

    El valor máximo es el que minimiza n_1^2+n_2^2+…+n_k^2, que es n_i=\frac{n}{k}. Pero como los valores de n_i deben ser enteros, \lfloor\frac{n}{k}\rfloor\leq n_i\leq\lfloor\frac{n}{k}+1\rfloor. Por tanto en la solución óptima n_i=\lfloor\frac{n}{k}\rfloor o n_i=\lfloor\frac{n}{k}+1\rfloor.

    El número de ángulos bicolores es a\lfloor\frac{n}{k}\rfloor\lfloor\frac{n}{k}\rfloor+b\lfloor\frac{n}{k}\rfloor\lfloor\frac{n}{k}+1\rfloor+c\lfloor\frac{n}{k}+1\rfloor\lfloor\frac{n}{k}+1\rfloor con a+b+c=\binom{k}{2} que es el número de combinaciones de ángulos con dos colores distintos.
    a\lfloor\frac{n}{k}\rfloor\lfloor\frac{n}{k}\rfloor+b\lfloor\frac{n}{k}\rfloor\lfloor\frac{n}{k}+1\rfloor+c\lfloor\frac{n}{k}+1\rfloor\lfloor\frac{n}{k}+1\rfloor\geq \lfloor\frac{n}{k}\rfloor^2 (a+b+c)=\lfloor\frac{n}{k}\rfloor^2 \binom{k}{2}

    Si n+1 es par las combinaciones de dos colores distintos son (n+1)\lfloor\frac{n}{k}\rfloor^2 \binom{k}{2} > n\lfloor\frac{n}{k}\rfloor^2 \binom{k}{2}.
    Si n+1 es impar las combinaciones de dos colores distintos en los primeros n puntos (pares) son n\lfloor\frac{n}{k}\rfloor^2 \binom{k}{2}. Con hacer que en el punto n+1 haya dos aristas de distinto color ya se cumple la desigualdad.

    Publica una respuesta
  11. @Juanjo Escribano: No sé si te entiendo bien. Si te refieres a la asignación de los colores, una vez que has asignado un número entre 1 y n a cada par de vértices, se calcula el módulo k para asignar el color. Como sabemos que para cada vértice los números asignados son todos los posibles sin repetición (y por lo tanto, consecutivos), la asignación de colores es equitativa.

    @Mmonchi: Si no estoy equivocado, la demostración para n+1 a partir de n sólo es válida si n+1 no es múltiplo de k. En ese caso, \lfloor\frac{n+1}{k}\rfloor=\lfloor\frac{n}{k}\rfloor, y simplemente con un ángulo bicolor más:

    T'>T\geq(n+1)\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}=(n+1)\lfloor\frac{n+1}{k}\rfloor^2\binom{k}{2}

    El caso que queda, n par y múltiplo de k, lo he resuelto de otra forma, pero es un poco farragosa. Si tengo tiempo, lo escribo luego.

    Publica una respuesta
  12. @Golvano, ya veo lo que dices. Para n par y múltiplo de k las nuevas aristas que salen de los primeros n puntos son todas del mismo color y no aportan un ángulo bicolor nuevo en el punto n+1. Hay que buscar otra distribución para ese caso, lo pensaré (si no lo subes antes 😉 ).

    Publica una respuesta
  13. La demostración para n par y múltiplo de k se basa en el hecho de que siempre es posible conseguir una distribución no óptima en la que el número de ángulos bicolor para cada vértice sea solamente uno menos que en el caso óptimo (por ejemplo, asignando a cada recta el color correspondiente al módulo k de la suma de los dos vértices, habiendo asignado previamente un número entre 1 y n+1 a cada vértice).

    Entonces se tiene:

    T\geq(n+1)(\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}-1)=n\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}+\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}-n-1=n\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}+(\frac{n}{k})^2\binom{k}{2}-n-1=n\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}+n^2\frac{k-1}{2k}-n-1\geq_{k\geq 3} n\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}+\frac{n^2}{3}-n-1>_{n\geq 4} n\lfloor\frac{n}{k}\rfloor^2\binom{k}{2}

    Publica una respuesta
  14. Golvano, no veo cómo consigues siempre uno menos del caso óptimo.

    Por ejemplo, para n=16 y k=4 el óptimo se consigue con una distribución de colores en los 15 vértices que sea {4,4,4,3}. Eso nos da 6+6+6+3=21 ángulos monocolores. Al hacer otra distribución siempre habrá varios ángulos monocolores más, no uno. Con {5,4,4,2} tengo 12+6+6+1=25, que son cuatro más; con {5,4,3,3} tengo 12+6+3+3=24, que son tres más.

    Publica una respuesta
  15. Ya, es que esa parte no la expliqué. Lo voy a intentar explicar ahora sobre tu ejemplo.

    Lo primero es que entiendo que, en realidad, en tu ejemplo, n vale 15. Es decir, hay 16 vértices.

    Por cada vértice pasarán 15 rectas y la distribución óptima sería, como tú dices {4,4,4,3}. En realidad, en la demostración, lo que se está utilizando es que, de cada color, hay al menos \lfloor\frac{n}{k}\rfloor rectas, en este caso 3. Si cogemos dos colores cualesquiera, el número de ángulos compuestos por una recta de cada uno de esos dos colores será al menos \lfloor\frac{n}{k}\rfloor^2, en este caso 9. Multiplicando por el número de parejas de colores posibles, que es \binom{k}{2}, en este caso 6, se obtiene el número mínimo de ángulos bicolor por vértice (54).

    Lo que yo digo es que con una distribución no óptima, por ejemplo el módulo k de la suma, se obtiene un número mínimo de ángulos bicolor que es uno menos, es decir, 53, en este caso. Concretamente, en este ejemplo, la distribución sería {5,4,4,2}, y el número de ángulos bicolor sería 82.

    La idea básica es la siguiente. En el caso óptimo estamos trabajando con la distribución {3,3,3,3} (los extras sólo nos van a favorecer), y el número de ángulos, como ya he dicho, 54. En el caso no óptimo, la distribución sería {4,3,3,2} y el número de ángulos, 53.

    No es difícil comprobar que esto es así para cualquier valor de n y k.

    Publica una respuesta
  16. Completamente de acuerdo. Yo entendía como óptima la {4,4,4,3}, pero tomando como tal la {3,3,3,3} sí es todo válido.

    Publica una respuesta
  17. Numeramos los colores del 1 al k.
    Para cada par de puntos (i,j) les asigno el color (i+j) mod k +1.
    Así, de los n segmentos que salen de un punto i habrá, a lo menos, Int(n/k) de cada color. (Creo que esto es obvio, pues los colores se asignan de modo correlativo).
    Ahora, trabajando para un solo vértice, hay (k sobre 2) pares de colores. y de cada color puedo elegir int(n/k) aristas, luego el total de ángulos bicolores mínimo que sale de un vértice es el producto (k sobre 2) * int(n/k)^2. Como hay (n+1) vértices el total de ángulos bicolores sería el producto anterior multiplicado por (n+1). Como existe un caso (n múltiplo de k) en que se daría la igualdad, para asegurar que es estrictamente mayor se ppone n en la expresión por demostrar y no (n+1). Saludos

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *