Suma de las potencias de cuatro

Question

Deje $0\leq a_1\leq a_2\leq\dots\leq a_n\leq b$ ser números enteros tales que a $4^b\leq 4^{a_1}+\dots+4^{a_n}$. Puede $4^b$ ser escrita como una suma de un subconjunto de a $4^{a_1},\dots,4^{a_n}$?

Yo creo que puede ser posible realizar algún tipo de algoritmo voraz, donde se recogen cuatro idénticos poderes de $4$, siempre que tales organizaciones existan, en un mayor poder de $4$. Podemos realizar este proceso a partir de la más pequeña de energía de $4$ hasta que ya no es posible, así que terminamos con en la mayoría de los tres poderes de $4$ para cada poder.

Answer 1

Por inducción en $b\geq 0$. El paso básico es trivial.

Para $b>1$, supongamos que el enunciado es verdadero para $b-1$. Tenemos dos casos.

i)$a_1\geq 1$, a continuación, tome $A_i=a_i-1$, por el paso inductivo $4^{b-1}$ puede ser escrita como una suma de un subconjunto de a $4^{A_1},\dots,4^{A_n}$ y, a continuación, multiplicando por $4$ obtenemos una representación de la $4^{b}$.

ii) Suponga que el $a_1=\dots=a_r=0$ $a_{r+1}\geq 1$ y asumir que $4^{b-1}$ no puede ser escrita como una suma de un subconjunto de a $4^{A_{r+1}},\dots,4^{A_n}$ (de lo contrario nos ara hacer como en i)). Esto significa que $$4^{b-1}> 4^{A_{i+1}}+\dots+4^{A_n}\quad \Rightarrow \quad 4^{b}> 4^{a_{i+1}}+\dots+4^{a_n}.$$ Pero sabemos que $4^{b}\leq r+4^{a_{r+1}}+\dots+4^{a_n}$. Por lo tanto $$4^{b}=4^{a_{1}}+\dots+4^{a_j}+4^{a_{r+1}}+\dots+4^{a_n}$$ donde $1\leq j=4^{b}-(4^{a_{r+1}}+\dots+4^{a_n})\leq r$.

P. S. Este enfoque le da también un algoritmo recursivo que generan este tipo de representaciones.

Answer 2

Su idea es aceptar. Pero es verdad que se necesita un poco de 'formalización'. Suponemos $a_n<b$ (o más que nada para mostrar). Usted puede escribir en la base 4 de expansión $$4^b \leq \sum_i 4^{a_i}=\sum_{k=0}^{b-1} p_k 4^k+n_b 4^b$$ with each $0\leq p_k\leq 3$ and $n_b\geq 0$. We will construct by induction coarser and coarser (sub-) partitions of the set of $a_i$'s. In the beginning we set $S_0=([a_1],...,[a_n])$ in which each $a_i$ is a one element partition. The value of each element of a partition is the sum of the 4th power of its elements. In $S_0$ each element therefore has a value of the form $4^k$, with $0\leq k<b$.

Si $0<p_0$ (recuerden $p_0$ no es mayor que 3), entonces no debe ser $p_0$ elementos de la partición $S_0$ del valor de las $1$ (es decir, tener $a_i=0$). Pones esos elementos a un lado. El resto se reagrupen en la más pequeña posible partición de elementos para formar múltiplos de 4. Llame a $S_1$ esta nueva partición. El valor de cada elemento es entonces de la forma$4^k$$1\leq k<b$.

Si $0<p_1 (\leq 3)$ debe ser $p_1$ de los elementos en $S_1$ con valor de $4$ que usted puede dejar de lado. El resto se reagruparse en una partición $S_2$ donde cada elemento de la partición tiene un valor de la forma$4^k$$2 \leq k<b$, etc...

En $S_{b-1}$ cada partición elemento debe tener el valor de $4^{b-1}$. Si tiene 4 de tales elementos, a continuación, su unión constituye una solución a su problema. Si no, entonces hay en la mayoría de los 3 elementos y la adición de los valores de todos los que han dejado de lado consigue $$ \sum_i 4^{a_i} \leq \sum_{k=0}^{b-1} 3 \times 4^k < 4^b$$ contradiciendo la hipótesis. (Hacer un dibujo de estas particiones pueden ayudar a conseguir la idea).