IMO 2020 Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 186
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 4
Nivel: 3

IMO 2020 Problema 6

Mensaje sin leer por Sandy »

Pruebe que existe una constante positiva $c$ para la que se satisface la siguiente afirmación:
Sea $n>1$ un entero y sea $\mathcal{S}$ un conjunto de $n$ puntos del plano tal que la distancia entre cualesquiera dos puntos diferentes de $\mathcal{S}$ es al menos $1$. Entonces existe una recta $\ell$ separando $\mathcal{S}$ tal que la distancia de cualquier punto de $\mathcal{S}$ a $\ell$ es al menos $cn^{-\frac{1}{3}}$.
(Una recta $\ell$ separa un conjunto de puntos $\mathcal{S}$ si $\ell$ corta a alguno de los segmentos que une dos puntos de $\mathcal{S}$.)

Nota. Los resultados más débiles que se obtienen al sustituir $cn^{-\frac{1}{3}}$ por $cn^{-\alpha}$ se podrán valorar dependiendo del valor de la constante $\alpha>\frac{1}{3}$.
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: IMO 2020 Problema 6

Mensaje sin leer por Prillo »

Spoiler: mostrar
Sean $X$ e $Y$ los dos puntos de $S$ mas lejanos, y sea $d$ su distancia. Sin perdida de generalidad $X=(0,0)$ e $Y=(d,0)$. Sea $x$ la recta que pasa por $X$ e $Y$ (el eje $x$). Notar que como $X$ e $Y$ son los mas lejanos, la proyeccion de cualquier otro punto de $S$ sobre la recta $x$ cae entre $X$ e $Y$.

Supongamos primero que $d$ es muy grande: $d\ge n^{2/3}$. Proyectamos todos los puntos de $S$ sobre la recta $x$. Debe haber un par de proyecciones consecutivas a distancia al menos $\frac{1}{n}d \ge n^{-1/3}$. La mediatriz $l$ de esas dos proyecciones esta a distancia al menos $\frac{1}{2}n^{-1/3}$ de cualquier punto de $S$.

Ahora supongamos que $d$ es chico: $d\le n^{2/3}$. Sea $\Omega$ la circunferencia centrada en $Y$ de radio $d$. Sea $P$ en el segmento $XY$ tal que $XP=1$ (o sea $P=(1,0)$). Vamos a ver que hay pocos puntos de $S$ cuya proyeccion cae en el segmento $XP$. Sea $h$ la perpendicular a $x$ por $P$. Los puntos de $S$ cuya proyeccion cae en el segmento $XP$ deben estar adentro de $\Omega$ (por la maximalidad de $XY$), y en el semiplano determinado por $h$ que contiene a $X$. Sea $R$ esta region. Veremos que $R$ contiene pocos puntos de $S$. Sea $Q$ una de las intersecciones de $\Omega$ con $h$. Por Pitagoras, $PQ=\sqrt{QY^2-PY^2}=\sqrt{d^2-(d-1)^2}=\sqrt{2d-1}\le \sqrt{2d}\le \sqrt{2}n^{1/3}$ (asi que la region $R$ es `chica'). Para cada punto de $S$ que esta en $R$, coloquemos un disco de radio $1/2$ (que tiene area $\frac{\pi}{4}$). Estos discos no se solapan por la hipotesis del enunciado. Sobresalen de $R$ a lo sumo $1/2$ en cualquier direccion, asi que estan contenidos en el rectangulo $[-1/2, 3/2]\times [-PQ-1/2,PQ+1/2]$, que como $PQ\le \sqrt{2}n^{1/3}$ tiene area a lo sumo $4\sqrt{2}n^{1/3}+2\le 8n^{1/3}$. Se sigue que si $k$ es la cantidad de puntos de $S$ en $R$, entonces $8n^{1/3} \ge \frac{\pi}{4}k$, o sea $k\le \frac{32}{\pi}n^{1/3}$. Asi que por el mismo argumento de antes, dos de estas proyecciones consecutivas (incluyendo a $P$) estan a distancia al menos $\frac{\pi}{32}n^{-1/3}$ y entonces su mediatriz $l$ deja todo punto a distancia al menos $\frac{\pi}{64}n^{-1/3}$.

Para terminar, tomamos $c=\min \left (\frac{1}{2},\frac{\pi}{64}\right )$ para ganar en los dos casos.

Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 205
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: IMO 2020 Problema 6

Mensaje sin leer por Matías »

$\alpha=\frac{1}{2}$
Spoiler: mostrar
Sean $A$ y $B$ dos de los $n$ puntos en el plano tales que su distancia $AB=d$ sea la mayor entre cualesquiera dos puntos.

De esta manera, tenemos que los $n$ puntos pertenecen al rectángulo de $2d\times d$ con base media $AB$ (cualquier punto fuera de este rectángulo está a una distancia de $A$ o de $B$ mayor a $d$).

Más aún, los $n$ círculos con centro en los puntos de radio $\frac{1}{2}$ están incluidos en el rectángulo de $(2d+1)\times (d+1)$ que se aleja en $\frac{1}{2}$ de los lados del rectángulo anterior.

Como cada par de círculos tiene a lo sumo un punto en común (ya que la distancia entre sus centros es mayor o igual a $1$), sus áreas son disjuntas, y como cada círculo tiene área $\frac{π}{4}$, la suma de sus áreas, que es $n\frac{π}{4}$, es menor o igual que el área del rectángulo, que es $(d+1)(2d+1)$, por lo tanto $d\geq\sqrt{n}\frac{\sqrt{π}}{2\sqrt{2}}-1\implies d\geq\sqrt{n}\frac{\sqrt{π}}{4\sqrt{2}}$ (ya que $d\geq 1$).

Y si proyectamos los $n$ puntos en el segmento $AB$ (así es ya que los puntos pertenecen al rectángulo de base media $AB$), lo vamos a dividir en $n-1$ segmentos, entre los cuales habrá uno con longitud de al menos $\frac{d}{n-1}\geq\frac{d}{n}\geq\frac{\sqrt{π}}{4\sqrt{2}\sqrt{n}}$, por lo tanto la mediatriz de ese segmento separará a los $n$ puntos de manera que la distancia de cada punto a esa recta será de al menos $\frac{\sqrt{π}}{8\sqrt{2}\sqrt{n}}=cn^{-\frac{1}{2}}$, siendo $c=\frac{\sqrt{π}}{8\sqrt{2}}$
1  

Responder