Dado $51$ números naturales cuya suma es $100$ , demuestran que es posible dividirlos en $2$ conjuntos tales que cada uno de ellos es $50$ .

Question

Dado $51$ números naturales cuya suma es $100$ .

Mostrar que es posible dividirlos para $2$ conjuntos tales que para cada uno la suma es $50$ .

Además, otra pregunta interesante es, ¿qué pasa que en lugar de números naturales tenemos números enteros?

Nota: Suponiendo aquí que $0$ no cuenta como un número natural.

Answer 1

Reclamación: Si $a_1,\cdots,a_{m+1}$ son números naturales que suman $2m$ entonces podemos encontrar un subconjunto que sume $m.$

Prueba: Por inducción.

Si $m=1$ entonces tenemos dos números naturales, $a_1,a_2$ que suman $2.$ Pero eso sólo puede ser $a_1=a_2=1$ y luego $a_1=1$ es el subconjunto.

Supongamos que es cierto para $m-1,$ con $m>1.$ Dado $a_1,\cdots,a_{m+1}$ números naturales que suman $2m,$ reduciremos la cuestión a un caso de $m-1.$

Sabemos que algunos $a_i=1,$ ya que de lo contrario, $a_i\geq 2$ para todos $i,$ y la suma es al menos $2(m+1)>2m.$

También sabemos que algunos $a_j>1,$ ya que en caso contrario, todos los valores son $1$ y la suma es $m+1<2m,$ desde $m>1.$

Si $a_i=1$ y $a_j>1,$ entonces podemos eliminar $a_i$ y reemplazar $a_j$ con $a_j-1.$ Esto nos da $m=m-1+1$ números naturales que suman $2(m-1).$ Entonces, por la proposición de inducción, debe tener un subconjunto que sume $m-1.$ Pero luego, al sustituir $a_j-1$ con $a_j$ si está en el subconjunto, tenemos un subconjunto que suma $m-1$ o $m.$ Si $m-1,$ añadimos el $1.$

---

Su solicitud es el caso $m=50.$

Podemos encontrar $a_1=a_2=\cdots=a_{m-1}=1$ y $a_m=m+1$ para conseguir $m$ números que suman $2m$ sin un subconjunto que se sume a $m.$ Si $m$ es impar, también podría elegir todo $a_i=2$ y no obtener una suma de $m.$

Podemos mejorar ligeramente este algoritmo para los casos de mayor tamaño $a_j.$

Supongamos que $a_j>1.$ Dejemos que $u$ sea el número de valores $i$ con $a_i=1.$ Entonces:

$$2m=\sum_{i=1}^{m+1} a_i \geq a_j + u + 2(m-u)=a_j+2m-u$$

Así que $u\geq a_j.$ Eso significa que podemos eliminar $a_j-1$ valores $a_i=1$ y reemplazar $a_j$ con $1.$ Entonces tienes $m-(a_j-1)+1$ números naturales que suman $2m-2(a_j-1).$ Puedes encontrar un subconjunto de estos números que sumen $m-(a_j-1).$ Si el subconjunto no contiene el índice $j,$ tomar el complemento para obtener un subconjunto que contenga $j.$ Entonces ese subconjunto funciona para $m,$ también.

Answer 2

Demostraremos que lo anterior se mantiene si incluso permitimos que haya al menos 51 enteros positivos que suman 100.

Primero observamos lo siguiente:

Afirmación 1: Sea $K$ sea el mayor número. Entonces, de los 51 $+m$ números naturales; $m$ un número entero no negativo; que sume 100, debe haber al menos $K$ 1s.

En efecto, dejemos que $J$ sea el número de 1s en los 50 enteros restantes. Entonces los restantes $50+m-J$ los números deben ser al menos 2 y sumar como máximo $100-K-J$ . Así, observamos la desigualdad $2(50+m-J) \le 100-K-J$ que da $J \ge K$ para todos esos $m$ . Por lo tanto, la afirmación 1 es la siguiente. $\surd$

Entonces la afirmación 2 se deduce casi inmediatamente de la afirmación 1

Afirmación 2: El mayor número no puede ser mayor que 50.

En efecto, si el mayor número es $Y \ge 51$ entonces Por la afirmación 1 debe haber al menos $Y-1$ 1s. Pero entonces $Y$ más el $Y-1$ 1s suman más de 100 para todos esos $Y$ . $\surd$

Así que ahora ordena los números de mayor a menor, y deja que $\ell$ sea el mayor número entero tal que el $\ell$ Los números enteros más grandes de la lista no suman más de 50, es decir, la suma es $50-L$ para algún valor no negativo $L$ . Entonces la afirmación 2 implica que $\ell>0$ . Entonces, si $L=0$ hemos terminado, por lo que podemos asumir que $L>0$ .

