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

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.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.