Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Vamos a comenzar probando que, si $0\leq e_1\lt e_2\lt\ldots\lt e_k$ son enteros, entonces se cumple que \[f(2^{e_1}+2^{e_2}+\ldots+2^{e_k})=(-1)^{e_1}+(-1)^{e_2}+\ldots+(-1)^{e_k}.\] Como todo entero positivo se expresa de forma única como suma de potencias distintas de $2$ (pensemos en el número escrito en el sistema binario), lo anterior nos determina completamente a $f$. Observamos también que $0$ es par, luego $f(0)=0$. Para ver cómo se nos puede ocurrir la fórmula anterior, véase la nota más abajo.

Vamos a probar la fórmula anterior por inducción sobre el número de sumandos $k$. Si $k=1$, entonces $f(2^{e_1})=(-1)^{e_1}f(1)$ aplicando reiteradamente la definición de $f(n)$ para $n$ par. Además, se tiene que $f(1)=f(0)+1=1$, lo que prueba que $f(2^{e_1})=(-1)^{e_1}$, como queríamos. Supongamos entonces que la igualdad es cierta para $k-1$ sumandos y demostrémosla para $k$ sumandos. Suponiendo que $e_1$ es el exponente más pequeño (como arriba), tenemos que \begin{align*} f(2^{e_1}+2^{e_2}+\ldots+2^{e_k})&=(-1)^{e_1}f(1+2^{e_2-e_1}+\ldots+2^{e_k-e_1})\\ &=(-1)^{e_1}(1+f(2^{e_2-e_1}+\ldots+2^{e_k-e_1}))\\ &\stackrel{(\star)}{=}(-1)^{e_1}(1+(-1)^{e_2-e_1}+\ldots+(-1)^{e_k-e_1})\\ &=(-1)^{e_1}+(-1)^{e_2}+\ldots+(-1)^{e_k}, \end{align*} donde en el la igualdad $(\star)$ se ha usado la hipótesis de inducción.

Teniendo en cuenta lo anterior y que $2\equiv -1\ (\text{mod }3)$ tenemos claramente el apartado (a). Si expresamos $n=2^{e_1}+\ldots+2^{e_k}$ como suma de potencias distintas de $2$, entonces \[f(n)=(-1)^{e_1}+\ldots+(-1)^{e_k}\equiv 2^{e_1}+\ldots+2^{e_k}=n\ (\text{mod }3),\] luego $f(n)$ es múltiplo de $3$ si y sólo si lo es $n$.

En cuanto al apartado (b), cada potencia de $2$ de exponente par suma una unidad y cada potencia de exponente impar resta una unidad, luego el menor $n$ tal que $f(n)=2017$ será la suma de las primeras $2017$ potencias de $2$ pares, es decir, la solución que buscamos es \[n=2^0+2^2+2^4+\ldots+2^{2\cdot 2016}=1+4+4^2+\ldots+4^{2016}=\frac{4^{2017}-1}{3},\] donde hemos usado la fórmula para la suma de los términos de una progresión geométrica.

Nota. Veamos cómo justificar la idea feliz con la que empieza la solución. Supongamos que el número $n$ está escrito en el sistema binario, únicamente con ceros y unos. Hagamos algunas observaciones previas:

• Por un lado, $n$ es par cuando su último dígito es $0$, en cuyo caso $\frac{n}{2}$ consiste en eliminar ese cero. Por lo tanto, si $n$ termina en $r$ ceros, tendremos que es múltiplo de $2^r$ y $f(n)=(-1)^rf(\frac{n}{2^r})$, donde ahora hay que calcular $f$ sobre el número $\frac{n}{2^r}$, que consiste en eliminar esos $r$ ceros de la expresión de $n$.
• Por otro lado, $n$ es impar cuando su último dígito es $1$ y ahora $n-1$ consiste en cambiar ese $1$ por un $0$. Por tanto, $f(n)=f(n-1)+1$ reduce el problema a calcular $f$ sobre un número que termina en ceros y aplicar el caso previo.
• Los pasos anteriores reducen progresivamente el número de dígitos de $n$ hasta llegar a un punto en que es necesario calcular $f(0)$. Por la propia ecuación, como $0$ es par, tendremos que $f(0)=-f(0)$, luego $f(0)=0$ necesariamente.

De esta forma, no es difícil convencerse de que para calcular $f(n)$, sólo hay que leer $f$ en binario de derecha a izquierda, sumando $1$ por cada $1$ que vayamos encontrando y multiplicando por $(-1)^{r+1}$ siempre que nos encontremos $r$ ceros seguidos. Esto se resume en que cada $1$ que aparece introduce realmente un sumando $(-1)^{s+1}$, siendo $s$ la posición en la que aparece y podemos intuir así que cada sumando $2^s$ se transforma en un sumando $(-1)^s$.

Solución. Escribamos la progresión aritmética como $a_n=c+(n-1)d$ y la progresión geométrica como $g_n=cr^{n-1}$. Aquí estamos reflejando que ambas sucesiones tienen término inicial común $a_1=g_1=c$ y denotamos por $d$ a la diferencia de la progresión aritmética y por $r$ a la razón de la progresión geométrica. Entonces, podemos escribir las otras dos condiciones que nos dan como \begin{align*} a_2&=g_2&\Leftrightarrow&& c+d&=cr&\Leftrightarrow& &r=1+\frac{d}{c}\\ a_{10}&=g_3&\Leftrightarrow&& c+9d&=cr^2&\Leftrightarrow&& r^2=1+9\frac{d}{c}, \end{align*} donde hemos usado que $c\neq 0$ por hipótesis. Igualando la segunda ecuación con el cuadrado de la primera tenemos que \[1+9\frac{d}{c}=\left(1+\frac{d}{c}\right)^2=1+2\frac{d}{c}+\frac{d^2}{c^2}\ \Leftrightarrow\ \frac{d}{c}=7,\] donde hemos usado que $d\neq 0$ ya que en tal caso la sucesión aritmética sería constante y, por tanto, $g_1=a_1=a_2=g_2$ y la geométrica también lo sería en contra de lo que nos dice el enunciado. Esto nos lleva a que $r=1+\frac{d}{c}=8$.

