OFO 2020 Problema 14

Problemas que aparecen en el Archivo de Enunciados.
14carlosoto

OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Mención Especial-FOFO 6 años FOFO Pascua 2017 - Mención-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Plata-OFO 2018
FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 OFO - Jurado-OFO 2020
Mensajes: 22
Registrado: Mar 15 Sep, 2015 7:54 pm
Medallas: 7
Nivel: 2

OFO 2020 Problema 14

Mensaje sin leer por 14carlosoto »

Se tienen $2^{180}+1$ puntos en el plano. Demostrar que existen $3$ de ellos que determinan un ángulo de al menos $179^{\circ}$ y a lo sumo $180^{\circ}$.
1  
14carlosoto

OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Mención Especial-FOFO 6 años FOFO Pascua 2017 - Mención-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Plata-OFO 2018
FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 OFO - Jurado-OFO 2020
Mensajes: 22
Registrado: Mar 15 Sep, 2015 7:54 pm
Medallas: 7
Nivel: 2

Re: OFO 2020 Problema 14

Mensaje sin leer por 14carlosoto »

Aquí vamos a publicar la solución oficial.
4  
14carlosoto

OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Mención Especial-FOFO 6 años FOFO Pascua 2017 - Mención-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Plata-OFO 2018
FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 OFO - Jurado-OFO 2020
Mensajes: 22
Registrado: Mar 15 Sep, 2015 7:54 pm
Medallas: 7
Nivel: 2

Re: OFO 2020 Problema 14

Mensaje sin leer por 14carlosoto »

SOLUCIÓN OFICIAL:
Spoiler: mostrar
Sea $P$ el conjunto de puntos. Vamos a definir algunas cosas:

Decimos que el ángulo entre dos puntos, notado por $\angle p q$, será el ángulo (en sentido antihorario) entre la semirrecta que comienza en $p$ y va hacia la derecha y la semirrecta $\overline{pq}$. Notmos que $\angle pq \neq \angle qp$, y además uno de ellos será siempre menor a $180^\circ$ y el otro al menos $180^\circ$, ya que ambos suman $360^\circ$. Notemos también que $p\hat{q}r = 180^\circ + \angle pq - \angle qr$, como se ve en la figura 1:

Imagen

Diremos que $A_{p, \alpha} = \{q \in P - \{p\} : \alpha \leq \angle p q < \alpha + 1^\circ\}$ es el conjunto de puntos que forman un ángulo de entre $\alpha$ y $\alpha+1^\circ$ con respecto a $p$; o, en otras palabras, el conjunto de puntos en una región del plano delimitada por dos semirrectas que salen desde $p$, con un ángulo de $1^\circ$ entre ellas, como la marcada en la figura 2.

Imagen

Para cada $p \in P$ vamos a construirnos un subconjunto $S_p \subseteq \{0, \dots 179\}$ definido de la siguiente manera: $i \in S_p \iff A_{p, i^\circ} \neq \emptyset$. En otras palabras, tomamos un ``abanico'' centrado en $p$ que va para arriba, y nos fijamos cuáles de sus secciones encontramos algún otro punto, como el mostrado en la figura 3.

Imagen

Lema 1: Habrá dos puntos $p, q \in P; p \neq q$ tal que $S_p = S_q$. Esto es fácil de ver ya que como $S_p, S_q \subseteq \{0, \dots, 179\}$, los conjuntos $S_i$ tienen a lo sumo $2^{180}$ posibilidades, y entonces como hay $2^{180}+1$ puntos, por palomar, habrá uno repetido. $\blacksquare$.

Ahora sean $p, q \in P; p \neq q$, con $S_p = S_q$. Asumamos sin pérdida de generalidad que $\angle p q < 180^\circ$, y sea $i \in \{0, \dots, 179\}, i = \lfloor \angle p q \rfloor$ el piso del ángulo en grados, tal que $i^\circ \leq \angle pq < i^\circ + 1^\circ$. Tenemos entonces una situación como la que muestra la figura 4.

Imagen

Tendremos luego que $q \in A_{p, i^\circ}$, por lo que $i \in S_p$, pero luego $i \in S_q$. Sea entonces $r \in P$ tal que $r \in A_{q, i^\circ}$.

Luego tenemos que $i^\circ \leq \angle pq, \angle qr < i^\circ + 1^\circ$. Luego su diferencia es a lo sumo $1^\circ$. Entonces tenemos que:

$$-1^\circ < \angle pq - \angle qr < 1^\circ$$
$$179^\circ < 180^\circ + \angle pq - \angle qr < 181^\circ$$
$$179^\circ < p\hat{q}r < 181^\circ$$

Luego hay dos puntos con un ángulo mayor a $179^\circ$. $\blacksquare$.
9  
Responder