También podemos suponer que el $\ell$ Los números enteros más grandes no incluyen ningún 1, de lo contrario todos los $50+L$ los números de la lista serían 1 y así sumarían $L$ de estos 1s al $\ell$ números más grandes para obtener una lista que sume exactamente 50. Por lo tanto, podemos suponer que no hay 1s en el $\ell$ números más grandes. Sin embargo, hay que tener en cuenta que $L \le K$ y que, según la reivindicación 1, hay al menos $K \ge L$ 1s, y como acabamos de observar, ninguno de estos $\ge K$ 1s están en la primera $\ell$ números. Así que añade $L$ de los a la $\ell$ números más grandes y sumarán exactamente 50.

Answer 3

Intenta un enfoque codicioso: Deja que $a_1\ge a_2\ge\ldots \ge a_{51}\ge 1$ sean los números naturales dados y supongamos que no es posible encontrar una subsecuencia que sume $50$ . Tenga en cuenta que $a_1\le 50$ porque ya $$51+\underbrace{1+1+\cdots+1}_{50}>100.$$ Si $a_1=50$ Hemos terminado, por lo tanto $a_1\le 49.$ Como ya $$\underbrace{2+2+\cdots+2}_{51}>100,$$ vemos que $a_{51}=1$ . Dejemos que $r$ sea el número de sumandos que son $=1$ . Como se acaba de ver $r\ge1$ . Dejemos que $m$ sea máxima con $$\tag1\sum_{i=1}^{m} a_i\le 49.$$ De lo anterior, $1\le m\le 50$ . Entonces $\sum_{i=1}^{m+1} a_i\ge 51$ . En particular, $a_{m+1}\ge2$ . De ello se deduce que todos los números $=1$ se encuentran entre $a_{m+2},\ldots, a_{51}$ . Por lo tanto, $$49\ge \sum_{i=m+2}^{51}a_i\ge (50-m)\cdot 2-r$$ o de forma equivalente $$\tag2r\ge51-2m .$$ Si $\sum_{i=1}^{m} a_i\ge 50-r$ podemos rellenar con sumandos que son $=1$ para alcanzar una suma de $50$ . Por lo tanto, $\sum_{i=1}^{m} a_i\le 49-r$ . Concluimos que $a_{m+1}\ge r+2$ . Entonces cada sumando en $(1)$ es $\ge r+2$ y por lo tanto $$\tag3m\le \left\lfloor\frac{49}{r+2}\right\rfloor.$$ Sabiendo que $r\ge1$ , $(3)$ nos da $m\le 16$ . Entonces $(2)$ nos da $r\ge19$ entonces $(3)$ da $m\le 2$ entonces $(2)$ da $r\ge47$ entonces $(3)$ da $m\le 1$ en la siguiente ronda obtenemos $r\ge49$ y finalmente $m\le 0$ , contradiciendo $m\ge1$ .

Answer 4

Aquí hay otra variación, haré uso de la declaración que Mike probó: si $K$ es el mayor de los números y $J$ es el número de $1$ 's, entonces $J\geq K$ la suma de todos los números es al menos tan grande como $K + J + 2(50-J)$ Así que $K-J+100\leq 100$ .

Supongamos ahora que tenemos algunos números $a_1,a_2,...,a_{51}$ para los que se cumple la afirmación "existe una división adecuada". Por lo tanto, podemos dividir el $a_i$ en conjuntos $X$ y $Y$ tal que las sumas sobre los elementos de $X$ y $Y$ son $50$ . Podemos construir otro grupo de números sumando $1$ a un número y restando $1$ de otro: $a_1,...,a_i+1,...,a_j-1,...,a_{51}$ . Supongamos que $a_i$ y $a_j$ ambos pertenecen a $X$ o $Y$ . Entonces la antigua división sigue siendo válida. En caso contrario, WLOG supone $a_i\in X$ y $a_j\in Y$ . Entonces la suma sobre $X$ será $51$ y la suma sobre $Y$ será $49$ . Supongamos que hay al menos un $1$ en $X$ . Podemos mover esto $1$ a $Y$ para obtener una división válida. Si no es así, todos los $J$ $1$ están en $Y$ . Elige cualquier elemento $b\in X$ y moverlo a $Y$ . Desde $b\leq K\leq J$ Podemos mover lo suficiente $1$ 's de $Y$ a $X$ para obtener una división válida.
En todos los casos, hemos encontrado una división válida, por lo que la afirmación es válida también para este nuevo grupo de números.

La afirmación es obviamente válida para la solución $1,1,...,1,50$ . Todas las demás soluciones se pueden construir a partir de ésta mediante el procedimiento de incremento/decremento anterior. Por lo tanto, la afirmación es válida para todas las soluciones.