Teoría de números (nivel 1) Lección 3. Los números y sus dígitos
Hay muchos problemas en los que se relacionan los números y las cifras que lo representan en el sistema decimal. Es importante empezar recordando que un núimero y sus cifras son dos cosas distintas. El número $1878$ tiene tres cifras: el $1$, el $8$, el $7$ y el $8$, que son cuatro números que tienen sentido por sí mismos y pueden estar sujetos a otras operaciones en las que no interviene el número $1878$. Por ejemplo, la suma de las cifras es $1+8+7+8=24$ y, para hallarla, no hemos usado el $1878$ en ningún cálculo. Sabemos también que el sistema decimal es posicional y a cada cifra le corresponde un orden (unidades, decenas, centenas,...), de forma que el $1878$ se recupera a partir de sus cifras como
$$1878=1\cdot 1000+8\cdot 100+7\cdot 10+8.$$
Con esta expresión se puede escribir matemáticamente la relación entre un número y sus cifras, lo que permite abordar la mayoría de los problemas de este tipo. Más explícitamente, un número natural $N$ de $k$ cifras se puede expresar como
$$N=10^{k-1}a_{k-1}+10^{k-2}a_{k-2}+\ldots+100a_2+10a_1+a_0$$
y cada dígito $a_{k-1},a_{k-2},\ldots,a_2,a_1,a_0$ es un número entre $0$ y $9$. Usualmente se suele tomar $a_{k-1}\neq 0$, en cuyo caso decimos que $k$ es el número de cifras de $N$.
Ejercicio resuelto
Con tres dígitos distintos se forman seis números distintos de tres cifras. Si se suman los seis números resulta 4218. Si se ordenan los seis números, la suma de los tres mayores menos la suma de los tres menores resulta 792. Halla los tres dígitos.
Solución
Pongamos que los dígitos son $a$, $b$ y $c$ y cumplen que $a>b>c$. Por tanto, los seis números ordenados de mayor a menor son
\begin{align*}
100a+10b+c&\gt 100a+10c+b\gt 100b+10a+c\\
&\gt 100b+10c+a\gt 100c+10a+b\gt 100c+10b+a.
\end{align*}
La suma de los seis números es
$$4218=100(2a+2b+2c)+10(2a+2b+2c)+(2a+2b+2c)=222(a+b+c),$$
de donde deducimos que $a+b+c=19$. La suma de los tres mayores menos la suma de los tres menores es
$$792=100(2a-2c)+(2c-2a)=198(a-c),$$
luego llegamos a que $a-c=4$. Distinguimos casos:
- Si $a=9$, entonces $c=5$ y, para que $a+b+c=19$, tendríamos que $b=5$, pero los dígitos tienen que ser distintos.
- Si $a=8$, entonces $c=4$ y, usando que $a+b+c=19$, obtenemos que $b=7$. Esta es una solución válida.
- Si $a\leq 7$, entonces $b\leq 6$ y $c\leq 3$, lo que nos da $a+b+c\leq 16$ y no puede ser que $a+b+c=19$.
Deducimos que los dígitos son $8$, $7$ y $4$.
A la hora de hacer operaciones elementales con números (sumas, restas, multiplicaciones y divisiones), usamos los dígitos en los distintos algoritmos. Podemos usar estos algoritmos para obtener información sobre los dígitos.
Ejercicio resuelto
Hallar el último dígito antes de la cola de ceros del número
$$19! + 20! + 21! +\ldots + 96! + 97!$$
(Olimpiada Matemática Argentina 1997, fase regional, problema 3)
Solución
El término $19!$ termina con tres ceros ya que es múltiplo de $1000$ (es múltiplo de $4\cdot 5\cdot 10\cdot 15=3000)$. Como $5$, $10$ y $15$ son los únicos factores múltiplos de $5$, el número $19!$ no puede ser múltiplo de $10000=2^45^4$, luego no termina en más de tres ceros. Ahora bien, la siguiente cifra en $19!$ tras estos tres ceros es el producto de las cifras de las unidades del resto de los factores:
\[1\cdot 2\cdot 3\cdot 4\cdot 6\cdot 7\cdot 9\cdot 11\cdot 12\cdot 13\cdot 14\cdot 3\cdot 16\cdot 17\cdot 18\cdot 19,\]
Multiplicando las cifras de las unidades de los números anteriores, llegamos a que esta es $2$, es decir, las últimas cuatro cifras de $19!$ son $2000$. Finalmente, observamos que todos los números $20!$, $21!$,..., $97!$ tienen más ceros finales que $19!$ ya que tienen, al menos, un factor $20$ adicional. Por tanto, las cuatro últimas cifras del número del enunciado son las mismas que las de $19!$, es decir, la solución al problema es $2$.
Un caso particular de acertijos que involucran a los dígitos de un número son los llamados criptoaritmos, en los que las incógnitas son los dígitos en operaciones aritméticas.
Ejercicio propuesto
En cada una de las siguientes operaciones, letras iguales representan dígitos iguales y un asterisco indica que se puede tratar de cualquier dígito. Encuentra el valor de todos los dígitos involucrados.
\[\begin{matrix}
&S&E&N&D\\
+&M&O&R&E\\\hline
M&O&N&E&Y\\
\end{matrix}\qquad \begin{matrix}
&&D&O&S\\
&&D&O&S\\
+&T&R&E&S\\\hline
S&I&E&T&E\\
\end{matrix}\qquad \begin{matrix}
&2&*&*\\
\times&&*&*\\\hline
&*&6&1\\
*&*&*&\\\hline
*&*&0&1
\end{matrix}\qquad \begin{matrix}
&a&b&c\\
-&c&b&a\\\hline
&c&a&b
\end{matrix}\]
(los dos primeros son criptoaritmos famosos, el tercero se propuso en la fase local de la Olimpiada Matemática Española y el cuarto en la Olimpiada Matemática Argentina).
Trabajando en otras bases
En todo lo anterior, el número $10$ se llama base y juega un papel fundamental ya que los números se expresan como combinaciones de potencias de $10$. El sistema posicional se ha consolidado porque con él podemos hacer algorítmicamente la mayoría de las operaciones y porque además permite representar números tan grandes como queramos. (Por ejemplo, ¿serías capaz de dividir MMMCDLXXXIII entre IX en números romanos sin pasar por los decimales? Investiga cómo lo hacían los romanos, si te interesa el tema.) Sin embargo, usar la base $10$ es simplemente un convenio que se heredó de las tradiciones india y arábe. Observa que también se usan otras bases como la base $2$ (binario), la base $8$ (octal) y la base $16$ (hexadecimal) en informática.
El concepto de base es muy simple si has entendido la base $10$: un número $N\geq 1$ tiene dígitos $a_{k-1},a_{k-2},\ldots,a_2,a_1,a_0$ en base $b\geq 2$ cuando se puede escribir como
$$N=a_{k-1}b^{k-1}+a_{k-2}b^{k-2}+\ldots+a_2b^2+a_1b+a_0.$$
siendo los dígitos números entre $0$ y $b-1$. Lo indicaremos utilizando un subíndice entre paréntesis. Esto quiere decir que, en base 2, todos los números se escriben con dígitos 0 y 1, en base 3 con dígitos 0, 1 y 2, y así sucesivamente. Por ejemplo, el número $201221_{(3)}$ es un número escrito en base $3$, que no es más que el número
\[\textcolor{red}{201221}_{(3)}=\textcolor{red}{2}\cdot 3^5 +\textcolor{red}{0}\cdot 3^4 +\textcolor{red}{1}\cdot 3^3 +\textcolor{red}{2}\cdot 3^2 +\textcolor{red}{2}\cdot 3^1
+\textcolor{red}{1}\cdot 3^0=538.\]
Es importante darse cuenta de que $201221_{(3)}$ y $538$ son el mismo número natural que simplemente está en dos formas diferentes. El resultado clave para entender las bases de numeración es el siguiente:
Ejercicio propuesto
Responde razonadamente a las siguientes preguntas:
- ¿Cómo se escribe el número $10202_{(3)}$ en base $5$?
- Si $73_{(b)}$ es exactamente el doble de $37_{(b)}$, ¿cuál es el valor de la base $b$?
- ¿Cuál es la menor base $b>10$ para la que $36_{(b)}$ es un cuadrado perfecto? ¿Y la menor base $b$ para la que $37_{(b)}$ no es un número primo?
- Si número natural se escribe como $xyy_{(7)}$ y como $yxx_{(6)}$, ¿cuál es el valor de los dígitos $x$ e $y$?
- Un número de tres cifras en base $104, se escribe como $xyz_{(7)}$ y como $zyx_{(9)}$. ¿Cuál es el número?
Teorema fundamental de la numeración
Todo entero $N\geq 1$ se expresa de forma única como
$$N=a_{k-1}b^{k-1}+a_{k-2}b^{k-2}+\ldots+a_2b^2+a_1b+a_0,$$
siendo $a_{k-1},a_{k-2},\ldots,a_2,a_1,a_0$ enteros entre $0$ y $b-1$.
Demostración
La demostración se divide en dos partes: demostrar que todo número se puede expresar de esa forma (existencia) y luego ver que la expresión es única (unicidad).
Existencia. Lo vamos a ver por inducción sobre $N$. Está claro que si $1\leq N\leq b-1$, el número $N$ se expresa con un único dígito en base $b$, por lo que supondremos que $N\geq b$ y lo reduciremos a un caso menor. Para ello, dividimos $N$ entre $b$ y obtenemos un cociente $q\geq 1$ y un resto $0\leq r\lt r$ tales que $N=bq+r$. Claramente, $q\leq N$, luego podemos escribir $q=a_{k-1}b^{k-1}+\ldots+a_2b^2+a_1b+a_0$ en base $b$ por hipótesis de inducción. Ahora basta darse cuenta de que
$$N=bq+r=a_{k-1}b^{k}+\ldots+a_2b^3+a_1b^2+a_0b+r$$
es una expresión de $N$ en base $b$.
Unicidad. Supongamos que un número $N$ se escribe de dos formas distintas y razonemos por reducción al absurdo:
$$N=a_{k-1}b^{k-1}+\ldots+a_2b^2+a_1b+a_0=c_{j-1}b^{j-1}+\ldots+c_2b^2+c_1b+c_0.$$
Esto puede ser porque ambas expresiones tengan distinto número de dígitos ($j\neq k$) o porque haya dígitos distintos. En cualquier caso, podemos dejar la mayor potencia de $b$ en uno de los dos miembros y pasar el resto de términos al otro, para llegar a una expresión del tipo
$$d_ib^i=d_{i-1}b^{i-1}+d_{i-2}b^{i-2}+\ldots+d_1b+d_0,$$
siendo $|d_r|=|a_r-c_r|\leq b-1$ (ya que $a_r$ y $c_r$ son números entre $0$ y $b-1$) y $|d_i|\neq 0$. Usando la desigualdad triangular, tenemos que
\begin{align*}
b^i&\leq |d_i|b^i=|d_ib_i|=|d_{i-1}b^{i-1}+d_{i-2}b^{i-2}+\ldots+d_1b+d_0|\\
&\leq|d_{i-1}|b^{i-1}+|d_{i-2}|b^{i-2}+\ldots+|d_1|b+|d_0|\\
&\leq(b-1)b^{i-1}+\ldots+(b-1)b+(b-1)\\
&=(b-1)(b^{i-1}+\ldots+b+1)=b^i-1.
\end{align*}
Esto es claramente una contradicción, luego hemos probado la unicidad.
La demostración anterior nos da de hecho una forma de pasar un número en base $10$ a una base cualquiera $b$ sin más que hacer divisiones euclídeas. Vamos a verlo con el número $538$ (que hemos visto hace un momento que se expresa como $201221_{(3)}$).
- Dividimos $538$ entre $3$: cociente $179$, resto $\textcolor{red}{1}$.
- Dividimos $179$ entre $3$: cociente $59$, resto $\textcolor{red}{2}$.
- Dividimos $59$ entre $3$: cociente $19$, resto $\textcolor{red}{2}$.
- Dividimos $19$ entre $3$: cociente $6$, resto $\textcolor{red}{1}$.
- Dividimos $6$ entre $3$: cociente $2$, resto $\textcolor{red}{0}$.
- Dividimos $2$ entre $3$: cociente $0$, resto $\textcolor{red}{2}$.
Como el cociente es $0$, hemos terminado. Ordenando, los restos obtenidos en sentido opuesto, tenemos el número $\textcolor{red}{201221}_{(3)}$.
En realidad, no es usual ver problemas de olimpiada en los que directamente se habla de expresiones en bases distintas (ya que se basa en conocimientos específicos que los participantes pueden no conocer), pero existen problemas en los que cambiar de base puede suponer una ayuda fundamental o en los que conocer la idea de cambio de base nos puede dar una idea feliz.
Ejercicio resuelto
Supongamos que $p(x)$ es un polinomio desconocido cuyos coeficientes son números naturales. Tenemos un programa de ordenador en el que podemos escribir un número $n$ y nos devuelve el resultado $p(n)$. ¿Cuántos números tenemos que suministrarle al programa para poder determinar cualquier polinomio con la información que nos devuelve?
Solución
Con dos valores es suficiente para determinar el polinomio en general. Supongamos que tenemos un polinomio dado por $p(x)=a_0+a_1x+\ldots+a_nx^n$ y queremos determinar $a_0,a_1,\ldots,a_n$ (y el propio $n$).
El primer número que le pasamos al programa es el $1$, que nos devuelve la suma $S=P(1)$ de todos los coeficientes. En particular, todos los coeficientes son menores o iguales que $S$. Supongamos que $10^k\gt S$, es decir, tomamos una potencia de $10$ mayor que $S$. Al evaluar $P(10^k)$ obtenemos
\[P(10^k)=a_0+10^ka_1+10^{2k}a_2+\ldots+10^{nk}a_n.\]
Este número contiene una copia de cada coeficiente separados en grupos de $k$ dígitos. Por ejemplo, si $p(x)=12+3x+88x^2+x^4$, evaluamos $p(1)=104$ y seguidamente evaluamos $p(1000)=1000088003012$, donde claramente se ven los coeficientes.
Finalmente, sabrías probar que dándole un solo valor al polinomio no es suficiente en general para determinarlo?
Ejercicio resuelto
Tenemos un conjunto de pesas de pesos enteros distintos que permiten pesar cualquier peso entero entre $1$ y $40$ en una balanza. ¿Es posible que sólo sean cuatro pesas?
Solución
La respuesta es que sí. Para demostrarlo, nos inspiraremos en la base $3$ y consideraremos pesas con pesos $1$, $3$, $9$ y $27$. Todos los números que se escriben sólo con ceros y unos en base $3$ se pueden pesar de forma directa, colocando los pesos correspondientes en el platillo opuesto al del objeto que queremos pesar (observemos que $40=1111_{(3)}$ es el mayor número que se puede pesar así). Ahora bien, si un número entre $2$ y $39$ tiene un dos en su representación en base $3$, basta echar pesas que complementan en el mismo platillo que el objeto. Por ejemplo, para un peso de $23=212_{(3)}$ que está en el platillo A, ponemos la pesa $1$ en A para eliminar el primer $2$, lo que nos da $24=220_{(3)}$. Ahora ponemos $3$ en A y nos queda un peso total de $27=1000_{(3)}$, luego basta poner la pesa de $27$ en el plato B.
Ejercicio propuesto
Consideremos todos los números naturales que son potencias de $5$ o bien que se expresan como suma de potencias de $5$ distintas. Si los ordenamos de menor a mayor, ¿qué número ocupa la posición $128$?
Operaciones con los dígitos
Hay algunos trucos para sacar información adicional sobre los dígitos, que a veces es suficiente para resolver un problema. Algunos de ellos los justificaremos en la siguiente lección, cuando estudiemos las congruencias:
- La cifra de las unidades de un número es el resto de dividirlo entre $10$.
- Para saber las últimas $k$ cifras de una suma o un producto, sólo es necesario saber las últimas $k$ cifras de los sumandos o de los factores.
- La suma de los dígitos de un número da el mismo resto al dividir entre 9 que el propio número.
- Un número $N\geq 1$ tiene exactamente $E(\log_{10}(N))+1$ dígitos, donde $\log_{10}$ es el logaritmo en base $10$ y $E(x)$ es la parte entera de un número real $x$ (es decir, el mayor entero menor o igual que $x$).
Todas estas propiedades prespuponen que el número está escrito en base 10. ¿Serías capaz de enunciar las propiedades correspondientes para números en otra base $b$?
Ejercicio propuesto
Responde razonadamente a las siguientes preguntas:
- ¿Cuántas cifras decimales tiene el número $2^{1000}$?
- ¿Es posible reordenar las cifras del número $12345678910111213141516$ para obtener otro número que sea múltiplo de $9$? ¿Y si además se nos permite añadirle una cantidad cualquiera de seises?
- Dos números naturales $A$ y $B$ se escriben únicamente con unos y nueves en base $10$. ¿Cuáles son las posibles cifras de las unidades del producto $AB$? ¿Y de las decenas?
Ir arribaIr al índiceInformar Problemas que puedes resolver con lo aprendido en esta lecciónProblema 49★☆☆☆☆
Determinar todos los números naturales de cuatro cifras que sean iguales al cubo de la suma de sus cifras.
Pista. Si un número es igual al cubo de la suma de sus cifras, entonces tiene que ser un cubo perfecto, ¿no?
PistaSolución 1Solución. La forma más sencilla de resolver este problema darse cuenta de que el número en cuestión tiene que ser un cubo perfecto de 4 cifras y, por tanto, tiene que ser el cubo de un número entre 10 y 21. En este punto, podría probarse caso por caso y llegar a la solución, aunque vamos a ver que podemos descartar algunos números directamente.
Es bien sabido que la suma de las cifras tiene el mismo resto que el propio número módulo $9$ luego si llamamos $r$ a dicho resto, ha de cumplirse que $r\equiv r^3\ (\text{mód }9)$, es decir, $r\equiv -1$, $r\equiv 0$ ó $r\equiv 1\ (\text{mód }9)$. Esto nos lleva a que el número es el cubo de 10, 17, 18 ó 19. Probando cada uno de estos cuatro casos llegamos a que los únicos que cumplen la condición son $17^3=4913$ y $18^3=5832$.
Informar InfoOlimpiada Matemática Española (fase nacional), 1998 problema 2
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 96★★☆☆☆
¿Existe algún número natural tal que al elevarlo al cubo su expresión decimal termine en $111$?
Pista. ¿Cuál debe ser la cifra de las unidades del número para que la de su cubo sea 1? ¿Y la de las decenas para que el cubo termine en 11?
PistaSolución 1Solución. La respuesta es afirmativa y un ejemplo es el 471, que cumple que $471^3=104487111$. Veamos cómo obtener este resultado.
Es obvio que los únicos números que al elevarlos al cubo su expresión decimal termina en $1$ son los que de por sí tienen la cifra de las unidades igual a $1$. Ahora bien, si queremos que la cifra de las decenas del cubo también sea $1$, ésta dependerá sólo de las cifras de las decenas y las unidades del número original y, haciendo la multiplicación con el algoritmo usual y poniendo una cifra indeterminada para las decenas, es fácil ver que tiene que ser $7$ para que el cubo termine en $11$. Repitiendo el proceso, se deduce que la de las centenas tiene que ser $4$.
Nota. Es curioso observar que, repitiendo el proceso, podemos llegar a un número que al cubo termine en tantas unos como deseemos. Esto no ocurre con otras potencias distintas del cubo en general.
Informar InfoSi crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 113★★☆☆☆
Hallar todos los números enteros positivos que son menores que $1000$ y que cumplen que el cubo de la suma de sus cifras es igual al cuadrado del dicho entero.
Pista. Observa que el número tiene que ser un cubo perfecto y, entre $1$ y $999$, no hay tantos cubos perfectos.
PistaSolución 1Solución. Un número que cumpla dicha condición cumple que su cuadrado es un cubo perfecto luego el número en sí ha de ser un cubo perfecto (todos los exponentes en su descomposición de su cuadrado en factores primos han de ser múltiplos de $3$ luego los del propio número también). Como tiene que ser menor que $1000$, tenemos las posibilidades $1$, $8$, $27$, $64$, $125$, $216$, $343$, $512$ y $729$. Además, por el mismo motivo, la suma de sus cifras ha de ser un cuadrado perfecto luego de estos nos quedan $1$, $27$ y $216$, de los cuales sólo $1$ y $27$ cumplen la condición buscada.
Informar InfoOlimpiada Iberoamericana de Matemáticas, 1999 problema 1
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 253★★★☆☆
¿Existe alguna potencia de $2$ tal que al escribirla en el sistema decimal tenga todos sus dígitos distintos de cero y sea posible reordenar los mismos para formar con ellos otra potencia de $2$?
Pista. ¿Qué ocurre si trabajamos módulo $9$?
PistaSolución 1Solución. Supongamos que $A$ y $B$ son dos potencias de $2$ distintas pero con los mismos dígitos (no nulos) reordenados. Vamos a llegar a una contradicción y esto dará respuesta negativa a la pregunta del enunciado. Primero observamos dos propiedades de $A$ y $B$.
- Como los dígitos tanto de $A$ como de $B$ son no nulos, ambos números han de tener el mismo número de cifras significativas. En particular, si suponemos que $A\lt B$, entonces ocurre alguna de las siguientes tres situaciones: $B=2A$ ó $B=4A$ ó $B=8A$ (observa que ambas son potencias de $2$ y $16A$ tiene siempre más cifras que $A$).
- Como los dígitos son los mismos, tenemos que $A\equiv B$ (mód $9$).
Ahora bien, como $A$ y $B$ son primos relativos con $9$ (son potencias de $2$), tenemos que $A\equiv B=2^kA$ (mod $9$) implica $1\equiv 2^k$ (mód $9$). Tanto si $k=1$ como si $k=2$ ó $k=3$ esta congruencia es falsa, lo que nos da la contradicción buscada.
Informar InfoOlimpiada Matemática Española (fase nacional), 2004 problema 4
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 25★★★☆☆
Dado $n\in\mathbb{N}$, denotamos por $S(n)$ la suma de los dígitos del número $n$ en base 10. Demostrar que $S(2n)\leq 2S(n)\leq 10S(2n)$ para todo $n\in\mathbb{N}$ y analizar para qué números se alcanza la igualdad en cada una de las desigualdades.
Pista. ¿Cómo pueden expresarse $S(n)$ y $S(2n)$ en términos de los dígitos de $n$?
PistaSolución 1Solución. Denotemos por $a_k$ el número de veces que un número $k\in\{1,\ldots,9\}$ aparece en la expresión decimal del número $n$. Es fácil ver entonces que
\begin{eqnarray*}
S(n)&=&a_1+2a_2+3a_3+4a_4+5a_5+6a_6+7a_7+8a_8+9a_9{,}\\
S(2n)&=&2a_1+4a_2+6a_3+8a_4+a_5+3a_6+5a_7+7a_8+9a_9{.}
\end{eqnarray*}
De aquí es obvio que $S(n)\leq 5S(2n)$ y la igualdad se alcanza si, y sólo si, el número $n$ está formado sólo por ceros y cincos. También es evidente que $S(2n)\leq 2S(n)$ y la igualdad se alcanza si, y sólo si, todas las cifras del número $n$ son menores o iguales que cuatro.
Informar InfoSi crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problemaProblema 256★★★★☆
Una función $f$ está definida sobre los enteros positivos mediante
\begin{eqnarray}
f(1)&=&1,\qquad f(3)=3,\\
f(2n)&=&f(n),\\
f(4n+1)&=&2f(2n+1)-f(n),\\
f(4n+3)&=&3f(2n+1)-2f(n).
\end{eqnarray}
Determinar el número de enteros positivos $n\leq 1988$ tales que $f(n)=n$.
Pista. Trabaja en base $2$ y calcula los primeros valores de $f(n)$ para encontrar una regla que defina la función $f$.
PistaSolución 1Solución. Las relaciones dadas en el enunciado determinan completamente $f(n)$. Al depender formalmente el valor de $f(n)$ del resto de dividir $n$ entre $4$, esto nos pone sobre aviso de trabajar en otra base. Concretamente, trabajaremos en base $2$. En este punto del razonamiento, sería interesante hacer pruebas con números pequeños (por ejemplo, calcular desde $f(1)$ hasta $f(20)$ para tener una mínima intuición de cómo se comporta $f$ y motivar lo que sigue). Vamos a probar que $f$ toma un número en base $2$ e invierte el orden de sus cifras.
Antes de entrar en el detalle de la demostración, observemos que si $n$ se escribe como $a_k\cdots a_1a_0$ en base $2$, donde $a_0,\ldots,a_k$ son sus dígitos, entonces tenemos que
\begin{eqnarray}
2n&=&a_k\cdots a_1a_00\\
2n+1&=&a_k\cdots a_1a_01\\
4n+1&=&a_k\cdots a_1a_001\\
4n+3&=&a_k\cdots a_1a_011
\end{eqnarray}
Visto eso, procedamos por inducción completa sobre $n$. Para $n=1,2,3,4$ el resultado se comprueba fácilmente ya que, en base 2, $f(1)=1$, $f(10)=f(1)=1$, $f(11)=11$ y $f(100)=f(10)=f(1)=1$. Supongamos entonces que $f(j)$ invierte las cifras de $j$ en base $2$ para $1\leq j\lt n$ y probémoslo para $n$, distinguiendo casos:
- Si $n$ es par, entonces $n=2j$ y $f(n)=f(2j)=f(j)$ por la propiedad del enuncidado. Por hipótesis de inducción, $f(j)$ es invertir las cifras de $j$ en base $2$, pero, como $n$ termina en $0$ en base $2$, es equivalente a invertir las cifras de $n$.
- Si $n=4j+1$, entonces $f(n)=f(4j+1)=2f(2j+1)-f(j)$. Escribamos $j=a_k\cdots a_1a_0$ en base $2$, con lo que $n=a_k\cdots a_1a_001$ y tenemos que probar que $f(n)=10a_0\cdots a_k$. La hipótesis de inducción nos dice que $f(j)=a_0\cdots a_k$ y $2f(2j+1)=1a_0\cdots a_k0$. Como las últimas cifras de $2f(2j+1)$ son $a_0\cdots a_k0=2f(j)$, es fácil darse cuenta de que $f(n)=2f(2j+1)-f(j)=10a_0\cdots a_k$ como queríamos probar.
- Si $n=4k+3$, entonces $f(n)=3f(2j+1)-2f(j)$. Si escribimos $j=a_k\cdots a_1a_0$ en base $2$, entonces se razona de forma análoga al punto anterior que $n=a_k\cdots a_1a_011$ y $3f(2j+1)-2f(j)=11a_0\cdots a_k$.
Queda por calcular el número de enteros positivos $n\leq 1988$ tales que $f(n)=n$, lo que equivale a encontrar los números $n\leq 1988$ que son capicúa en base $2$, es decir, que se escriben igual de derecha a izquierda que de izquierda a derecha. En base $2$ tenemos que $1988$ se escribe $11111000100$, que tiene $11$ cifras. Hay un solo capicúa con $1$ cifra, también hay un solo capicúa con $2$ cifras (el $11$), con $3$ cifras hay $2$ capicúas (el $101$ y el $111$) y, en general, hay $2^k$ capicúas con $2k$ cifras y $2^k$ capicúas con con $2k-1$ cifras. Por tanto, hay $1+1+2+2+4+4+8+8+16+16+32=94$ capicúas con a lo sumo $11$ cifras, pero sólo dos de ellos son mayores que $11111000100$ (el $11111011111$ y el $11111111111$), luego el número buscado es $92$.
Informar InfoOlimpiada Matemática Internacional, 1988 problema 3
Si crees que el enunciado contiene un error o imprecisión, puedes notificarlo pulsando en el siguiente botón:
Informar de error en enunciadoSi conoces una competición en la que apareció este problema o bien crees que la información que aquí aparece es incorrecta, puedes notificarlo pulsando en el siguiente botón:
Informar de procedencia del problema