OBM 2018 - Nível 3 - P6

Problema 6

Considere $4n$ pontos no plano, sem três colineares. Utilizando esses pontos como vértices, podemos formar $4n\choose 3$ triângulos. Mostre que existe um ponto $X$ do plano que pertence ao interior de pelo menos $2n^3$ desses triângulos.

Solução de Caio Hermano:

Seja $S$ o conjunto dos $4n$ pontos dados e considere uma reta $l$ que não é paralela a nenhuma reta determinada por dois pontos de $S$ (isto é possível, pois há uma quantidade finita de retas, ou seja, uma quantidade finita de coeficientes angulares que elas representam no plano cartesiano, enquanto existem infinitos ângulos reais entre $0$ e $\pi$).

Lema 1: Existe uma reta $s$ paralela a $l$ tal que $s$ divide o plano em duas regiões, cada uma contendo exatamente $2n$ dos pontos de $S$.

Prova: Para todo ponto $P\in S$, considere a reta $k$ passando por $P$ e paralela a $l$. Perceba que $k$ é única para cada $P$, uma vez que $l$ não é paralela a nenhuma reta que passa por dois pontos de $S$. Chame de $L=\{l_1,l_2,...,l_{4n}\}$ o conjunto contendo todas as tais retas e ordene-as de forma crescente respectivo às abscissas dos pontos de interseção dessas retas com o eixo $x$ do plano cartesiano (a não ser que $l$ seja paralela eixo $x$, nesse caso considere as ordenadas dos pontos de interseção dessas retas com o eixo $y$), de tal modo que a reta $l_i$ esteja localizada na região do plano delimitada pelas retas $l_{i-1}$ e $l_{i+1}$, para todo $i=2,3,...,4n-1$.

Assim, tome a reta $s$ como sendo qualquer reta paralela a $l$ que esteja localizada estritamente entre as retas $l_{2n}$ e $l_{2n+1}$. Ela satisfará as condições do Lema, pois um de seus semiplanos conterá os $2n$ pontos de $S$ que determinam as retas $l_1,l_2,...,l_{2n}$ (chame esse semiplano de esquerda), enquanto o outro conterá os $2n$ pontos de $S$ que determinam as retas $l_{2n+1},l_{2n+2},...,l_{4n}$ (chame esse semiplano de direita), como queríamos demonstrar.

Lema 2: Existe uma reta $t$ tal que as retas $s$ e $t$ dividem o plano em quatro regiões, cada uma com exatamente $n$ pontos de $S$.

Prova: Inicialmente, considere $t=l_{2n}$ e o seu ponto de $S$ como o pivô. Gire $t$ no sentido horário ao redor do pivô $T$ até que a reta encontre pela primeira vez um outro ponto de $S$, que denotaremos por $U$. Com $U$ como novo pivô, a reta $t$ continua a rodar no sentido horário até encontrar outro ponto de $S$. Este processo continua sem parar, sendo sempre o pivô algum ponto de $S$.

Primeiramente, note que a quantidade de pontos de $S$ em cada semiplano de $t$ é invariante (a não ser quando $t$ passa por dois pontos de $S$), pois sempre que ele encontra um novo pivô, o antigo se encontrará no mesmo semiplano que o novo pivô antes ocupava, como ilustrado na figura acima.

Além disso, se pintarmos todos os $2n$ pontos à esquerda de $s$ de vermelho, observe que a quantidade de pontos vermelhos em cada semiplano de $t$ sempre decresce em $1$ unidade, permanece a mesma ou cresce em $1$ unidade, pois cada troca de pivôs consiste em tirar um ponto e adicionar outro em algum dos semiplanos de $t$, ou seja, no pior dos casos, eu tiro um vermelho e adiciono um não-vermelho ($-1$), no melhor dos casos, eu tiro um não-vermelho e adiciono um vermelho ($+1$) ou eu tiro um vermelho e adiciono um vermelho ou tiro um não-vermelho e adiciono um não-vermelho ($=$).

