Archivo de la etiqueta: dígitos

Seminario de Resolución de Problemas: Bases numéricas y dígitos

[latexpage]

Introducción

En las entradas anteriores de teoría de números hemos hablado acerca de divisibilidad, de aritmética modular y de factorización única en primos. En esta entrada vamos a hablar de propiedades que podemos deducir de ciertos números a partir de su dígitos.

Usualmente escribimos a los números en base $10$, usando los dígitos de $1$ a $9$. En realidad, esto es relativamente arbitrario. Podemos usar bases distintas de $10$ para expresar cualquier número de manera (casi) única. Conocer la expresión de un número en cierta base nos permite deducir propiedades algebraicas y de divisibilidad que nos ayuden a resolver problemas.

Expresión en una base arbitraria

Para cualquier base entera $b\geq 2$ que elijamos, cualquier número real se puede expresar de manera (casi) única en base $b$. La afirmación precisa es el siguiente resultado.

Teorema. Sea $r$ un número real y $b\geq 2$ un entero. Entonces, existen únicos enteros $A_0,A_1,\ldots, a_1,a_2,\ldots$ en $\{0,1,\ldots,b-1\}$ tales que $$r=\sum_{i=0}^\infty A_i b^i + \sum_{i=0}^{\infty} a_i 10^{-i}$$ y $a_i\neq b-1$ para una infinidad de $i$’s.

Para estos $a_i$ y $A_i$ escribimos $$r=(\ldots A_2A_1A_0.a_1a_2\ldots)_b,$$ en donde el subíndice indica la base que se está usando.

La condición de $a_i\neq b-1$ para una infinidad de $i’s$ está ahí para garantizar que la expresión sea única pues, por ejemplo, $1=\sum_{i=0}^\infty 9\cdot 10^{-i}=0.9999\ldots$, pero esa condición descarta la expresión de la derecha.

Si $b=2$, a esta expresión le llamamos la expresión binaria de $r$.

Ejemplo. La expresión binaria de $4/3$ es $(1.010101\ldots)_2$. ¿Por qué?

Multiplicar y dividir entre $10$ cuando tenemos números en base $10$ es sencillo: simplemente recorremos el punto decimal. Lo mismo sucede en cualquier base $b$.

Proposición. Cuando tenemos un número en base $b$ y multiplicamos por $b$, el «punto decimal» se recorre a la derecha. Cuando dividimos entre $b$ se recorre a la izquierda.

Problema. Determina si existe un real $x$ tal que $$\floor{x}+\floor{2x}+\floor{4x}+\floor{8x}= 2222.$$

Sugerencia pre-solución. Trabaja hacia atrás suponiendo que la ecuación sí tiene una solución para determinar cómo tiene que verse $x$. Usa la expresión binaria de $x$.

Solución. Tenemos que $r\geq \floor{r}$ para todo real $r$, de modo que si dicho número $x$ existe, se cumple $$17x\geq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} = 2222.$$ De aquí, $x\geq 2222/17 = 130.705\ldots\geq 130$. También, $r\leq \floor{r}+1$, de modo que si $x$ existe necesitamos $$17x\leq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} + 4 = 2226.$$

De aquí, $x\leq 2226/17 =130.94\leq 131$.

Esto nos dice que $x$ es un real entre $130$ y $131$. Escribámoslo como $130$ más una parte fraccional en base $2$, es decir, de la forma $x=130+(abcde\ldots)_2$. Multiplicar por $2$ simplemente recorre el punto decimal en base $2$ un lugar hacia la derecha, de modo que
\begin{align*}
2x&=260+(a.bcde\ldots)_2\\
4x&=520+(ab.cde\ldots)_2\\
8x&=1040+(abc.de\ldots)_2,
\end{align*} y por lo tanto
\begin{align*}
\floor{x}&=130\\
\floor{2x}&=260+(a)_2=260+a\\
\floor{4x}&=520+(ab)_2=520+2a+b\\
\floor{8x}&=1040+(abc)_2=1040+4a+2b+c.
\end{align*}

Concluimos entonces que la suma buscada es igual a $1950+7a+3b+c$. Si existe el número que queremos, la ecuación $$1950+7a+3b+c=2222$$ debe tener una solución con $a$, $b$ y $c$ iguales a $0$ o a $1$. Pero esto es imposible, pues incluso aunque los tres sean iguales a $1$, tenemos a lo más $1950+11=1961$. De esta forma, no existe la $x$ que buscamos.

