Número máximo de miembros en el club de matemáticas

Dejar$M$Sea el subconjunto máximo de estudiantes, no hay dos en él que sean enemigos. Luego, cada estudiante que no esté en$M$tiene al menos un enemigo en$M$y cada uno en$M$tiene exactamente dos enemigos en$G\setminus M$. Así que por doble conteo tenemos

Ahora para el límite superior. Si consideramos este grupo$G$de estudiantes como un gráfico cuando dos vértices están conectados si son enemigos, entonces vemos que este gráfico es, ya que cada vértice tiene un grado exactamente$2$, unión disjunta de algunos ciclos$C_1,C_2,...C_k$. Desde$\varepsilon = 40$tenemos

Todos los valores entre$14$y$20$puede lograrse:

• Para$|M|=14$tomar cada segundo vértice en$C_{4}$y un vértice de cada uno de los doce$C_3$.
• Para$|M|=15$tomar cada segundo vértice en$C_{10}$y un vértice de cada uno de diez$C_3$.
• Para$|M|=16$tomar cada segundo vértice en$C_{16}$y un vértice de cada uno de ocho$C_3$.
• Para$|M|=17$tomar cada segundo vértice en$C_{22}$y un vértice de cada uno de los seis$C_3$.
• Para$|M|=18$tomar cada segundo vértice en$C_{28}$y un vértice de cada uno de los cuatro$C_3$.
• Para$|M|=19$tomar cada segundo vértice en$C_{34}$y un vértice de cada uno de dos$C_3$.
• Para$|M|=20$tomar cada segundo vértice en$C_{40}$.

Entonces, el resultado es$119$.

Suponga que ordena a los estudiantes que entren en "bucles enemigos". Por ejemplo, comience con un estudiante (a quien le daremos el nombre 1) y elija al azar a los enemigos de uno (a quien le daremos el nombre 2). Luego, elegimos al enemigo de 2 que no era 1, y continuamos hasta que cerramos el ciclo llegando al otro enemigo de 1.

Las siguientes afirmaciones son válidas:

1. Cada estudiante estará exactamente en un ciclo. Esto se debe a que cada estudiante tiene exactamente dos enemigos, y la propiedad del enemigo es mutua entre los estudiantes.

2. Cada bucle contendrá al menos tres estudiantes. Esto se debe a que todos los enemigos, si todos los miembros de un ciclo, serán miembros del mismo ciclo.

3. Debe haber un número par de bucles de tamaño impar. Esto se debe al hecho de que el número total de estudiantes es par y que cada estudiante debe estar exactamente en un bucle.

4. Si un bucle tiene$N$estudiantes, no más de$\lfloor \frac N2\rfloor$los estudiantes de ese bucle pueden estar en el club. Esto se puede demostrar mediante el uso del principio del casillero.

5. Como resultado de lo anterior, M puede tomarse sumando$\lfloor \frac N2\rfloor$sobre cada bucle.

6. La combinación de dos bucles pares en un bucle par más grande no tiene impacto en el valor de M. La combinación de un bucle de tamaño par con un bucle de tamaño impar no tiene impacto en el valor de M. La combinación de dos bucles de tamaño impar en un bucle de tamaño par aumenta$M$por uno. Esto se debe a que la operación de piso solo afecta el valor si el tamaño del bucle es impar, en cuyo caso reduce su argumento en$\frac 12$.

7. Podemos dividir a nuestros alumnos en un máximo de 13 bucles, de los cuales un máximo de 12 pueden ser impares.

Con base en estas afirmaciones, podemos afirmar que dependiendo de la distribución de la enemistad, podemos tener desde$M=14$a$M=20$, por lo que el total de todos los valores posibles de$M$es$\sum_{M=14}^{20}M$=119.