Una pregunta relacionada con el principio de encasillamiento

Question

En una habitación hay $10$ personas, ninguna de las cuales es mayor de $60$ pero cada uno de los cuales es al menos $1$ años. Demuestra que siempre se pueden encontrar dos grupos de personas (sin ninguna persona en común) cuya suma de edades sea la misma.

Mi enfoque: Hay $2^{10}=1024$ subconjuntos, $1023$ subconjuntos no vacíos. Por lo tanto, hay $1023$ sumas de edades y cada suma está entre $1$ y $600$ . Entonces hay $600$ valores posibles, pero $1023$ sumas. Por lo tanto, al menos dos de ellos deben ser iguales, es decir, existen subconjuntos diferentes $\{P_{i1}, \ldots, P_{in}\}$ y $\{P_{j1}, \ldots, P_{jn}\}$ tal que la suma de las edades concuerde. Ahora quita las personas presentes en ambos subconjuntos.

Puede $10$ ¿se sustituye por un número menor de personas?

Supongo que no puede. Por ejemplo, si hubiera $9$ gente, entonces tendría $2^9-1 = 511$ subconjuntos adecuados y como ahora tengo $9\cdot 60=540$ totales posibles, no está garantizado que existan dos grupos disjuntos de personas tales que la suma de sus edades sea la misma.

¿Estoy en lo cierto?

Answer 1

Como han señalado Ross y otros, tu argumento para 10 personas está bien. Para demostrar que es pas posible encontrar dos grupos de este tipo de 9 o menos personas, debería exhibir un conjunto de 9 personas que no tenga dos subconjuntos de este tipo, o al menos demostrar de alguna manera que dicho conjunto de 9 personas existe.

Por desgracia, según una búsqueda informática de fuerza bruta que realicé, no parece existir tal contraejemplo: no hay forma de asignar números entre 1 y 60 a 9 personas de manera que no haya dos subconjuntos con la misma suma. De hecho, tampoco parece haber ningún contraejemplo de 8 personas.

Sin embargo, es fácil encontrar contraejemplos de 7 personas: $(1, 2, 4, 24, 40, 48, 56)$ y $(60, 59, 58, 56, 53, 47, 36)$ son dos de ellos. Así que ahora la pregunta interesante es, ¿hay alguna manera de demostrar que un contraejemplo de 8 personas no puede existir sin ¿una búsqueda exhaustiva?

Answer 2

Aquí hay una prueba (no exhaustiva) de que no existe un conjunto de 9 personas. Se trata de un conjunto más restrictivo, para reducir en gran medida el número de encasillamientos.

Que las edades del pueblo sean (WLOG) $1 < a_1 < a_2 < \ldots a_9 \leq 60$ . Tienen que ser distintos, de lo contrario estamos acabados.

Considera todos los subconjuntos con al menos 1 persona. Hay $2^9 - 1 = 511$ tales conjuntos. Estas son nuestras palomas, anteriormente 512. La diferencia entre la mayor y la menor suma de edades es $a_2 + a_3 + \ldots a_9 \leq 452$ . Por lo tanto, la suma de las edades puede tomar como máximo 453 valores diferentes. Estos son nuestros casilleros, anteriormente 540. Por lo tanto, por el principio de los casilleros, hay 2 conjuntos con la misma suma. Ahora tomamos la diferencia de conjuntos, para asegurarnos de que obtenemos 2 grupos sin personas comunes.

Este enfoque no se extiende a demostrar que un conjunto de 8 personas no existe, como afirma Ilmari.

Answer 3

Para el $10$ parte estás bien. Para el $9$ parte, no has demostrado que se pueda hacer, sólo que este planteamiento no es suficiente para descartarlo. Una forma de terminar el $9$ parte es mostrar un conjunto de $9$ números que no se puede encontrar tal conjunto de subconjuntos. Después de buscar un poco no he encontrado ninguno.

Answer 4

Un grupo de $9$ es suficiente para obtener grupos de edad coincidentes, utilizando una pequeña extensión en la estimación del rango de sumas posibles.