$\square$

Bases y números racionales

Una sucesión infinita $\{a_1,a_2,\ldots,\}$ es preperiódica si existen enteros positivos $n$ y $d$ tales que $a_m=a_{m+d}$ para todo entero $m\geq n$. A $d$ se le llama un periodo de la sucesión, y decimos que $\{a_1,a_2,\ldots\}$ es periódica a partir de $a_n$.

Teorema. Sea $r$ un número real. Las siguientes tres afirmaciones son equivalentes:

  • $r$ es racional
  • Para toda base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\ldots\}$ es preperiódica.
  • Para alguna base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\ldots\}$ es preperiódica.

Problema. Considera el número en binario $$r=(0.a_1a_2a_3\ldots)_2$$ en donde $a_i=0$ si $i$ es primo y $a_i=1$ si no. Determina si $r$ es un número racional o irracional.

Sugerencia pre-solución. Procede por contradicción, suponiendo que $r$ es racional.

Solución. Si $r$ fuera racional, la sucesión $\{a_1,a_2,\ldots\}$ sería preperiódica, de modo que existirían $n$ y $d$ tales que $a_{m+d}=a_m$ para todo $m\geq n$. Consideremos el bloque de $d$ dígitos $(a_na_{n+1}\ldots a_{n+d-1})_2$. Como el periodo de la sucesión es $d$, a partir de $a_n$ este bloque de dígitos se repite.

Los números $M=n(2d+1)!+2$, $M+1=n(2d+1)!+3$, $\ldots$, $M+(2d-1)=n(2d+1)!+(2d+1)$ son $2d$ números consecutivos mayores a $n$ y tales que ninguno de ellos es primo, pues el primero es divisible entre $2$, el segundo entre $3$, …, y el último entre $2d+1$. Esto muestra que el bloque de $d$ dígitos debe consistir de puros $1$’s, pues uno de los bloques del ciclo queda contenido en el bloque de $2d$ dígitos $(a_Ma_{M+1}\ldots a_{M+2d-1})_2$. Así, a partir de $a_n$ todos los dígitos son iguales a $1$.

Pero esto es imposible, pues quiere decir que todos los enteros mayores o iguales a $n$ no son primos. Esto contradice que hay una infinidad de números primos.

$\square$

Criterios de divisibilidad

Si sabemos cómo es la expresión de un número en una base, entonces a veces podemos decir cosas acerca de su divisibilidad o residuo al dividirse entre algunos enteros relacionados con la base. Cuando estamos trabajando módulo $10$ tenemos el siguiente resultado.

Proposición (criterios de divisibilidad base 10). Sea $n$ un entero positivo. En base $10$,

  • $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $10^k$, y por lo tanto también módulo $2^k$ y módulo $5^k$.
  • $n$ es congruente con la suma de sus dígitos módulo $9$, y por lo tanto también módulo $3$.
  • Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $10^{j}+1$.

Demostrar estos criterios es sencillo. Por ejemplo, un número $(A_nA_{n-1}\ldots A_0)_{10}$ en base $10$ es igual a $$10^{n}A_n+10^{n-1}A_{n-1}+\ldots+10 A_1+ A_0.$$ Trabajando módulo $9$, todos los $10$ son $1$, así que $$n=10^nA_n+\ldots+A_0\equiv A_n + A_{n-1}+\ldots+A_0.$$

Como ejemplo del último criterio, considera el siguiente problema:

Problema. ¿Cuál es el residuo que queda al dividir $n=1512513514515$ entre $13$?

Sugerencia pre-solución. Usa el tercer criterio de divisibilidad base $10$ para $j=3$. Factoriza $1001$.

Solución. Vamos a estudiar al número módulo $1001$. Para esto, agrupamos los dígitos de tres en tres, de derecha a izquierda $$515, 514, 513, 512, 1$$ y hacemos la suma alternada $$515-514+513-512+1=3.$$ Por el tercer criterio de divisibilidad, tenemos que $n\equiv 3 \pmod{1001}$. Notemos que $1001=7\cdot 11 \cdot 13$, de modo que $n\equiv 3 \pmod{13}$. Así, el residuo al dividir $n$ entre $13$ es $3$.

$\square$

En general, tenemos lo siguiente.

