Tercer problema, último del primer día, de la Olimpiada Matemática Española 2013 celebrada en Bilbao. El enunciado es el siguiente:
Sean
y
enteros, con
. Se consideran
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
Se dice que un ángulo es bicolor si tiene por vértice uno de los
Demuestra que existe una coloración tal que el número de ángulos bicolores es estrictamente mayor que
OBSERVACIÓN: Se denota por
la parte entera del número real
. Es decir, el mayor entero
.
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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.
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
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
Sea el conjunto formado por los vértices, sea el conjunto formado por los colores y sea el conjunto formado por subconjuntos de dos elementos de (conjunto formado por todos los segmentos). Consideremos la siguiente coloración: Esta coloración está «bien definida», pues el color asignado al lado es igual al asignado a , pues . Consideremos el vértice y el segmento entonces otro segmento está pintado del mismo color, si y sólo si, , es decir, con entero no negativo y , es decir, . Luego por el vértice , hay segmentos pintados del mismo color que el segmento . Dando… Lee más »
En mi comentario anterior, no es correcto el cálculo de … Contemos los ángulos unicolor para la coloración definida en mi comentario anterior: Si dos vértices y son congruentes módulo , entonces el ángulo formado por estos dos vértices y cualquier otro vértice , es unicolor. En efecto, los segmentos y estarán pintados del mismo color, pues . Por tanto, para cada pareja de vértices congruentes módulo hay ángulos unicolor, y el total de ángulos unicolor será: , donde es el total de parejas de vértices equivalentes módulo . Determinemos : Sea . Si es un vértice congruente módulo con… Lee más »
Corrijo: la suma en
y en 
va desde 
hasta 
.
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… Lee más »
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, rectas. Entonces, para cada una de las parejas de colores habrá, al menos, ángulos bicolor, y si multiplicamos por los vértices tendremos un número total: ¿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… Lee más »
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)
De forma gráfica:
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.
Tenemos puntos. De cada punto salen aristas. En cada punto hay ángulos. Hay colores. De un punto salen aristas de color , de modo que . El número de ángulos monocolores es . El número de ángulos bicolores es . El valor máximo es el que minimiza , que es . Pero como los valores de deben ser enteros, . Por tanto en la solución óptima o . El número de ángulos bicolores es con que es el número de combinaciones de ángulos con dos colores distintos. Si es par las combinaciones de dos colores distintos son . Si es… Lee más »
@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, , y simplemente con un ángulo… Lee más »
@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 😉 ).
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:
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.
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 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 , en este… Lee más »
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.
Continuo con mi entrada anterior:
Había llegado a expresar:
para la coloración que definí en mi primer comentario (RB | 24 de abril de 2013 | 12:59)
He podido simplificar esta expresión reduciéndola a:
para probar que
, donde 
Algunos resultados:
Por último, algunos ejemplos gráficos:
https://www.dropbox.com/s/j31i4ykazryzcqd/coloraci%C3%B3n.pdf
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… Lee más »