Una pregunta sobre "números binarios en bases arbitrarias"

Question

Este es un problema que se me ocurrió hace tiempo:

Sea un "número binario en base $n$ "se refiere a un número natural cuya representación en base $n$ se compone únicamente de $0$ y $1$ 's. Demuestra que todo número natural puede expresarse como la suma de un número binario en base $3$ un número binario en base $4$ y un número binario en base $5$ .

Al final conseguí demostrarlo (lo que por el momento se dejará como ejercicio al lector, ya que parece que he borrado la única copia que tenía). Pero los descubrimientos de esa prueba acabaron dando lugar a otra cuestión:

Dada una colección de números $a_1, a_2, a_3, \ldots, a_n\ (a_k \ge 2)$ para que $\displaystyle \sum_{k=1}^n \frac{1}{a_k-1} \geq 1$ todo número natural puede expresarse como la suma de números binarios $b_1, b_2, b_3, \ldots, b_n$ de modo que para todos $1 \le k \le n$ , $b_k$ está en la base $a_k$ .

¿Es esto cierto? Si es así, ¿puede demostrarlo?

Answer 1

Sí, creo que esto debería seguirse fácilmente de dos lemas muy simples:

Lema 1: Si $S = ( a_1 \le a_2 \le a_3 \le \cdots)$ es un multiconjunto de enteros positivos, entonces todo número natural puede representarse como una suma de elementos distintos de $S$ si para todo $k\ge 0$ , $$\tag{*}\sum_{i=1}^k {a_i} \ge a_{k+1}-1.$$ De forma equivalente: para cada $m$ los elementos de $S$ sin exceder $m$ suman al menos $m$ .

Prueba. Una dirección es obvia: si $\sum_{i=1}^k {a_i} < a_{k+1}-1$ para algunos $k$ entonces no hay manera de representar $a_{k+1}-1$ como una suma de elementos de $S$ .

En sentido inverso, demostramos por inducción que si $S$ satisface (*), entonces todo entero no negativo hasta $\sum_{i=1}^n a_i$ puede representarse como una suma de términos de $S_n := (a_1, a_2, \ldots, a_n)$ . El caso base $n=1$ es fácil porque (*) con $k=0$ implica que $a_1 = 1$ .

Para el paso de inducción, supongamos $S_n$ representa todos los números hasta $M$ donde $M \ge a_{n+1}-1$ . Entonces es fácil ver que $S_{n+1}$ representa cada $0 \le x \le M+a_{n+1}$ : si $0 \le x \le M$ esto es obvio, mientras que si $x \ge M+1 \ge a_{n+1}$ entonces $x-a_{n+1}$ es un número entero no negativo que no supera $M$ que puede ser representado por $S_n$ . Ahora sólo hay que añadir $a_{n+1}$ .

Esto demuestra la primera equivalencia. Ahora observamos que (*) es equivalente a la afirmación de que $\sum_{x \in S, x \le m} x \ge m$ para cada $m$ . Si (*) se cumple, entonces para cualquier $m \in \mathbb N$ , dejemos que $k$ sea el mayor número entero tal que $a_k \le m$ . Entonces la suma de todos los elementos hasta $m$ es precisamente $\sum_{i=1}^k a_k \ge a_{k+1} - 1 > m-1$ , lo que hace que al menos $m$ .

En el otro sentido, (*) es vacuamente cierto siempre que $a_k = a_{k+1}$ Así pues, supongamos que $a_k < a_{k+1}$ . Ahora elija $m=a_{k+1}-1 \ge a_k$ y aplicar la propiedad de que todos los elementos hasta $m$ suman al menos $m$ .

Lema 2: Sea $b \ge 2$ y $n \in \mathbb N$ . La suma de todos los $b^i$ sin exceder $n$ es al menos $\frac{n}{b-1}$ .

Prueba. Este es muy fácil. Si $r$ es el mayor número entero tal que $b^r \le n$ entonces $n < b^{r+1}$ Por lo tanto $n \le b^{r+1}-1 = (b-1)(1 + b + \cdots + b^r)$ .

Finalmente, combinando estos dos lemas se obtiene la afirmación de la pregunta: sea $S$ sea el conjunto de todas las potencias no negativas de todos los $a_k$ . Para cada $m \in \mathbb N$ la suma de todos los elementos de $S$ hasta $m$ es al menos $\sum_k \frac{m}{a_k-1} \ge m$ .