Demuestre que 3 es el número más eficiente.

Question

Dada una constante $n$, la construcción de una secuencia de números naturales $a_0, a_1, \ldots, a_k$ tal forma que:

• $a_0 + a_1 + \cdots + a_k \leq n$
• $a_0 a_1 \cdots a_k$ es maximizada

Suponemos que la solución es la siguiente:

Agregar $3$ de su secuencia. Restar $3$$n$. Repita hasta que el sobrante es $2, 3, \text{or } 4$. Si el resto de la es $2$, final de la secuencia con un $2$; si la sobras de es $3$, final de la secuencia con un $3$; y si el resto de la es $4$, final de la secuencia con dos $2$s.

Para mostrar esto, quiero decir que $3$ es el dígito de más eficiente de número.

Para todos los números naturales $m > 1$, podemos decir:

$$3^m \geq m^3$$

Tanto el LHS y RHS de esta desigualdad tiene una secuencia suma de $3m$.

Esto es suficiente para mostrar que mi solución es la correcta? Tengo una fuerte sensación de que mi prueba es que falta algo (por ejemplo, el extraño caso de un sobrante de $4$ no es realmente ", explicó"), pero no estoy seguro de qué. ¿Cómo puedo formalizar lo que he escrito, y lo que tengo que agregar para hacer una solución integral?

---

Sólo para aclarar cualquier duda acerca de lo que este problema está pidiendo, vamos a decir $n = 11$. Entonces:

$$3+3+3+2 = 11$$ $$3*3*3*2 = 54$$

Y $54$ es el mayor número que se puede hacer. Aquí, la secuencia en cuestión es $\{3, 3, 3, 2\}$.

Answer 1

Si no es $a_i\gt4$, tenemos

$$ 2(a_i-2)=2a_i-4\gt a_i\;, $$

contradiciendo de optimalidad. Por lo tanto $a_i\le4$ todos los $i$. Podemos reemplazar cualquier $4$ dos $2$s sin cambiar la restricción o la función objetivo. También se $1$s, obviamente, son subóptimos.

Por lo tanto todos los $a_i$ son $2$ o $3$. Cualquier grupo de tres $2$s se puede mejorar mediante la sustitución de la misma por dos $3$s. Desde hace dos $2$s son mejor que uno $3$, se deduce que la solución óptima es la que consta de todos los $3$s y el número único de cero a dos $2$s para hacer que la suma sea igual a $n$.

Nota la conexión a la transformada Rápida de Fourier, donde este problema de optimización se plantea en la elección de la base. El radix $3$ es óptimo en este sentido, pero la más habitual radix $2$ tiene otras ventajas.

Para motivar a la solución utilizando el cálculo, podemos dividir el $n$ a $k$ a partes iguales y maximizar $\left(\frac nk\right)^k$ con respecto al $k$:

$$ \frac{\mathrm d}{\mathrm dk}\log\left(\frac nk\right)^k=\frac{\mathrm d}{\mathrm dk}\left(k(\log n-\log k)\right)=\log n-\log k-1\stackrel{!}{=}0\;, $$

rendimiento $k=\frac n{\mathrm e}$, por lo que las piezas de tamaño $\mathrm e$. El valor óptimo de$ \left(\frac nk\right)^k$ es así

$$ \left(\sqrt[\mathrm e]{\mathrm e}\right)^n\approx1.445^n\;, $$

en comparación con

$$ \left(\sqrt[2]2\right)^n\approx1.414^n $$

y

$$ \left(\sqrt[3]3\right)^n\approx1.442^n\;, $$

por tanto, las diferencias entre $2$, $\mathrm e$ y $3$ son más bien marginales.