Download Soluciones

Problemas Olímpicos I
Eva Elduque Laburta y Adrián Rodrigo Escudero
Teoría:
En toda la sesión, a, b, c... van a ser números enteros.
Primero recordamos algunas definiciones ya conocidas:
1. Si b  a  q , escribimos a | b (se lee “ a divide a b ”).
2. Si m | a  b , escribimos a  b(mod .m) (se lee “ a es congruente con b módulo m”).
A continuación enunciamos una serie de propiedades que ya conocéis, aunque quizá no
las hayáis visto escritas con esta forma. Todas estas propiedades son fáciles de
demostrar y podéis hacerlo como ejercicio.
1. Si a | b y b | c , entonces a | c .
2. Si d | a y d | b , entonces d | ax  by .
3. Si dos términos de a  b  c son divisibles por d , el tercero también es divisible por
d . Si d divide a un término, pero no divide a otro, entonces d no divide al tercero.
Y por tanto m.c.d.c, b  m.c.d.b, c  b
4. Si a  bmod .m y b  cmod .m , entonces a  cmod .m
5. Si a  a'(mod .m) y b  b'(mod .m) , entonces se cumple:
a  b  a'b'(mod .m)
a  b  a'b'(mod .m)
a n  a' (mod .m)
a  b  a'b'(mod .m)
6. Si ca  cb(mod .m) , y m.c.d .c, m  1 (es decir, c y m son primos entre sí).
Entonces podemos “dividir” por c , es decir:
a  bmod .m
n
Por último os mostramos dos teoremas. El primero ya lo conocéis desde hace mucho
tiempo y es básico en la teoría de números. Sin embargo, el segundo probablemente sea
nuevo para vosotros y no se usa en la mayoría de los problemas, pero siempre viene
bien conocerlo por si acaso.
1. (Algoritmo de la división) Dados a, b (donde b  0 ), existen dos únicos números
c, r que cumplen:
a  bc  r (con 0  r | b | )
Además, se cumple que:
m.c.d.a, b  m.c.d.b, r 
2. (Teorema pequeño de Fermat) Si p es primo, y a no es múltiplo de p , se cumple
que:
a p 1  1mod . p 
1
Demostración:
Primero consideramos la siguiente secuencia de números:
0, a,2a,3a,...,  p  1a
Vamos a ver que dos números cualesquiera distintos de la secuencia no son congruentes
entre sí módulo p. Para ello cogemos dos miembros de la secuencia: xa, ya , veremos
que la única forma de que se cumpla xa  ya(mod . p) es que x  y
Tenemos pues: xa  ya(mod . p) Como p es primo y no divide a a , m.c.d .a, p   1 , y
podemos “dividir” por a : x  ymod . p . Y esto último implica que x  y , ya que
ambos números son menores que p y mayores o iguales que 0.
Segundo comparamos estas dos secuencias de números:
0,1,2,3,..., p  1
0, a,2a,3a,...,  p  1a
La primera secuencia está formada por todos los posibles valores módulo p . Esto
quiere decir que dado un número cualquiera, es congruente con un único número de la
primera secuencia (esto es consecuencia del Algoritmo de la división)
Así, dado un número de la segunda secuencia, será congruente con uno de la primera
secuencia. Además, dos números distintos de la segunda secuencia son congruentes
números distintos de la primera secuencia (ya que si no, por la propiedad 4, serían
congruentes entre sí). Así:
1  2  3  ...   p  1  a p 1  a  2a  3a  ...   p  1a  1  2  3  ...   p  1mod . p 
Como todos los números de la secuencia 1,2,3,..., p  1 son primos respecto a p ,
podemos “dividir” por ellos para obtener:
a p 1  1mod . p 
Que es lo que queríamos demostrar.
2
Problemas:
1. Encontrar todas las soluciones enteras posibles, x e y, de la ecuación: p(x+y)=xy,
siendo p un número primo.
(Fase local, 2007)
Solución: Es claro que p | xy , y como p es primo, se tiene que p | x o p | y . Como el
problema es simétrico, supondremos p | x , es decir, x  pk para algún k entero. Ahora
tenemos p(kp  y)  kpy  kp  y  ky  kp  (k - 1)y . Como m.c.d. (k, k-1)=1, para
todo k entero, k-1|p, por lo que k-1 sólo puede tomar los siguientes valores: 1, -1, p, -p.




k - 1  1 , ( k  2 ): se tiene que y  2p, x  2p .
k - 1  -1 , (k = 0): se tiene que y  0, x  0 .
k - 1  p , ( k  p  1 ): se tiene que y  p  1, x  (p  1)p .
k - 1  -p , ( k  1 - p ): se tiene que y  p - 1, x  (1 - p)p .
Éstas son todas las soluciones que hay.
2. Escribo en la pizarra 14 números enteros, no necesariamente distintos, que
verifican la propiedad de que al borrar cualquiera de ellos, puedo agrupar los
trece restantes en tres montones de igual suma.
a) Demuestra que cada uno de los catorce es múltiplo
b) ¿Es posible que alguno de los catorce que he escrito no sea el 0?
de
3.
(Fase local 2002)
Solución:
a) Sean n1, n2,…,n14 los números que hay escritos en la pizarra, y sea S la suma de todos
ellos. Denotamos si a la suma de cada uno de los tres montones que resultan si borras el
número ni, para i=1,2,…14.
Se tiene: S  n i  3si , para todo i=1,2,…,14. Al sumar las 14 ecuaciones, queda
14
14
14
i 1
i 1
i 1
14S   ni  3( s i ) , o lo que es lo mismo, 13S  3( s i ) . De esto último se deduce
que, como 3 no divide a 13, tiene que ocurrir 3 | S , es decir, S = 3c, con c entero.
Volviendo ahora a las ecuaciones iniciales, se tiene 3c  n i  3si , luego 3|ni para todo
i=1,2,…14.
b) Ya sabemos que ni es múltiplo de 3. Llamamos m i :
ni
(para todo i=1,2,…,14).
3
3
s
s
S ni S  ni 3si
 

 3 i , con i un número entero, por ser si