Como se observa el número de subconjuntos no vacíos será $2^9-1=511$ y, como antes, podemos suponer que todas las edades son diferentes, ya que, de lo contrario, podemos utilizar dos personas con la misma edad para lograr nuestro objetivo.

Ahora considere la persona más joven, con una edad de $y$ - este es el límite inferior de las sumas de edad posibles. El límite superior es entonces como máximo $y+\sum_{53}^{60}i = y+452$ . Por lo tanto, hay $453$ o menos sumas de edad diferentes disponibles para los distintos grupos y, por tanto, se aplica el principio de encasillamiento, en el que dos grupos deben tener la misma suma de edad.

---

Está claro que también podemos ampliar el límite de edad: $9$ personas hasta la edad de $67$ seguirá produciendo grupos con una suma de edad común a partir de este proceso todavía bastante sencillo.

A costa de sacrificar algunos subconjuntos menos útiles, podemos reducir también el rango de los totales. Está claro que el conjunto completo no va a coincidir con ningún otro subconjunto, y tampoco lo va a hacer ningún subconjunto al que le falte una sola persona, a no ser que esa persona sea la más antigua. Así que en un grupo de $n$ personas que podemos descartar $n$ subconjuntos y reducir el total más alto posible por el límite de edad. Así, por ejemplo, para $10$ personas, teniendo en cuenta la $1013$ grupos definidos bajo este proceso podemos imponer un límite de edad de $130$ ya que el rango de totales factibles de nuestros subconjuntos elegidos es $y$ a $y+\sum_{122}^{129}i = y+251\cdot 4 = y+1004$ para $1005$ totales posibles, lo que permite el argumento del encasillamiento.

Los límites de edad correspondientes para algunos grupos más pequeños son:

$$\begin{array}{c|c|c} \text{# people} & \text{# useful subsets} & \text{age limit}\\ \hline 10 & 1013 & 130 \\ 9 & 502 & 75\\ 8 & 247 & 44\\ 7 & 120 & 26\\ 6 & 57 & 16\\ 5 & 26 & 10 \end{array}$$

Pero hay que tener en cuenta que estos límites de edad son probablemente subestimaciones. Por ejemplo, en el último caso, la lógica para conseguirlo ha supuesto que tenemos edades de $\{10,9,8,7\}$ que producen inmediatamente dos grupos de igual suma de edades ( $10+7=9+8$ ). De hecho, dejar sólo una edad "final joven" puede producir enormes huecos en las posibles sumas de edad (menos huecos para nuestras palomas). Así que es totalmente probable que los límites de edad sean algo más altos y no me sorprende la afirmación de que un grupo de $8$ podría tener un límite de edad de $60$ y seguir teniendo necesariamente grupos de la misma edad.

Answer 5

En su solución, ha mencionado que la suma máxima es de 60. Pero fíjate que si hubiera dos personas de la misma edad, entonces ya hemos terminado, ya que podemos elegir fácilmente a las dos personas como un grupo distinto. Así que debería ser distinto, es decir, suma máxima= $\displaystyle\sum_{i=0}^9 (51+i)=\dfrac{10}{2}(51+60)=555$ . Pero aquí viene la sorpresa, la suma mínima = $\displaystyle\sum_{i=0}^9 (1+i)=\dfrac{10}{2}(1+10)=55$ y el número total de sumas utilizando el principio de inclusión y exclusión obtenemos, $555-55+1=501$ . Aquí vemos que $2^9-1=511$ De ahí que @Ilmari Karonen no haya encontrado ningún problema con el conjunto de 9 números con su algoritmo de fuerza bruta.

Pero no hemos terminado aquí, observe que $2^8-1=255<501$ . Simplemente implica que siempre podemos encontrar un subconjunto tal que no haya 2 grupos de personas que tengan la misma edad. Aquí hemos reducido el número de sumas posibles, lo cual es muy importante ya que no obtenemos las posibilidades reducidas ignorando todos los casos imposibles. Se puede intentar demostrar que no es posible obtener un conjunto de 8 números.