IX OIM 1994

Demostrar que todo número natural $n\leq 2^{1000000}$ puede ser obtenido a partir de 1 haciendo menos de 1100000 sumas; más precisamente: que hay una sucesión finita de números naturales $x_0, x_1,\ldots,x_k$, con $k < 1100000$, $x_0 = 1, x_k = n$ tal que para cada $i = 1, 2,\ldots, k$, existen $r, s$ con $0\leq r < i, 0 \leq s < i$, y $x_i = x_r + x_s$.

Sean $n, r$ dos enteros positivos. Se desea construir $r$ subconjuntos $A_1, A_2,\ldots, A_r$ de $\{0, 1,\ldots, n-1\}$ cada uno de ellos con exactamente $k$ elementos y tales que, para cada entero $x$, $0\leq x \leq n-1$, existen $x_1$ en $A_1$, $x_2$ en $A_2$ ,... , $x_r$ en $A_r$ (un elemento en cada conjunto) con $x = x_1 + x_2\dots+ x_r$. Hallar el menor valor posible de $k$ en función de $n$ y $r$.

Se dan los puntos $A, B, C$ sobre una circunferencia $K$ de manera que el triángulo $ABC$ sea acutángulo. Sea $P$ un punto interior a $K$. Se trazan las rectas $AP, BP, CP$, que cortan de nuevo a la circunferencia en $X, Y, Z$. Determinar el punto $P$ que hace equilátero al triángulo $XYZ$.

En cada casilla de un tablero $n\times n$ hay una lámpara. Al ser tocada una lámpara, cambian de estado ella misma y todas las lámparas situadas en la fila y la columna que ella determina (las que están encendidas se apagan y las apagadas se encienden). Inicialmente todas están apagadas. Demostrar que siempre es posible, con una sucesión adecuada de toques, lograr que todo el tablero quede encendido y encontrar, en función de $n$, el número mínimo de toques para que se enciendan todas las lámparas.

Dado un cuadrilátero inscrito en una circunferencia, sus vértices se denotan consecutivamente por $A, B, C, D$. Se supone que existe una semicircunferencia con centro en $AB$, tangente a los otros tres lados del cuadrilátero.

• i) Demostrar que $AB = AD + BC$.
• ii) Calcular, en función de $x = AB, y = CD$, el área máxima que puede alcanzar un cuadrilátero que satisface las condiciones del enunciado.

Se dice que un número natural $n$ es "sensato" si existe un entero $r$, con $1 < r < n-1$, tal que la representación de $n$ en base $r$ tiene todas sus cifras iguales. Por ejemplo, 62 y 15 son sensatos, ya que 62 es 222 en base 5 y 15 es 33 en base 4.  Demuestre que 1993 no es sensato pero 1994 si lo es.