Partición $n$ suma natural $2N$ en dos conjuntos que suman $N$

Question

Estoy tratando de resolver este problema:

Dejemos que $a_1, \ldots , a_n$ sean números naturales tales que $a_k \le k$ por cada $k = 1,\ldots,n$ et $\sum_{k=1}^{n} a_k=2N$ . Demuestre que existe una partición de este $n$ números en dos conjuntos, tales que para cada conjunto, la suma de sus elementos es $N$ .

Creo que he encontrado un algoritmo que funciona, pero no sé cómo demostrar formalmente que funciona. Va como sigue:

Tenemos $a_1, \ldots , a_n$ . Reordena los elementos en orden ascendente. Esto preserva la propiedad de que $a_k \le k$ por cada $k = 1,\ldots,n$ . Entonces empieza por elegir el elemento más grande $a_n$ . Añade $a_{n-1}$ que es $\le a_{n}$ . Si la suma es superior a N, vuelva sobre sus pasos y reste $a_{n-1}$ y luego intente lo mismo con $a_{n-2}$ . Si, por el contrario, la suma no superaba N, también pasa a $a_{n-2}$ pero esta vez sin restar $a_{n-1}$ . Siga haciendo esto hasta que llegue a $a_1$ lo que significa que has intentado añadir cada elemento a la suma, con la condición de que la inclusión de ese elemento no haga que la suma sea mayor que $N$ . Al final, los elementos que eligió suman $N$ y los que quedan fuera también suman $N$ .

¿Podría alguien ayudarme a formalizar esto? (o mostrarme que no funciona) (o mostrarme una forma más agradable de resolver esto)

Answer 1

Podemos demostrar por inducción la afirmación aún más fuerte, que dados los números naturales $a_1\leq ...\leq a_n$ con $a_k\leq k$ podemos encontrar un subconjunto que sume cualquier número entre $0$ (la suma vacía) y $S_n=\sum_{k=1}^n a_k$ :

Primero el caso base, es decir $n=1$ en el que sólo tenemos $a_1=1$ y cada número entre $0$ y $\sum_{k=1}^1 a_1=1$ puede formarse a partir de la suma de un subconjunto.

A continuación, el paso inductivo: dado $a_1\leq ...\leq a_n$ sabemos que $\sum_{k=1}^{n-1} a_k=S_{n-1}\geq n-1$ ya que cada $a_k\geq 1$ y por la hipótesis de inducción, estos $n-1$ puede formar cualquier número entre $0$ y $S_{n-1}\geq n-1\geq a_n-1$ . Así, junto con $a_n$ pueden formar cualquier número entre $0$ y $a_n-1$ pero también entre $a_n+0$ y $a_n+S_{n-1}=\sum_{k=1}^n a_k$ . Hecho.

En particular, en la configuración de la pregunta, podemos hacer subconjuntos de la $a_k$ a cualquier número entre $0$ y $2N$ . En particular $N$ .