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

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 $x \ne y$ , si se cumple una de las tres condiciones siguientes:

$xy=1$ ;

$x+y=0$ ;

$x+y=1$

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

Que se os dé bien.

19 comentarios

josejuan | 26 de April de 2011 | 08:50

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.
Javier | 26 de April de 2011 | 10:50

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.
.mau. | 26 de April de 2011 | 12:28

de distinto color, non de mismo color!
Ford Prefect | 26 de April de 2011 | 14:40

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.
josejuan | 26 de April de 2011 | 14:49

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

pues es verdad… en tal caso, no soy capaz de entender ni el enunciado.
josejuan | 26 de April de 2011 | 14:57

“… 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).
josejuan | 26 de April de 2011 | 15:08

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.
Maelstrom | 27 de April de 2011 | 00:01

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.
Lautaro | 27 de April de 2011 | 07:25

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.
Trackback | 27 Apr, 2011

Bitacoras.com
Sive | 28 de April de 2011 | 07:33

@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.
Felix | 30 de April de 2011 | 19:46

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.
daniel73 | 13 de May de 2011 | 11:46

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.
Osioso | 10 de July de 2011 | 14:16

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.
Antonio | 30 de September de 2011 | 22:49

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!
Agustin | 20 de April de 2012 | 11:13

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
daniel73 | 20 de April de 2012 | 12:18

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!
Agustin | 20 de April de 2012 | 18:37

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
daniel73 | 20 de April de 2012 | 20:23

Muy buena Agustín!!!