Partición y potencia de 2s

Question

Estoy tratando de encontrar una partición del número natural N por la cual

1. podemos generar una partición para todos los números naturales menores que N a partir de los elementos de la partición.
2. El número de elementos de la partición debe ser el menor posible.

Por ejemplo, si N es 8, creo que la partición es {1,2,4,1} ya que puedo formar una partición para todos los números naturales menores que 8 a partir de los elementos como los siguientes.

1 = 1, 2 = 2, 3 = 1+2, 4 = 4, 5 = 1+4, 6 = 2+4, 7 = 1+2+4

Simplemente pongo las potencias de 2 (ej. {1,2,4}) hasta que la suma de ellas sea menor o igual a N. Luego, pongo el resto (ej. {1}) para que la suma de todos los elementos sea igual a N. Me gustaría saber si este método es el correcto para obtener una partición con el menor número de elementos. ¿Hay algún teorema relacionado con ello? Sería estupendo si alguien puede ayudarme a demostrar si mi método es correcto o no. Gracias.

Answer 1

Esto produce la partición de menor tamaño (aunque puede haber otras particiones de este tamaño que hagan el trabajo - pero la tuya definitivamente funciona). Observe que el tamaño de su partición es $\lceil \log_2(N+1) \rceil$ (como puedes comprobar); podemos demostrar que ninguna partición más pequeña funcionará.

Suponga que tiene una partición con $k<\lceil \log_2(N+1) \rceil$ partes, de modo que $k < \log_2(N+1)$ en particular. El número de subconjuntos de su partición es $2^k$ por lo que, aunque todos tuvieran sumas diferentes, el número total de sumas que se pueden conseguir (como suma de una subpartición) es como máximo $2^k < 2^{\log_2(N+1)} = N+1$ En otras palabras, el número total de sumas que se pueden conseguir es como máximo $N$ . Pero las dos sumas $0$ y $N$ se alcanzan definitivamente, por lo que debe haber algún número natural entre $1$ y $N-1$ que no se puede lograr.