Proposición (criterios de divisibilidad base $b$). Sea $n$ un entero positivo. En base $b$:

  • $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $b^k$, y por lo tanto también módulo $d^k$ para cualquier divisor $d$ de $b$.
  • $n$ es congruente con la suma de sus dígitos módulo $b-1$ (y por lo tanto también módulo cualquier divisor de $b-1$)
  • Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $b^{j}+1$.

Problema. Considera los números del $1$ al $500$ (inclusive). ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en base $3$? ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en binario?

Sugerencia pre-solución. Haz casos pequeños para encontrar un patrón que te diga cuántos números del $1$ al $n$ tienen una cantidad impar de $1$’s en su expresión en base $2$ y $3$. Para demostrar el resultado para base $3$, usa criterios de divisibilidad generalizados. Para base $2$ usa paridad y aprovecha la simetría.

Solución. Un número en base $3$ es congruente con la suma de sus dígitos módulo $2$. En base $3$ el único dígito impar es el $1$. Así, un número en base $3$ es congruente a su cantidad de dígitos $1$ módulo $2$. De esta forma, $n$ tiene una cantidad impar de $1$’s si y sólo si es impar. Por lo tanto, hay $250$ números entre $1$ y $500$ que tienen una cantidad impar de $1$’s en su expresión en base $3$.

En base $1$ el patrón no es tan claro. Los primeros números son $1$, $10$, $11$, $100$, $101$, $110$, $111$. A veces cuando se cambia de cantidad de dígitos se cambia la paridad de $1$’s (como de $11$ a $100$) y a veces no (como de $111$ a $1000$). Haremos entonces un argumento de emparejamiento.

Notemos que cualquier número par $2n$ termina en $0$ en binario y que $2n+1$ tiene la misma expansión salvo el último dígito, que ahora es $1$.Así, a los números del $2$ al $499$ los podemos agrupar en parejas en donde en cada pareja los números tienen distinta paridad de $1$’s. De esta forma, aquí hay $498/2=249$ números con una cantidad impar de $1$’s. El $1$ tiene una cantidad impar de $1$’s. El $500$ en binario es $(111110100)_2$, que tiene una cantidad par de $1$’s. Así, hay $250$ números entre $1$ y $500$ con una cantidad impar de $1$’s en binario.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.4 del libro Problem Solving through Problems de Loren Larson.

Seminario de Resolución de Problemas: Aritmética modular

[latexpage]

Introducción

En la entrada anterior hablamos de divisibilidad, máximo común divisor y combinaciones lineales enteras. Cuando hablamos de trabajar en artimética modular nos referimos a que tomamos un entero $n$ y realizamos todas las operaciones «sólo en el mundo de $n$», es decir, aplicando las operaciones únicamente en los residuos que deja un número al ser dividido entre $n$.

Cuando estamos trabajando módulo $n$, dos enteros $a$ y $b$ «son los mismos» si $n$ divide a $a-b$. En este caso decimos que $a\equiv b \pmod n$, que se lee «$a$ es congruente con $b$ módulo $n$».

En esta entrada de blog discutimos la relación «ser congruente con» y cómo se puede enunciar en términos de anillos. Ahí damos las demostraciones de varias de las propiedades que no probaremos aquí. Es recomendable por lo menos echarle un ojo.

Aritmética modular

Para recordar los principios básicos de la aritmética modular, comencemos con el siguiente problema.

Problema. Determina cuál es el residuo obtenido de dividir $1305\cdot 1302+1314\cdot 1311$ al dividirse entre $11$.

Sugerencia pre-solución. Intenta resolver este problema trabajando módulo $11$.

Solución. Tenemos que $1305$, $1302$, $1314$ y $1311$ los podemos poner como un múltiplo de $13$ más un residuo como sigue: $1300+5$, $1300+2$ y $1313+1$, $1300+11$. Así, $1305\equiv 5\pmod {13}$, $1302\equiv 2 \pmod {13}$, $1314\equiv 1 \pmod {13}$ y $1311\equiv 11 \pmod {13}$. Así, trabajando módulo $1$ tenemos que:

\begin{align*}
1305\cdot 1302+1314\cdot 1311 &\equiv 5\cdot 2 + 1\cdot 11 \\
&\equiv 10 + 11 \equiv 21 \\
&\equiv 8 \pmod {13}
\end{align*}
De esta forma, $1305\cdot 1302+1314\cdot 1311$ deja residuo $8$ al dividirse entre $13$.

$\square$