Por lo tanto, tenemos que responder si, para cada entero positivo $p$, existe un entero positivo $m$ tal que $8^{p-1}=1+7(m-1)$. Esto es verdad ya que $8^{p-1}\equiv 1^{p-1}=1\pmod{7}$ para todo $p\geq 1$. Por lo tanto, la respuesta a la pregunta que nos hacen es afirmativa.

Solución. Si dividimos $x$ entre $240$, podemos escribir $x=240m+y$ con resto $0\leq y\lt 240$. Dividiendo $y$ entre $40$, podemos escribir $y=40n+z$ con resto $0\leq z\lt 40$. Dividiendo $z$ entre $8$ podemos escribir $z=8k+r$ con resto $0\leq r\lt 8$. Esto nos dice que $x=240m+40n+8k+r$ para ciertos enteros no negativos tales que $y=40n+8k+r\lt 240$, $z=8k+r\lt 40$ y $r\lt 8$, por lo que podemos calcular \begin{align*} \left\lfloor\frac{x}{8}\right\rfloor+\left\lfloor\frac{x}{40}\right\rfloor+\left\lfloor\frac{x}{240}\right\rfloor &=\left\lfloor\tfrac{240m+40n+8k+r} {8}\right\rfloor+\left\lfloor\tfrac{240m+40n+8k+r}{40}\right\rfloor+\left\lfloor\tfrac{240m+40n+8k+r}{240}\right\rfloor\\ &=\left\lfloor 30m+5n+k+\tfrac{r} {8}\right\rfloor+\left\lfloor 6m+n+\tfrac{z}{40}\right\rfloor+\left\lfloor m+\tfrac{y}{240}\right\rfloor\\ &=30m+5n+k+6m+n+m=37m+6n+k. \end{align*} Tenemos entonces que encontrar la solución de $37m+6n+k=210$ que minimiza $x=240m+40n+8k+r$. Esto nos lleva a elegir directamente $r=0$ ya que $r$ no interviene en la ecuación. Observemos que tenemos la restricción $0\leq n\leq 5$ y $0\leq k\leq 4$, luego $0\leq 6n+k\leq 34$. Así, dividiendo $210$ entre $37$, tenemos $210=5\cdot 37+25$ y deducimos que ha de ser $m=5$, lo que nos deja con $6n+k=25$. La única posible solución positiva con $0\leq k\leq 4$ es $n=4$ y $k=1$. Por tanto, el menor valor posible de $x$ es $240\cdot 5+40\cdot 4+8\cdot 1+0=1368$.

Nota. Esta demostración nos dice que el único grado de libertad que tenemos es $r$ entre $0$ y $7$, luego los únicos $x$ que cumplen esta ecuación son 1368, 1369, 1370, 1371, 1372, 1373, 1374 y 1375.

Solución. Veamos lo que ocurre con los primeros socios, para entender la regla general:

• El primer socio paga $1$ según el enunciado
• El segundo socio le tiene que pagar al primero $2$.
• El tercer socio le tiene que pagar el primer socio $2$ y al segundo $3$.
• El cuarto socio le tiene que pagar al primero $2$, al segundo $3$ y al tercero $6$.
• El quinto socio le paga al primero $2$, al segundo $3$, al tercero $6$ y al cuarto $12$.

Si ponemos que $a_k$ es lo que paga el socio $k$-ésimo, entonces el $n$-ésimo pagará \begin{align*} a_n&=a_1+a_2+\ldots+a_{n-1}+(n-1)\\ &=2a_1+2a_2+\ldots+2a_{n-2}+(n-2)+(n-1)\\ &=4a_1+4a_2+\ldots+4a_{n-3}+2(n-3)+(n-2)+(n-1)\\ &=\ldots\\ &=2^{n-2}a_1+2^{n-3}\cdot 1+2^{n-4}\cdot 2+\ldots+2^1(n-3)+2^0(n-2)+(n-1) \\ &=2^{n-2}+n-1+[2^{n-3}\cdot 1+2^{n-4}\cdot 2+2^{n-5}\cdot 3+\ldots+2^1(n-3)+2^0(n-2)]. \end{align*} La suma entre corchetes es aritmético-geométrica y puede obtenerse el resultado multiplicando por $2$ su expresión para aumentar cada exponente en una unidad y después restar la expresión original. Para $n\geq 2$, tenemos entonces que \begin{align*} a_n=2a_n-a_n&=2^{n-1}+2(n-1)+[2^{n-2}\cdot 1+2^{n-3}\cdot 2+2^{n-4}\cdot 3+\ldots+2^2(n-3)+2^1(n-2)]\\ &\qquad -2^{n-2}-(n-1)-[2^{n-3}\cdot 1+2^{n-4}\cdot 2+2^{n-5}\cdot 3+\ldots+2^1(n-3)+2^0(n-2)]\\ &=2^{n-2}+n-1+[2^{n-2}+2^{n-3}+2^{n-4}+\ldots+2^2+2^1]-(n-2)\\ &=2^{n-2}+2^{n-2}+2^{n-1}+2^{n-2}+\ldots+2^2+2^1+1=3\cdot 2^{n-2}-1, \end{align*} luego el $n$-ésimo socio ($n\geq 2$) ha de abonar un total de $3\cdot 2^{n-2}-1$ euros.