Problemas y Soluciones de la 24 OIM Pa´ıses que mandaron problemas Problema 1 - M´exico - Efr´en P´erez Terrazas Problema 2 - M´exico - Ju´an Jos´e Alva Gonz´alez Problema 3 - El Salvador - Eder Alexander Jacobo Ar´evalo Problema 4 - M´exico - Eduardo Velasco Barreras Problema 5 - Argentina - Equipo Argentino Problema 6 - Argentina - Equipo Argentino Problema 1 M´exico Sea n un natural mayor que 2. Supongamos que n islas est´an ubicadas en un c´ırculo y que entre cada dos islas vecinas hay dos puentes como en la figura: xn x3 x1 x2 xn−1 xj Comenzando en la isla x1, ¿de cu´antas maneras se pueden recorrer los 2n puentes pasando por cada puente exactamente una vez? Soluci´on. Es claro que existe simetr´ıa entre comenzar el recorrido “en el sentido opuesto al de las manecillas del reloj” (sentido anti-horario o lev´ogiro), o bien comenzarlo “en el sentido de las manecillas del reloj”(sentido horario o dextr´ogiro). Por consiguiente, bastar´a 12 Problemas y Soluciones de la 24 OIM con conocer cuantos caminos hay en la gr´afica que recorren todas las aristas y cada una de ellas una sola vez, que empiezan en x1 y que recorren su primer arista en el sentido horario y al resultado multiplicarlo por 2 Se denotar´a por x2 al v´ertice que se encuentra al final de la primera arista y por x3, . . . , xn a los dem´as v´ertices que se van encontrando al recorrer la circunferencia en el sentido horario. xn x3 x1 x2 xn−1 xj Se dice que xj es un v´ertice de rebote (o bien, que hay un rebote en xj) si desde x1 se avanza hasta xj y luego se regresa a x1 por la direcci´on opuesta, es decir que para 1 < j n hay un rebote en xj si el camino da origen a la sucesi´on de v´ertices x1 − x2 − · · · − xj−1 − xj − xj−1 − · · · − x2 − x1 y si el rebote es en x1 entonces se tiene una sucesi´on de v´ertices x1 − x2 − · · · − xn − x1 − xn − · · · − x2 − x1. Es inmediato que hay 2 × 2 × 2 × · · · × 2 | {z } j−1 ×1 × 1 × · · · × 1 | {z } j−1 = 2j−1 caminos desde x1 hasta x1 determinados por el v´ertice de rebote xj , pues hay dos aristas por elegir en cada v´ertice xi con i 2 {1, . . . , j − 1} al desplazarse hasta xj , mientras que en el desplazamiento de regreso solamente queda una opci´on en cada v´ertice. Si xj es un v´ertice de rebote entonces, para poder recorrer todo la gr´afica pasando una sola vez por cada arista, es necesario que ahora se realice un camino hasta xj en el sentido anti- horario y luego un camino de regreso hasta x1 en el sentido horario, es decir que ahora hay una sucesi´on de v´ertices x1 −xn −xn−1 −· · ·−xj+1 −xj −xj+1 −· · ·−xn−1 −xn −x1, para la cual hay 2 × 2 × 2 × · · · × 2 | {z } n−j+1 ×1 × 1 × · · · × 1 | {z } n−j+1 = 2n−j+1 caminos. Por consiguiente hay n (2n) caminos con rebote que comienzan en x1 y que su primer arista se recorre en el sentido horario. 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.Problemas y Soluciones de la 24 OIM 3 Solamente queda considerar el caso en que no hay rebotes, es decir que hay una sucesi´on de v´ertices x1 − x2 − · · · − xn − x1 − x2 − · · · − xn − x1, para la cual tambi´en hay 2n caminos posibles. Se concluye que existen 2n(n+1) caminos que empiezan en x1 y cuya primer arista se recorre en el sentido horario, por lo que la respuesta es 2 · 2n (n + 1) = 2n+1 (n + 1) . Problema 2 M´exico Para cada entero positivo n se define an = n + m donde m es el mayor entero tal que 22m n2n. Determinar qu´e enteros positivos no aparecen en la sucesi´on an. Soluci´on. Realizando las cuentas, se ve que los primeros t´erminos de la sucesi´on son 1,3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, . . ., por lo que se demostrar´a que la respuesta son los naturales que no son potencias de 2. Depende del primer momento en que m cambia el que un n´umero aparezca o no en la sucesi´on. Ahora bien, en la lista mostrada, se ve que a2−1, a22−2 y a23−3 son los elementos de la sucesi´on previos a un “salto”. Si n = 2k − k, entonces n2n 22k y log2 (n) < k. Luego log2 (n) + n < k + 2k − k = 2k, y n2n < 22k , por lo que a2k−k < 2k. (1) Si n = 2k−k+1, entonces 22k n2n. Como 2k−1 > k−1 se tiene que 2k−k+1 > 2k−1, y as´ı log2 (n) > k−1. Se sigue de las identidades previas que n+log2 (n) > k−1+2k−k+1 = 2k, luego n2n > 22k , por lo que a2k−k+1 2k + 1. (2) Es f´acil ver que si 22k > n2n, entonces 22k+1 > (n + 1) 2n+1, as´ı que an+1 − an 2. De este argumento y de las identidades (1) y (2) se obtiene que a2k−k = 2k − 1; a2k−k+1 = 2k + 1. (3) M´as a´un, como an+1 − an 1, las identidades (3) muestran que a2k−k+t = 2k + t para t 2 1, . . . , 2k − 1. Si no, de otra manera se tendr´ıa que a2k+1−(k+1) = a2k−k+2k−1 > 2k+1−1. Se concluye que en la sucesi´on aparecen todos los enteros positivos excepto los que son potencias de 2. Segunda Soluci´on Los primeros t´erminos de la sucesi´on son 1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, . . . , esto sugiere que la sucesi´on omite las potencias de 2 (mayores que 1). 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.4 Problemas y Soluciones de la 24 OIM Sea bn la sucesi´on formada por los enteros positivos que no son de la forma 2k con k 1 ordenados de manera creciente. Se mostrar´a que bn = an para todo n 1. Para n = 1 tenemos que b1 = 1 = a1. Ahora se considera n 2. Sea k el entero positivo tal que 2k n < 2k+1. Como n 2 y k es positivo, 2k < n + k < n + k + 1 < 2k+1 + k + 1 < 2k+2. Esto muestra que n + k est´a entre las potencias 2k y 2k+2. Hay dos casos: 1. 2k < n + k < 2k+1 Esto implica que n + k + 1 2k+1. De los n + k enteros del conjunto {1, 2, . . . , n + k} exactamente k de ellos son potencias de 2: 21, 22, . . . , 2k (pues 2k+1 > n + k), por lo que los restantes n enteros son los primeros n t´erminos de la sucesi´on bj . Esto dice que bn es el ´ultimo entero del conjunto {1, 2, . . . , n + k} que no es potencia de 2. Pero en este caso que se analiza, n + k no es potencia de 2, por lo que bn = n + k. Por otra parte, de las desigualdades que satisfacen n y k, tenemos que 22k < 2n+k = 2k2n n2n < 2k+12n = 2n+k+1 22k+1. Entonces k es el mayor entero tal que 22k n2n, por lo que an = n + k y entonces an = bn. 2. 2k+1 n + k < 2k+2 En este caso sucede que 2k+1 n+k < n+k+1 < 2k+2. Aqu´ı de los n+k+1 enteros positivos del conjunto {1, 2, . . . , n + k + 1} exactamente k + 1 de ellos son potencias de 2, por lo que los restantes n son los primeros n t´erminos de la sucesi´on bj . Luego bn es el ´ultimo entero del conjunto {1, 2, . . . , n + k + 1} que no es potencia de 2. Pero n + k + 1 no es potencia de 2, por lo que bn = n + k + 1. Por otra parte, de las desigualdades que satisfacen n y k, tenemos que 22k+1 2n+k = 2k2n n2n < 2k+12n = 2n+k+1 < 22k+2. Entonces k + 1 es el mayor entero tal que 22k+1 n2n, por lo que an = n + k + 1 = bn. Problema 3 El Salvador Sean C1 y C2 dos circunferencias de centros O1 y O2 con el mismo radio, que se cortan en A y en B. Sea P un punto sobre el arco AB de C2 que est´a dentro de C1. La recta AP corta a C1 en C, la recta CB corta a C2 en D y la bisectriz de \CAD intersecta a C1 en E y a C2 en L. Sea F el punto sim´etrico a D con respecto al punto medio de PE. Demostrar que existe un punto X que satisface \XFL = \XDC = 30y CX = O1O2. Soluci´on. Observemos primero que, puesto que F es el sim´etrico de D con respecto al punto medio de PE, se tiene que las diagonales del cuadril´atero FPDE se intersectan en su punto medio. Por tanto, FPDE es un paralelogramo. As´ı que FP = ED. Ahora bien, como las circunferencias son iguales y AB es la cuerda com´un, AB abre el mismo arco en ambas circunferencias. De aqu´ı que \ACB = \ADB. Entonces el tri´angulo ACD es is´osceles. Como AL es bisectriz del \CAD, se tiene que AL es la mediatriz de 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.Problemas y Soluciones de la 24 OIM 5 CD. Adem´as, puesto que \CAE = \LAD, las cuerdas CE y LD son iguales. Observemos que \BCA = \BAE = \BDL por abrir arcos iguales. Concluimos que CE es igual y paralela a DL. As´ı que ECLD es un paralelogramo. De aqu´ı que CL es igual y paralela a DE. Por tanto, CL es igual y paralela a FP. Hemos demostrado que FPCL tambi´en es un paralelogramo. Como CD es perpendicular a EL, EDCL es un rombo. As´ı que ED = DL = LC = CE. Observemos que PL = LD pues \PAL = \LAD. Concluimos que FC = PL = LD = LC = FP. Puesto que LD = CE y las circunferencias son iguales, los tri´angulos O1CE y O2LD son congruentes. Como LD es paralela a CE concluimos que O1C es paralela O2L. Esto muestra que O1O2LC es un paralelogramo. De aqu´ı que O1O2 = CL = LD = FC. Ahora bien, sea X un punto tal que el tri´angulo LCX es equil´atero. Como CF = CL = CX, C es el circuncentro de FLX. De aqu´ı que \LFX = 12\LCX = 1260= 30. Hemos mostrado que X cumple lo que se pide. Problema 4 M´exico Sea ABC un tri´angulo con AB 6= AC. Sean I el incentro de ABC y P el otro punto de intersecci´on de la bisectriz exterior del ´angulo A con el circunc´ırculo de ABC. La recta PI intersecta por segunda vez al circunc´ırculo de ABC en el punto J. Demostrar que los circunc´ırculos de los tri´angulos JIB y JIC son tangentes a IC y a IB, respectivamente. Soluci´on. Sea M el punto de intestecci´on de AI con el circunc´ırculo de ABC. Como AM y AP son la bisectriz interior y exterior del ´angulo A, entonces forman un ´angulo recto en A. Por tanto, \PMA = 90− \APM. Pero \APM = \ACM = \ACB + \BCM = \C + \BAM = \C + 12\A. Concluimos que \PMA = 90− \C − 12\A = 12 (\B − \C). Por otro lado, \BJP = \BCP = \BCA + \ACP = \BCA + \AMP = \C + 12 (\B − \C) = 12 (\B +\C) = \IBC +\ICB. Es decir, \BJP es igual al ´angulo externo en I del tri´angulo IBC. Esto muestra que CI es tangente al circunc´ırculo del JIB. An´alogamente, se tiene que BI es tangente al circunc´ırculo de JIC. Segunda Soluci´on Como AP es bisectriz exterior del ´angulo en A, se tiene que P es el punto medio del arco dBC que contiene a A. Sean C1 la circunferencia tangente a CI en I que pasa por B y C2 la circunferencia tangente a BI en I que pasa por C. Sea K el segundo punto de intersecci´on, distinto de I, de C1 con C2. Veamos que K = J. Como C1 es tangente a CI, \BKI es igual al ´angulo exterior en I del tri´angulo BIC. Es decir, \BKI = \IBC + \ICB = 12 (\B + \C). An´alogamente, \CKI = 12 (\B + \C). Por tanto, \BKC = \BKI +\CKI = 2( 12 (\B +\C)) = \B +\C = 180−\A. De aqu´ı que el cuadril´atero ABKC es c´ıclico. Entonces K pertenece al arco dBC, del circunc´ırculo del tri´angulo ABC, que no contiene a A. Adem´as, puesto que \BKI = 12 (\B +\C) = \CKI, KI es bisectriz del ´angulo \BKC. Por lo tanto, KI pasa por el punto medio del arco BC opuesto a K. Es decir, K, I y P son colineales. As´ı que K = J. Tercera Soluci´on Observemos que, como AP es bisectriz exterior del ´angulo en A, entonces P es el punto medio del arco dBC que contiene a A. De aqu´ı que \BJP = \PJC. Pero 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.6 Problemas y Soluciones de la 24 OIM \BJP + \PJC = \BJC = 180− \A = \B + \C. Por lo que \BJP = \PJC = 12 (\B +\C). Adem´as, el ´angulo exterior del \BIC mide \IBC +\ICB = 12 (\B +\C) = \BJP = \PJC. El resultado se sigue por el teorema del ´angulo semi-inscrito. Problema 5 Argentina La sucesi´on an est´a definida por a1 = 1, a2k = 1 + ak y a2k+1 = 1 a2k , para todo entero k 1. Demostrar que todo n´umero racional positivo aparece exactamente una vez en esta sucesi´on. Soluci´on. Es claro que a2k > 1 y a2k+1 2 (0, 1) si k > 0. Ahora a1 = 1, a2 = 2, a3 = 1/2. Sea u/v un n´umero racional positivo con u y v coprimos. Se probar´a por inducci´on sobre s = u + v que ak = u/v para alg´un k. Como se ha visto, esto se cumple para s = 2 y s = 3. Si u/v > 1 se considera al n´umero u/v − 1 = (u − v)/v. Observe que u − v y v son coprimos y que la suma de ellos es (u − v) + v = u < s, por hip´otesis de inducci´on se tiene que ak = (u − v)/v para alg´un k. Por lo tanto, a2k = 1 + ak = u/v. Si u/v < 1, entonces v/u > 1. Por un argumento como el anterior, existe k tal que ak = v/u−1 = (v−u)/u. Por lo tanto, a2k = 1 + ak = v/u, y entonces a2k+1 = 1/a2k = u/v. Para ver que dado un racional positivo u/v hay s´olo un k tal que ak = u/v, supongase que no es as´ı y sea u/v un racional tal que ai = aj = u/v, i < j, con i m´ınimo con esta propiedad. Entonces, los dos indices i y j tienen la misma paridad (y los dos son pares si u/v > 1, y los dos son impares si u/v < 1). Si son los dos pares, con i = 2i0, j = 2j0, tenemos que ai = a2i0 = 1 + ai0 y aj = a2j0 = 1 + aj0 , por lo tanto ai0 = aj0, contradiciendo la manera de escoger i. Si son los dos impares con i = 1, entonces aj = 1, y esto puede pasar si y s´olo si j = 1. Si i > 1, entonces i = 2i0 + 1, j = 2j0 + 1, ai = 1/a2i0 , aj = 1/a2j0, y se obtiene que a2i0 = a2j0 , una vez m´as se contradice la minimalidad de i. Segunda Soluci´on Si se escribe la representaci´on binaria de n como n = 20 + 20+1 + · · · + 20+···+s donde s 0, 0 0 y 1, . . . , s positivos, se puede mostrar f´acilmente por inducci´on que an = [0, 1, . . . , s−1, s + 1], (4) donde se utiliza la notaci´on [b0, b1, b2 . . . , bt] para la fracci´on continua b0 + 1 b1 + 1 b2 + · · · + 1 bt−1 + 1bt . (5) 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.Problemas y Soluciones de la 24 OIM 7 En efecto, si s = 0 se tiene a20 = 1 + a20−1 = 2 + a20−2 = · · · = 0 + a1 = 0 + 1 = [0 + 1], lo que prueba la f´ormula (4) para s = 0. Suponiendo que s > 0 y escribiendo m = 21 + 21+2 + · · · + 21+···+s , se tiene que n = 20(1 + m). Como m es par, obtenemos an = 1 + a20−1(1+m) = · · · = 0 + a1+m = 0 + 1 am. Ahora la f´ormula (4) se sigue f´acilmente por inducci´on sobre m, ya que el n´umero de suman- dos binarios de m es < s. Ahora la conclusi´on del problema se sigue del hecho conocido que cada n´umero racional admite una representaci´on en fracci´on continua como aquella que aparece en el lado derecho de (4) que adem´as es ´unica ya que para s 0 se tiene que s+1 > 1 (sin esta condici´on, cualquier n´umero racional admite de hecho dos representaciones como una fracci´on continua que son [b0, . . . , bs−1, bs] = [b0, . . . , bs−1, bs − 1, 1] para bs > 1). Problema 6 Argentina Alrededor de una circunferencia se marcan 6000 puntos y cada uno se colorea con uno de 10 colores dados, de manera tal que entre cualesquiera 100 puntos consecutivos siempre figuran los 10 colores. Hallar el menor valor k con la siguiente propiedad: Para toda coloraci´on de este tipo existen k puntos consecutivos entre los cuales figuran los 10 colores. Soluci´on. El menor valor es k = 89. Veamos primero que, en toda coloraci´on con las caracteristicas del enunciado, los 10 colores est´an presentes en alg´un arco de longitud 89. Aqu´ı, y en lo que sigue, un arco de longitud ` significa ` puntos consecutivos alrededor de la circunferencia. Siempre supondremos que la direcci´on del movimiento alrededor de la circunferencia es en el sentido del reloj. Supongamos por el contrario que para alguna coloraci´on, ning´un arco de longitud 89 contiene todos los 10 colores. Entonces suceder´a lo siguiente: (i) en cada arco de longitud 11 hay un color que no figura entre los 89 puntos subsiguientes; (ii) cada arco de longitud 12 contiene precisamente 2 colores. Veamos porqu´e. Si (i) es falso para alg´un arco de longitud 11, en los 89 puntos subsiguientes tienen que estar presentes los 10 colores (pues en cada arco de longitud 100 figuran todos los colores), lo que es contrario a lo supuesto. Para ver (ii), dividimos cualquier arco de longitud 100 en 9 arcos A1, . . . ,A9, los primeros 8 de longitud 11 cada uno y A9 de longitud 12. Por (i), para cada i = 1, . . . , 8 existe un color i en Ai que no figura en Ai+1, . . . ,A9. 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.8 Problemas y Soluciones de la 24 OIM Claramente, los colores 1, . . . , 8 son distintos, luego hay a lo m´as 10 − 8 = 2 colores en A9. En este argumento A9 puede ser cualquier arco de longitud 12 de la circunferencia. Entonces cada arco de longitud 12 contiene a lo m´as 2 colores. En realidad contiene exacta- mente 2 colores. En efecto, si alg´un arco de longitud 12 tienen todos sus puntos del mismo color, consideremos A junto con el arco B de longitud 88 que sigue a A. En el arco A [ B figuran los 10 colores de modo que B y el ´ultimo punto de A forman un arco de longitud 89 en el que figuran los 10 colores, en contradicci´on con nuestro supuesto. Entonces (ii) es verdadero. Ahora tomemos un punto p0 del color 0 que no figura en los siguientes 89 puntos. Tal punto existe, en virtud de (i). Los 11 puntos subsiguientes a p0 forman un arco A1. En el arco {p0} [ A1 de longitud 12, hay exactamente 2 colores, por (ii). Uno de ellos es el color 0; llamemos al otro color 1. Adem´as, por la elecci´on de p0, en A1 no figura el color 0. Luego todo el arco A1 es de color 1. Ahora, (i) garantiza que el color 1 no aparece en los subsiguientes 89 puntos siguientes al ´ultimo punto p1 de A1. Exactamente el mismo argumento se aplica a p1 y al subsiguiente arco A2 de longitud 11. Entonces el arco A2 contiene un ´unico color, que adem´as no figura entre los subsiguientes 89 puntos. Aplicando repetidas veces el mismo razonamiento se ve que la circunferencia se divide en arcos de longitud 11 con todos los puntos del mismo color en cada arco. Sin embargo esto es imposible, pues el n´umero total de puntos, 6000, no es un m´ultiplo de 11. Por lo tanto, hay un arco de longitud 89 en el que figuran los 10 colores. El siguiente ejemplo muestra que la longitud 88 no es suficiente para garantizar esto en general. Dados 10 colores denotados por 0, . . . , 9, tomamos los siguientes 10 arcos A0, . . . ,A9, cada uno de longitud 12: A0 = 000101101000, A1 = 111212212111, . . . , A8 = 888989989888, A9 = 999090090999. El arco Ai+1 se obtiene del arco Ai por desplazamiento c´ıclico i 7! i + 1 de los colores. Repetimos el patr´on A0, . . . ,A9, 50 veces para obtener una coloraci´on con 10 colores de los 6000 puntos alrededor de la circunferencia. Esto es posible, pues 6000 = 50 · 120. Sea A cualquier arco de longitud 100 de esta coloraci´on. Por la periodicidad podemos suponer que A comienza con un punto de un arco A0, entonces contiene con certeza el color 0. Luego A contiene los arcos completos A1, . . . ,A7 que siguen a A0, y al menos cuatro puntos del arco A8. Como el cuarto punto de A8 tiene color 9, y como los colores 1, . . . , 8 figuran en A1, . . . ,A7, concluimos que A contiene los 10 colores. Ahora tomemos cualquier arco B de longitud 88 y supongamos de nuevo que comienza en un punto de un arco A0. Consideremos los siguientes arcos A1, . . . ,A8. El ´ultimo punto de B est´a, o bien entre los 9 ´ultimos puntos de A7, o bien entre los primeros tres puntos de A8, que tienen color 8. Como A0, . . . ,A7 no contienen el color 9, se infiere que tampoco lo contiene el arco B. La demostraci´on est´a completa. 24 Olimpiada Iberoamericana de Matem´aticas, M´exico.