Utilizando el algoritmo de la división, que vimos en la entrada anterior, se puede probar el siguiente resultado.

Proposición. Para cada entero $a$ y entero positivo $n$, existe un único número $r$ en $\{0,1,\ldots,n-1\}$ tal que $a\equiv r\pmod n$, que es justo el residuo obtenido al dividir $a$ entre $n$.

Dicho en otras palabras, sólo hay $n$ posibles residuos al dividir entre $n$. Esto nos permite que las operaciones módulo $n$ siempre las hagamos con números chiquitos, y que afirmaciones sencillas de divisibilidad entre $n$ dependen sólo de $n$ casos. Esto lo podemos aprovechar para resolver problemas como el siguiente.

Problema. Se tienen $13$ números enteros. Muestra que hay tres de ellos $a,b,c$ que satisfacen que $$1331\mid (a-b)(b-c)(c-a).$$

Sugerencia pre-solución. Notemos que $1331=11^3$, así que trabajamos módulo $11$. Encuentra todas las posibilidades que pueden tener los números cuadrados.

Solución. Un entero $n$ sólo puede ser congruente con alguno de los números $0,1,2,3,4,5,6,7,8,9,10$ módulo $11$. Los cuadrados tienen entonces las siguientes posibilidades:

$n$$n^2 \pmod {11}$
$0$$0$
$1$$1$
$2$$4$
$3$$9$
$4$$16\equiv 5$
$5$$25\equiv 3$
$6$$36\equiv 3$
$7$$(-4)^2\equiv 5$
$8$$9$
$9$$4$
$10$$1$

A partir del $6$ estamos aprovechando que ya conocemos los del $1$ al $6$ y que $a \equiv a-11 \pmod {11}$. Notemos que sólo hay $6$ residuos posibles para los cuadrados módulo $11$, que son $0$, $1$, $4$, $9$, $5$ y $3$.

Ahora sí, resolvamos el problema. Como tenemos $13$ números enteros y sólo hay $6$ posibles residuos para los cuadrados módulo $11$, entonces por principio de las casillas hay tres de estos enteros cuyo cuadrado deja el mismo residuo al dividirse entre $11$, digamos $a,b,c$. Como dejan los tres el mismo residuo, tenemos $11\mid a-b$, $11\mid b-c$ y $11\mid c-a$, de donde se sigue la conclusión que queremos.

$\square$

Últimos dígitos

Los últimos $m$ dígitos de un entero $n$ corresponden con el residuo de dividir $n$ entre $10^m$. Por esta razón, en este tipo de problemas es conveniente usar módulos.

Problema. Determina los últimos dos dígitos de $7^{25}+25^7$.

Sugerencia pre-solución. Trabajamos módulo $100$, así que todas las congruencias son módulo $100$. Hay muchas formas de proceder para encontrar $7^{21}$. Notemos que $7^{2}\equiv 49$. y que $$7^4\equiv 49\times 49 = 2401 \equiv 1.$$ Esto es una gran ventaja, pues entonces $7^{24}\equiv (7^4)^6 \equiv 1^6 \equiv 1$, así que $7^{25}\equiv 7$.

Para $25^7$, nos conviene notar que $25=20+5$, de modo que
\begin{align*}
25^2&=(20+5)^2\\
&=20^2+2\cdot 20 \cdot 5 + 25\\
&\equiv 25,
\end{align*}

pues los primeros dos sumandos son múltiplos de $100$. De esta forma, $25^7\equiv 25$. Así, $7^{25}+25^7\equiv 7+25\equiv 32$, por lo que los dos últimos dígitos de la expresión son $32$.

$\square$

Veamos otro ejemplo en el que además combinamos un poco de la teoría mencionada en la entrada anterior.

Problema. Demuestra que existe un entero que es múltiplo de $2002$ y que tiene por lo menos $2002$ dígitos iguales a $7$.

Sugerencia pre-solución. Intenta hacer que los $2002$ dígitos $7$ que se necesitan aparezcan hacia el final. Esto te permitirá usar congruencias. Además, necesitarás el resultado de la entrada anterior que dice que el máximo común divisor de dos números se puede expresar como combinación lineal entera de ellos.

Solución. Tomemos el número $N=777\cdots770$, en donde hay $2002$ dígitos iguales a $7$.

El máximo común divisor de $2002$ y $10^{2003}$ es $2$, de modo que existen enteros $m$ y $n$ tales que $2002m+10^{2003}n=2$.