No início, temos que $t=l_{2n}$, então não há nenhum ponto vermelho à direita de $t$ e sempre haverá $2n-1$ pontos de $S$ à esquerda de $t$ e $2n$ à direita de $t$. Perceba que, no momento em que $t$ tiver girado exatamente $180$°, a sua atual esquerda será a sua antiga direita e a sua atual direita será a sua antiga esquerda, além de termos que $t\parallel s$, que $t$ passa por algum ponto de $S$ ($t=l_i$, para algum $i$) e que há precisamente $2n-1$ pontos à sua esquerda e $2n$ à sua direita $\Rightarrow t=l_{2n+1}$. Nesse momento, há $2n$ pontos vermelhos à direita de $t\Rightarrow$ Como inicialmente havia $0$ ponto vermelho à direita de $t$, por Continuidade Discreta, em algum momento, houve exatamente $n$ pontos vermelhos à direita de $t$.

Nesse exato instante, havia precisamente $n$ pontos vermelhos e $n$ pontos não-vermelhos à direita de $t$, pois sempre há $2n$ pontos à direita de $t$. Translade $t$ para a sua direita apenas o suficiente para que o seu pivô fique à sua esquerda, sem passar por nenhum outro ponto de $S$. Agora, veja que há exatamente $n$ pontos vermelhos e $n$ pontos não-vermelhos em cada semiplano de $t$, isto é, $s$ e $t$ dividem o plano em quatro regiões, cada uma contendo exatamente $n$ pontos de $S$, como queríamos demonstrar.

Voltando para o problema...

Denote as quatro regiões delimitadas pelas retas $s$ e $t$ por $\mathbb{A},\mathbb{B},\mathbb{C},\mathbb{D}$ no sentido horário e tome o ponto $X$ como sendo a interseção das retas $s$ e $t$. Podemos supor que $X$ não está em nenhuma reta que conecta dois pontos de $S$, pois caso contrário, basta transladar $s$ e $t$ em qualquer direção apenas o suficiente para que $X$ saia da reta em que estava, mas não se encontre em nenhuma outra, e $s$ e $t$ não passem por nenhum ponto de $S$. Vejamos que, agora, $X$ satisfaz as condições do enunciado:

Escolha dois pontos $P,Q\in S$, tais que $P\in \mathbb{A}$ e $Q\in \mathbb{C}$. Note que $X$ deve estar no mesmo semiplano delimitado pela reta $\overline{PQ}$ que apenas uma dentre as regiões $\mathbb{B}$ ou $\mathbb{D}$ ($X\not\in \overline{PQ}$), suponha, sem perda de generalidade, que é a região $\mathbb{B}$. Então, observe que, para qualquer um dos $n$ pontos $R\in\mathbb{B}$, temos que $X$ está no interior do triângulo $PQR$. Portanto, cada par de pontos em $\mathbb{A}\times\mathbb{C}$ gera, pelo menos, $n$ triângulos distintos que contêm o ponto $X$, ou seja, encontramos, ao todo, $n\cdot n\cdot n=n^3$ triângulos que contêm $X$.

De forma análoga, cada par de pontos em $\mathbb{B}\times\mathbb{D}$ gera, pelo menos, $n$ triângulos que contêm o ponto $X$, o que, por sua vez, gera um total de $n^3$ novos triângulos que contém o $X$. Perceba que nenhum triângulo foi contado duas vezes, pois os primeiros $n^3$ triângulos possuem um vértice em $\mathbb{A}$, um vértice em $\mathbb{C}$ e apenas um vértice em $\mathbb{B}\cup\mathbb{D}$, enquanto os últimos $n^3$ triângulos possuem um vértice em $\mathbb{B}$, um vértice em $\mathbb{D}$ e apenas um vértice em $\mathbb{A}\cup\mathbb{C}$.

Logo, o ponto $X$ está no interior de, ao menos, $n^3+n^3=2n^3$ triângulos distintos com vértices nos pontos de $S$, como queríamos demonstrar $_{\blacksquare}$

Observação: A prova do Lema 2 foi fortemente baseada no Problema 2 da IMO 2011, também conhecido na comunidade olímpica como "Problema do Moinho-de-vento" ou "Windmill Problem". Caso queira saber mais acerca dessa questão, recomendamos que assista ao vídeo produzido pelo 3Blues1Brown linkado a seguir: The unexpectedly hard windmill question (2011 IMO, Q2)