Todos los clubes tienen un miembro entre $n$ personas

Question

Dejemos que $n \geq 14$ sea un número entero positivo. En una ciudad hay más de $n$ clubes, todos ellos tienen exactamente 14 miembros. En cada grupo de $n+1$ clubes hay una persona que es miembro de al menos 15 de estos $n+1$ clubes. Demostrar que es posible seleccionar $n$ personas de manera que todos los clubes tengan un miembro entre estas personas.

Esta pregunta es de Hungría. Traté de proceder por inducción en el número $n$ y podría probar el caso base $n=14$ . Sin embargo no sé cómo seguir. Cualquier ayuda es bienvenida.

Answer 1

Elijamos cualquier $n$ clubes, y llamar a esto el conjunto base de los clubes. El resto de los clubes se consideran actualmente descubierto . También tenemos un conjunto de soluciones (actualmente vacío) $S$ donde pretendemos que el conjunto final de $n$ miembros que portada todos los clubes. Repite el siguiente proceso hasta que (1) no haya más palos sin cubrir, o (2) hayamos repetido $n$ tiempos.

1. Elige cualquier club descubierto.
2. Aplicar la condición dada a este conjunto de $n+1$ palos: el juego base + el palo elegido en $(1)$ . Del enunciado del problema, obtenemos un miembro, digamos $M$ que es en al menos $15$ de estos clubes.
3. Añadir $M$ a nuestro conjunto de soluciones $S$ y marcar como cubiertos todos los palos que no estén en el juego base y que tengan $M$ como miembro.

Ahora hay dos casos. O bien (1) ejecutamos los pasos anteriores $k$ tiempos, $k \leq n$ y no tenemos más conjuntos sin cubrir. O (2) ejecutamos los pasos anteriores exactamente $n$ veces, y todavía hay algunos conjuntos sin cubrir.

Caso (1): El único problema es que algunos de los conjuntos básicos podrían no estar cubiertos. Tenga en cuenta que cada uno de los $k$ miembros en $S$ están presentes en al menos $14$ de los conjuntos base. Esto supone al menos $14k$ de las ranuras disponibles $14n$ ranuras en el juego base. Lo que significa que al menos $14k/14 = k$ conjuntos de bases han sido cubiertos, dejándonos con un máximo de $n-k$ conjuntos de bases sin cubrir. Elige un miembro de cada uno de ellos (como máximo) $n-k$ conjuntos base y añadirlos a nuestro conjunto de soluciones $S$ y tenemos un conjunto de soluciones finales válidas.

Caso (2): Tenemos exactamente $n$ miembros en nuestra solución. Cada uno de esos $n$ miembros están presentes en al menos 14 de nuestros conjuntos base, ocupando así al menos $14n$ ranuras base, que resultan ser todas nuestras ranuras base. Por lo tanto, si ahora consideramos lo siguiente $n+1$ clubes: conjunto base + cualquier club descubierto, obtenemos una contradicción a la condición dada en el enunciado del problema.

EDIT: Parece que la elección de $14$ y $15$ en el enunciado del problema es arbitrario, dos números consecutivos cualesquiera habrían servido para el propósito.