Multiplicando esta igualdad por el entero $N/2$, obtenemos que $2002\cdot \frac{mN}{2}+10^{2003}\frac{nN}{2}=N$. Aplicando módulo $10^{2003}$ obtenemos que $2002\cdot \frac{mN}{2} \equiv N \pmod {10^{2003}}$.

Como $N<10^{2003}$, esto nos dice que $2002\cdot \frac{mN}{2}$ es un múltiplo de $2002$ cuyos últimos $2003$ dígitos son los de $N$, es decir, que tiene por lo menos $2002$ dígitos iguales a $7$.

$\square$

Teorema chino del residuo

En algunos problemas necesitamos construir un entero que satisfaga un conjunto de congruencias. El teorema chino del residuo nos da una condición bajo la cual podemos garantizar la existencia de dicho número.

Teorema. Sea $n\geq 2$ un entero, $b_i$ enteros para $i\in\{1,2,\ldots,n\}$ y $m_i$ enteros positivos para $i\in\{1,\ldots,n\}$. Supongamos además que cada par $m_i, m_j$ de enteros ($i\neq j$) son primos relativos. Entonces el sistema lineal de congruencias
\begin{align*}
x&\equiv b_1\pmod {m_1}\\
x&\equiv b_2\pmod {m_2}\\
&\vdots\\
x&\equiv b_n\pmod {m_n}
\end{align*}
tiene una y sólo una solución módulo $m_1m_2\ldots m_n$.

El teorema tiene muchas aplicaciones tanto en resolución de problemas, como en matemáticas en general. Veamos un ejemplo.

Problema. ¿Será posible encontrar $5$ enteros consecutivos tales que cada uno de ellos sea divisible entre un cubo distinto de $1$?

Sugerencia pre-solución. Intenta construir el ejemplo usando el teorema chino del residuo con $5$ módulos y en donde los $b_i$ son consecutivos.

Solución. Por el teorema chino del residuo, existe un entero positivo $n$ tal que
\begin{align*}
n&\equiv 0 \pmod{2^3}\\
n&\equiv -1\pmod{3^3}\\
n&\equiv -2\pmod{5^3}\\
n&\equiv -3\pmod{7^3}\\
n&\equiv -4\pmod{11^3}
\end{align*}

Para este entero, se tiene que $2^3$ divide a $n$, $3^3$ divide a $n+1$, $5^3$ divide a $n+2$, $7^3$ divide a $n+3$ y $11^3$ divide a $n+4$.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.2 del libro Problem Solving through Problems de Loren Larson.

Hay otros dos teoremas que sirven cuando estamos trabajando módulo $n$, de los cuales hemos escrito aquí en el blog. Para empezar, aquí hay una entrada con videos de ejercicios de trabajar módulo $n$.

El teorema de Fermat y el de Wilson ayudan a entender potencias y factoriales, respectivamente. En la entrada sobre el teorema chino del residuo damos una demostración al teorema.

Usa la paridad

HeuristicasLos números enteros pueden ser pares o impares, dependiendo de si son divisibles entre dos o no. Más aún, se van alternando uno y uno. Además, es muy sencillo saber cómo es la paridad de la suma de dos números o bien de su producto si sabes la paridad de esos números. Estas ideas pueden parecer muy básicas, pero ayudan en una gran cantidad de problemas y son una introducción a los invariantes.

Cuando en un problema observamos nada más la paridad, estamos cubriendo una gran cantidad de casos nada más analizando pocos. En estos videos vemos cómo se aplica la idea de paridad en varios problemas de tableros, juegos, álgebra y teoría de números.

Ir a los videos…

Busca una contradicción

HeuristicasTerminamos esta serie de técnicas de resolución de problemas con una de las técnicas más finas y más usadas en las matemáticas: las pruebas por contradicción.

La idea es la siguiente. Por un momento suponemos que lo que queremos demostrar es falso. Después trabajaremos haciendo todo lo demás correctamente. La idea es llegar a una contradicción con las hipótesis del problema, o bien a algo que sabemos que es imposible. De esta forma, sabemos que debe haber un error en la demostración de eso imposible. Y como lo único que hicimos mal fue suponer que lo original era falso, debemos tener que en realidad es verdadero.

En estos videos veremos varios ejemplos de este argumento para acostumbrarnos. Es súper útil pensar en estos argumentos casi automáticamente.

Ir a los videos…