Olimpiada Matemática Española – Problema 5: Coloraciones sanfermineras

Publicado por el 26 de abril de 2011 en Juegos | 20 comentarios

Quinta entrega de los problemas planteados en la XLVII Edición de la Olimpiada Matemática Española. En esta ocasión el problema (segundo de la segunda sesión), tuvo el siguiente enunciado, muy relacionado con Pamplona, la ciudad sede de esta edición de la OME:

Cada número racional se pinta de un color usando sólo dos colores: blanco y rojo. Se dice que una tal coloración es sanferminera cuando para cada dos números racionales x, y, con x \ne y, si se cumple una de las tres condiciones siguientes:

  1. xy=1;
  2. x+y=0;
  3. x+y=1

entonces x e y están pintados del mismo color. ¿Cuántas coloraciones sanfermineras hay?

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.

20 Comentarios

  1. josejuan

    26/04/2011

    Si he entendido el enunciado (en el que yo cambiaría “Cada número racional se pinta de un color…” por “Pinte los números racionales de tal forma…”):

    Blanco, Blanco:

    \{~x=\frac{1}{n},~y=n~|~n\in N ~\}

    Rojo, Rojo:

    \{~x=\frac{2}{2n+1},~y=2n+1~|~n\in N ~\}

    Blanco, Rojo:

    \{~x=\frac{1}{n},~y=-\frac{1}{n}~|~n\in N ~\}

    Rojo, Blanco:

    \{~x=-\frac{1}{n},~y=\frac{n+1}{n}~|~n\in N ~\}

    Luego la respuesta es: Las cuatro posibles..

    Aunque probablemente no haya entendido el problema porque parece muy fácil.

    Publica una respuesta
  2. Javier

    26/04/2011

    Hay una unica coloración:

    Demostramos que todos los enteros tienen la misma coloracion

    Supongamos 0 blanco

    Si 0 es blanco.

    Supongamos n blanco => -n blanco => n+1 blanco, pues -n+n+1=1

    Con lo cual hemos demostrado que todos los enteros son del mismo color.

    Si n blanco -> 1/n blanco

    Sea -p/q, irreducible tenemos dos opciones p>q, y p<q

    Si p<q, sabemos que p/q tiene el mismo color que q/p, con lo cual el caso es analogo.

    Sabemos que existe n natural tal que -p/q=-n+r/q, r<q

    Si r=1, 1/q es blanco

    si r mayor que1, r/q tiene el mismo color que -q/r, y repetimos analogamente este proceso, haciendo cada vez mas pequeños los denominadores, hasta que obtengamos que el color es analogolo siempre a un numero de la forma 1/n.

    Publica una respuesta
  4. Ford Prefect

    26/04/2011

    Javier, entonces hay dos coloraciones posible puesto que hay dos colores a elegir.

    Hay que decir, no obstante, que el enunciado es bastante, bastante incomprensible.

    Publica una respuesta
  5. josejuan

    26/04/2011

    “entonces x e y están pintados del mismo color”

    pues es verdad… en tal caso, no soy capaz de entender ni el enunciado.

    😕

    Publica una respuesta
  6. josejuan

    26/04/2011

    “… Se dice que una tal coloración es sanferminera cuando … si se cumple … entonces x e y están pintados del mismo color …”

    Uhm… la “tal coloración sanferminera” ¿serán las formas de colorear los racionales para cumplir la condición?… en tal caso sí parece bastante más complicado… y por supuesto no tienen porqué ser sólo dos.

    Las dos formas triviales son “todos los racionales blancos” y “todos los racionales rojos”, pero eso no quita, para que haya otras coloraciones “compatibles” (con las restricciones).

    Publica una respuesta
  7. josejuan

    26/04/2011

    Vale, la demostración de Javier sirve para probar que todos los racionales tienen el mismo color luego (por la demostración de Javier), sólo hay dos coloraciones.

    Publica una respuesta
  8. Maelstrom

    27/04/2011

    No estoy del todo convencido con la demo de Javier. Descomponiendo p/q en la forma n+r/q tenemos n blanco y r/q supongamos blanco, o suponiendo aun mas, supongamos ese r=1, tendriamos n+1/q con ese 1/q blanco. ¿Cómo entonces todo este n+1/q es blanco? ¿Por ser suma de dos blancos (n y 1/q)? El enunciado no dice nada de que la suma de dos blancos sea blanco. Bueno, a decir verdad, el enunciado es bastante confuso.

    Publica una respuesta
  9. Lautaro

    27/04/2011

    Hola.

    Para hacer las cosas más cómodas, podríamos reformular la regla para una coloración sanferminera como sigue:

    “Para todo n racional, debe cumplirse que tanto \frac{1}{n}, como -n, como 1-n tenga el mismo color (blanco o rojo) que n.”

    Bien. Por la condición 2, n debe tener la misma coloración que -n, y luego, por la condición 3, la misma que n+1. Haciendo el mismo razonamiento, usando en distinto orden las condiciones, tenemos que n también debe tener el mismo color que n-1.

    Entonces, sabemos que, en particular, todos los enteros deben tener el mismo color. Ahora, por la condición 1, n es de la misma coloración que \frac{1}{n}. Entonces, hasta ahora sabemos que el cero y todos los números de la forma \frac{1}{n} con n entero comparten coloración.

    Por último, tenemos que todos éstos deben compartir color con 1+\frac{1}{n} o, lo que es lo mismo, \frac{n+1}{n}. Lo mismo con \frac{n-1}{n}. Así, podemos seguir y decir que todos los números de las formas \frac{n\pm1}{n}, \frac{n\pm2}{n}, \frac{n\pm3}{n}, \dots tienen la misma coloración que n. Y éstos son todos los racionales. Por lo que las soluciones triviales son las únicas posibles: todos blancos o todos rojos.

    Saludos.

    Publica una respuesta
  10. Sive

    28/04/2011

    @Maelstrom, la demostración de Javier me parece correcta, y muy elegante, para mi gusto. Eso sí, me parece también que debió explicar mejor ese paso.

    La clave está en que uno de los sumandos es natural.

    Si un número racional r es blanco, r+1 es blanco, porque -r + (r+1) = 1.

    Por lo que r+n, siendo n natural, es blanco también.

    Publica una respuesta
  11. Felix

    30/04/2011

    El enunciado esta mal, si una de las tres condiciones se cumplen además de que y no es igual a x entonces x e y son de distinto color. Lo se por participar en la olimpiada, y dan 2 coloraciones.

    Publica una respuesta
  12. daniel73

    13/05/2011

    Félix tiene razón, el enunciado dice que x,y tienen que tener distinto color cuando cumplen al menos una de las tres condiciones. Si no, el problema sería más fácil que el propuesto en la competición, y la solución de Javier sería perfectamente correcta. Tal vez basándose en la solución de Javier (aunque sea a otro problema) alguien puede dar la solución al problema que sí se propuso en la OME.

    Publica una respuesta
  13. Osioso

    10/07/2011

    La parte final de la demostración de Javier también se puede hacer con el método del descenso infinito, un método muy interesante a mi parecer.

    Si p/q es rojo, con p>q (ya hemos dicho que se pueden intercambiar), y ambos enteros positivos, diferentes (porque si fueran iguales tendríamos que la fracción vale 1 y sería blanca), entonces existe otra fracción r/q tal que r/q + n = p/q. r/q tiene que ser rojo porque al sumarle 1 n veces se mantiene el color. También tiene que se rr, y ésta tendrá las mismas propiedades que la inicial. Entonces debe existir una succesión infinita decreciente de p>q>r…

    Pero como no existe ningún p natural mayor que infinitos números naturales, no existe ninguna fracción positiva de color rojo, y todos los racionales positivos son blancos. Eso, claro está, suponiendo que el 0 es blanco, porque también podría ser rojo, así que existen un total de 2 coloraciones sanfermineras.

    Saludos

    Luego, si cuando x+y=0, x, y tienen el mismo color, también son blancos todos los racionales negativos.

    Publica una respuesta
  14. Antonio

    30/09/2011

    Hola.
    Aporto mi solución:
    He considerado las aplicaciones f:Q-{0}—>Q, f(x)=1/x; g:Q—>Q, g(x)=-x y
    h:Q—>Q, h(x)=1-x.
    En Q he definido la relación: x~y si y sólo si y es imagen de x mediante una aplicación formada por un número finito de composiciones de f,g y h.
    Es fácil ver que la relación es de equivalencia.
    A continuación, he probado que todos los números racionales están relacionados con el 0, es decir, el respectivo conjunto cociente solo tiene un elemento. De aquí se deduce que fijado un color al 0, hay una única coloración. Por tanto sólo hay dos coloraciones fijando rojo y blanco respectivamente al 0.
    Para ver que todos los elementos de Q están relacionales he procedido de la siguiente forma:
    (1) 1/n~0, 2/n~0, …, (n-1)/n~0. (Por ejemplo, f(hg)^n(0)=1/n, luego 0~1/n)
    (2) He probado que a/b~0 para todo a,b(no nulo) tales que a/b>0. Para esto, basta hacer la división entera de a por b, para expresar a/b=c+d/b con d<b y observar que c+d/b=(hg)^c(d/b), por tanto, a/b~d/b~0.
    (3) Si a/b<0 y como a/b~(-a/b) y por (2) -a/b~0, por transitiva, a/b~0.
    A quien le interese los detalles se los puedo enviar, lo tengo escrito en LaTeX.
    Saludos!

    Publica una respuesta
  15. Agustin

    20/04/2012

    Llamaremos f(x) al color con que se pinta el número x:

    f(x+1)=f(1-(-x))=f(-x)=f(x)

    Por inducción f(x+k)=f(x) para cualquier k entero.

    También f(k+1/x)=f(1/x)=f(x)

    Usando fracciones continuas se tiene

    f( [a1,a2,…,an]) = f ( a1 + 1/[a2,…an]) = f [a2,..an]) = f( [a3,…,an] ) = …= f(an)=f(0)

    Como tod0 número racional positivo puede ponerse en forma de fracción continua, se concluye que f(q)=f(0)

    Si q fuese negativo sería f(q)=f(-q)=f(0)

    Así pues hay solo dos soluciones :
    – Todos los números pintados de blanco
    – Todos los números pintados de rojos

    Unos sanfermines demasiado monótonos 🙂

    Publica una respuesta
  16. daniel73

    20/04/2012

    Agustín, si lees un post mío un poco más arriba, verás que cuando x,y cumplen una de las dos condiciones, entonces han de tener DISTINTO color, no el mismo… Hay una errata en el enunciado, y el problema es algo más difícil que lo que planteas, y no, los sanfermines que resultan no son nada monótonos… igual que los de verdad!

    Publica una respuesta
  17. Agustin

    20/04/2012

    Bien, yo me limité a resolver el problema tal como aparece enunciado. Vaya ahí la solución suponiendo que en las condiciones dadas hay cambio de color.

    Llamaremos por comodidad 1 y -1 a los dos colores y diremos que una coloración sanferminera es una aplicación f:{Q} \to \{ -1,1 \} verificando que

    \forall x,y \in {Q} con x \neq y verificando x+y=0 ó x+y=1 ó xy=1, se tiene f(x)=-f(y)

    Se tienen los siguientes resultados:

    Si x\neq 0, - \frac 1 2: f(1+x)=f(1-(-x))=-f(-x)=f(x)
    Si x\neq 1, -1: f \left( {\frac 1 x} \right) =-f(x)

    f(1)=-f(0)
    f(1)=f(2)=f(3)=···=-f(0)

    Si x>0 y k \in {N}: f(k+x)=f(x) y f \left( k+ {\frac 1 x} \right) = f \left( {\frac 1 x} \right)=-f(x)
    Si x>0, x \neq 1, k \in {N}: f \left( k+ {\frac 1 x} \right) = f \left( {\frac 1 x} \right)=-f(x)

    Dado un número racional positivo x, este se puede expresar de manera única como fracción continua x=[a_1,a_2,…,a_n]
    Entonces:
    f(x)=f([a_1,a_2,…,a_n])=f \left( a_1+\frac 1 {[a_2,…,a_n]} \right)=-f \left( [a_2,…,a_n] \right)=f \left( [a_3,…,a_n] \right)=…=(-1)^{n-1}f \left( [a_n] \right)=(-1)^n f \left( 0 \right)

    Así, f está unívocamente determinada por el valor de f(0), para los valores positivos de x.

    Si x<0: f(x)=-f(-x) y tenemos que la unicidad se extiende a todos los racionales.

    Así pues hay dos coloraciones sanfermineras, una con f(0)=1 y otra con f(0)=-1

    Publica una respuesta
  19. Juanjo Escribano

    13/07/2012

    Hola Agustin,

    creo que la definición de f(x) está cruzada.

    Revísalo por favor

    Publica una respuesta
  20. Gustavo

    22/09/2013

    Los números X y-X tienen la misma coloración y -X y X+1 también Entonces X y X+1 tienen la misma coloración o sea los números enteros tienen la misma coloración X y 1/X tienen la misma coloración entonces Los números de la forma 1/n Son de la misma coloración

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Quinta entrega de los problemas planteados en la XLVII Edición de la Olimpiada Matemática…

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.

Responder a Lautaro Cancelar respuesta

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

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.