3 3
3
3
3
3
suma de números que son múltiplos de 3 (para todo i=1,2,…14). Así, vuelve a repetirse
el problema, tenemos 14 números enteros mi , cuya suma es c, y que quitando
cualquiera de ellos se pueden agrupar en montones de igual suma, luego reiterando el
argumento, los mi, vuelven a ser divisibles por 3. Así, se ve que los ni se van a poder
dividir indefinidamente por 3, y el único entero que cumple eso es el 0, luego ni=0 (para
todo i=1,2,…,14), y NO es posible que algún entero de los 14 que he escrito no sea el 0.
Se tiene c  mi 
3. Encuentra todos los enteros positivos m y n tales que n! + 1 = (m! - 1)2.
(Fase local 2002)
Solución: Desarrollando la ecuación, tenemos n!  1  (m! ) 2 - 2(m! )  1 , es decir,
n!  (m! )(m!-2). De aquí se deduce que m  3 y n  m , porque si m  1 o m  2 ,
tenemos que (m!-2)  0 , luego n! 0 (imposible), y es claro que n  m , porque
n!  (m! )(m!-2) , luego n! m!  n  m .
Ahora, ponemos la ecuación como n(n - 1)...(m  2)(m  1)  m!-2 (hemos simplificado
por m!). Como m  3 , 3 | (m! ) , luego (m!-2) no es múltiplo de 3, luego n  m  1 , o
n  m  2 (en otro caso, si n  m  3 , se tiene que 3|(m+3)(m+2)(m+1), porque en tres
números naturales consecutivos siempre va a haber un múltiplo de 3, y como se tendría
que (m  3)(m  2)(m  1) | n(n - 1)...(m  2)(m  1) , tendría que ocurrir que
3 | n(n - 1)...(m  2)(m  1) , que ya hemos probado que es imposible).
Estudiemos los dos casos posibles:
 n  m  1 : La ecuación queda como m  1  m! - 2 , o lo que es lo mismo, m  3  m! .
Como m | m , y m | (m)! , m tiene que dividir a 3, y como m  3 , se tiene que m  3 .
Sustituyendo en la ecuación m  3  m! , queda que 3+3=3!=6, por lo que m  3 ,
n  4 es una solución posible.
 n  m  2 : La ecuación queda como (m  2)(m  1)  m!-2 , o lo que es lo mismo,
m 2  3m  4  m! , como m | m , m | m2, y m | (m)! , se tiene que m | 4 , y como
m  3 , m  4 . Sustituyendo en la ecuación m 2  3m  4  m! , se tiene 16+12+4=4!,
y esto no es cierto, porque 16+12+4=32, y 4!=24.
La única solución al problema es pues m  3 , n  4 .
4. Se dispone de pequeñas piezas de madera de tamaño 4 x 5 x 10. Decidir si es
posible o no apilarlas, sin dejar huecos y apoyándolas siempre sobre cualquiera
de sus caras, para formar un ortoedro de dimensiones 22003 x 32003 x 52003.
(Fase local 2003)
Solución: La respuesta es NO, no hace falta más que fijarse en que una de las caras del
ortoedro tiene superficie 2 2003 ·32003  6 2003 . Si hubiera alguna forma de apilar las cajas
para que llenaran toda la superficie de esa cara, sería a base de sumar superficies de
4
4  5  20 , 4 10  40 ó 5 10  50 (unidades métricas cuadradas), que son las superficies
de las caras de las cajas de madera. Todas estas son múltiplos de 10, y como 62003 no es
múltiplo de 10, es imposible.
5. Demostrar que la fracción
21  n  4
( n es un número entero) no puede
14  n  3
simplificarse más.
(Fase internacional, 1959)
Solución: Tenemos que probar que m.c.d.21 n  4,14  n  3  1. Aplicamos la propiedad
4 varias veces:
m.c.d.21 n  4,14  n  3  m.c.d.7  n  1,14  n  3
m.c.d.14  n  3,7  n  1  m.c.d.7  n  2,7  n  1
m.c.d.7  n  2,7  n  1  m.c.d.1,7  n  1
Pero m.c.d.7  n  1,1  1
El método que hemos seguido se conoce como Algoritmo de Euclides.
6. a) Demostrar que no existe ningún número n que cumple n 2  2(mod .4) ó
n 2  3(mod .4)
b) Hallar todas las maneras de escribir 2003 como suma de dos cuadrados.
(Fase local, 2004)
Solución:
a) Dado un número n , es congruente con 0, 1, 2, ó 3 módulo 4. Nos basta con analizar
cada una de las cuatro opciones.
Si n  0mod .4 , entonces n 2  0mod .4
Si n  1mod .4 , entonces n 2  1mod .4
Si n  2mod .4 , entonces n 2  0mod .4
Si n  3mod .4 , entonces n 2  1mod .4
b) Vamos a ver que no hay ninguna manera.
2003  500  4  3 , luego 2003  3mod .4
Y como por el apartado anterior, la suma de dos cuadrados sólo puede ser
congruente con 0, 1, ó 2, es imposible que haya dos números que cumplan el
enunciado.
5