Un problema de matemáticas discretas (relacionado con el principio de encasillamiento)

Question

Esta pregunta es de la prueba de elección múltiple:

Una región circular está dividida por 5 radios en sectores, como se muestra arriba. Se eligen 21 puntos en la región circular, ninguno de los cuales está en ninguno de los 5 radios. ¿Cuál de las siguientes afirmaciones debe ser cierta?

I. Algún sector contiene al menos 5 de los puntos

II. Algún sector contiene como máximo 3 de los puntos.

III. Algún par de sectores adyacentes contiene un total de al menos 9 de los puntos.

Aquí me interesa sobre todo la III (no es difícil demostrar que la I es verdadera, mientras que la II no lo es). Intuitivamente, III también es verdadera. Pero aquí están mis preguntas:

• Cómo probar ¿que el III es cierto? (¿Se puede utilizar aquí el principio del encasillamiento?)

• ¿Con qué temas/teoremas/principios está relacionado el enunciado III de este problema en la combinatoria?

Answer 1

Para el III, el principio de encasillamiento funcionará muy bien. Llama a los sectores, en orden antihorario, $1$ , $2$ , $3$ , $4$ , $5$ .

Dejemos que $P_1$ , $P_2$ y así sucesivamente hasta $P_5$ sea el número de puntos de estos sectores.

Mira la suma $$(P_1+P_2)+(P_2+P_3) +(P_3+P_4) +(P_4+P_5)+(P_5+P_1)$$ que es la suma de los números de los puntos de los sectores adyacentes.

Es fácil ver que esta suma es $42$ por lo que el promedio de los componentes es de $8.4$ que es mayor que $8$ . Pero cada componente es un número entero, por lo que al menos una de las sumas es $9$ o más.

Comentario : Prefiero la siguiente variante. Cinco personas están sentadas alrededor de una mesa redonda. Entre ellos tienen $21$ monedas de diez centavos. Demuestra que hay dos personas sentadas una al lado de la otra que entre las dos tienen al menos $9$ monedas de diez centavos.

Nótese que la solución aprovechó la simetría circular. La simetría es nuestra amiga. En la resolución de problemas, es útil "romper la simetría" lo más tarde posible, o no hacerlo.

Answer 2

Para cada radio defina una cantidad de puntos que es la suma de la cantidad de puntos de los sectores adyacentes. Entonces está claro que la suma de los cinco puntos debe ser 42, ya que cada punto se cuenta dos veces. Por lo tanto, por el mismo razonamiento que demuestra I, ahora se puede demostrar que al menos uno de estos pointcount debe ser mayor o igual a 9 QED.

Answer 3

Supongamos que III no es cierto. Por I, podemos encontrar un segmento con al menos 5 puntos, llame a este número de puntos x. Como estamos asumiendo que III no es cierto, cada uno de los segmentos junto al segmento con x en él puede tener a lo sumo 8-x puntos en él.

En los tres segmentos hasta ahora, hemos contabilizado x + (8-x) + (8-x) puntos, es decir, 16-x puntos. Los dos segmentos restantes deben tener 21 - (16-x) puntos, es decir, 5+x puntos. Como x es 5 o más, estos dos últimos segmentos deben tener 10 o más puntos. Esto es contrario a nuestra suposición, por lo que III debe ser cierto.