Olimpiada Matemática Española – Problema 5: Coloraciones sanfermineras
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
, si se cumple una de las tres condiciones siguientes:
;
;
entonces x e y están pintados del mismo color. ¿Cuántas coloraciones sanfermineras hay?
Que se os dé bien.
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:
Rojo, Rojo:
Blanco, Rojo:
Rojo, Blanco:
Luego la respuesta es: Las cuatro posibles..
Aunque probablemente no haya entendido el problema porque parece muy fácil.
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.
26/04/2011
de distinto color, non de mismo color!
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.
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.
😕
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).
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.
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.
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
racional, debe cumplirse que tanto
, como
, como
tenga el mismo color (blanco o rojo) que
.”
Bien. Por la condición 2,
debe tener la misma coloración que
, y luego, por la condición 3, la misma que
. Haciendo el mismo razonamiento, usando en distinto orden las condiciones, tenemos que
también debe tener el mismo color que
.
Entonces, sabemos que, en particular, todos los enteros deben tener el mismo color. Ahora, por la condición 1,
es de la misma coloración que
. Entonces, hasta ahora sabemos que el cero y todos los números de la forma
con
entero comparten coloración.
Por último, tenemos que todos éstos deben compartir color con
o, lo que es lo mismo,
. Lo mismo con
. Así, podemos seguir y decir que todos los números de las formas
tienen la misma coloración que
. Y éstos son todos los racionales. Por lo que las soluciones triviales son las únicas posibles: todos blancos o todos rojos.
Saludos.
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.
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.
13/05/2011
Félix tiene razón, el enunciado dice que
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.
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 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.
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!
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 🙂
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!
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:
verificando que
Se tienen los siguientes resultados:
Si
: f(1+x)=f(1-(-x))=-f(-x)=f(x)
=-f(x)
Si
f(1)=-f(0)
f(1)=f(2)=f(3)=···=-f(0)
Si x>0 y
: f(k+x)=f(x) y
=-f(x)
:
=-f(x)
Si x>0,
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] [a_1,a_2,…,a_n]](https://s0.wp.com/latex.php?latex=%5Ba_1%2Ca_2%2C%26%238230%3B%2Ca_n%5D&bg=ffffff&fg=000000&s=0)
=
=-
=
=…=
=
Entonces:
f(x)=
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
20/04/2012
Muy buena Agustín!!!
13/07/2012
Hola Agustin,
creo que la definición de f(x) está cruzada.
Revísalo por favor
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