Nível 3 - Fase 3

Problema 1

As bissetrizes internas dos ângulos $A\hat{B}C$ e $A\hat{C}B$ do triângulo $ABC$ se encontram no ponto $I$. A reta paralela a $BI$ que passa pelo ponto $A$ encontra a reta $CI$ no ponto $D$. A reta paralela a $CI$ por $A$ encontra a reta $BI$ no ponto $E$. As retas $BD$ e $CE$ se encontram no ponto $F$. Mostre que $F$, $A$ e $I$ são colineares então $AB = AC$.

Solução

Vamos mostrar que se $F$, $A$ e $I$ são colineares, então, $AB = AC$.

Observe o triângulo $FIC$, como $IC // AE$, pelo Teorema de Tales:

$\dfrac{FA}{AI} = \dfrac{FE}{EC}$

Agora observe o triângulo $FIB$, como $IB // AD$, novamente pelo Teorema de Tales:

$\dfrac{FA}{AI} = \dfrac{FD}{DB}$

Por fim, chame de $N$ o ponto que $AI$ corta $BC$ e utilize o teorema de Ceva no triângulo $FBC$:

$\dfrac{BN}{NC} \cdot \dfrac{EC}{FE} \cdot \dfrac{FD}{DB} = 1$

Pelos resultados anteriormente encontrados:

$\dfrac{BN}{NC} \cdot \dfrac{AI}{FA} \cdot \dfrac{FA}{AI} = 1 \Rightarrow \dfrac{BN}{NC} = 1 \Rightarrow BN = NC$

O ponto $N$ será ponto médio de $BC$. Para finalizar o problema basta aplicarmos o teorema da Bissetriz Interna relativa ao lado $BC$:

$\dfrac{AB}{AC} = \dfrac{BN}{NC}$

Mas $\dfrac{BN}{NC} = 1 \Rightarrow AB = AC$.

Como queríamos demonstrar!

Problema 2:

Encontre o menor $n$ tal que qualquer conjunto de $n$ pontos do plano cartesiano, todos com coordenadas inteiras, contém dois cujo quadrado da distância é um múltiplo de $2016$.

Solução

Sabemos por geometria analítica que a distância $d$ entre dois pontos $A$ e $B$ pode ser obtida em função das coordenadas $x$ e $y$ dos pontos $A$ e $B$ a partir desta equação:

$d=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}$
$d^2=(x_A-x_B)^2+(y_A-y_B)^2$

Chamando $(x_A-x_B)=x$ e $(y_A-y_B)=y$ e sabendo que $d^2 \equiv 0 (mod \ 2016)$ temos:

$x^2-y^2 \equiv 0 (mod \ 2016)$
$x^2 \equiv -y^2 (mod \ 2016)$

Como $2016=2^5\cdot3^2\cdot7=32\cdot9\cdot7$ então $x,y$ satisfazem:

$x^2 \equiv -y^2 (mod \ 7)$ (1)
$x^2 \equiv -y^2 (mod \ 9)$ (2)
$x^2 \equiv -y^2 (mod \ 32)$ (3)

Em (1): se $x^2 \equiv -y^2 (mod \ 7)$ então existe $a$ para tal que $a^2 \equiv -1 (mod\ 7)$, mas sabemos por Legendre que $(\dfrac{-1}{7})=(-1)^\dfrac{7-1}{2}=-1$, portanto $-1$ não é resíduo quadrático, então não existe $a$ tal que $a^2 \equiv -1 (mod\ 7)$, logo a única solução é $x^2\equiv y^2\equiv0(mod\ 7) \Rightarrow x\equiv y\equiv0(mod\ 7)$.

Em (2): se $x^2 \equiv -y^2 (mod \ 9) \Rightarrow x^2 \equiv -y^2 (mod \ 3)$ então existe $a$ para tal que $a^2 \equiv -1 (mod\ 3)$, mas sabemos por Legendre que $(\dfrac{-1}{3})=(-1)^\dfrac{3-1}{2}=-1$, portanto $-1$ não é resíduo quadrático, então não existe $a$ tal que $a^2 \equiv -1 (mod\ 3)$, logo a única solução é $x^2\equiv y^2\equiv0(mod\ 3) \Rightarrow x\equiv y\equiv0(mod\ 3)$.

Em (3): se $x^2 \equiv -y^2 (mod \ 32)$. Olhando os resíduos quadráticos módulo $32$: $0,1,4,9,16,17,25$, vemos que os únicos que satisfazem $x^2 \equiv -y^2 (mod \ 32)$ são $x^2 \equiv y^2 \equiv0(mod \ 32)$ ou $x^2 \equiv y^2 \equiv16(mod \ 32)$, e então $x \equiv y \equiv0(mod \ 8)$ ou $x \equiv y \equiv4(mod \ 8)$.

Daí tiramos que $x$ e $y$ satisfazem estas três equações abaixo:

$x \equiv y \equiv0(mod \ 7)$
$x \equiv y \equiv0(mod \ 3)$
$x \equiv y \equiv0(mod \ 8)$ ou $x \equiv y \equiv4(mod \ 8)$

De onde podemos reduzir para:

$x \equiv y \equiv0(mod \ 168)$ (4) ou
$x \equiv y \equiv84(mod \ 168)$ (5)

Logo precisamos contabilizar o menor número $n$ tal que conseguimos encontrar $x,y$ que satisfazem (4) ou (5). Para isto utilizaremos de argumentos combinatórios. Para isto utilizaremos o PCP e tentaremos descobrir o maior $n'$ tal que o enunciado não é verdade, defina $A_i$ como o conjunto de todos os pontos do plano que possuem sua coordenada $x$ como $x \equiv i(mod \ 168)$ e coloque $i$ variando de $0$ a $167$.

Lema 1: $A_i$ possui no máximo $168$ elementos.

Prova: Caso $A_i$ possua mais que $168$ elementos então existem dois pontos que possuem sua coordenada $y$ com a mesma congruência módulo $168$ e então por (4) encontramos dois pontos que possuem sua distância múltipla de $2016$, algo que não queremos, logo não podemos ter dois elementos de $A_i$ com sua coordenada $y$ de mesma congruência módulo $168$, e então $A_i$ possui no máximo $168$ elementos.

Lema 2: O par de conjuntos $A_i$ e $A_{i+84}$ possuem no máximo 168 elementos juntos.

Prova: Caso $A_i$ e $A_{i+84}$ (perceba que $168+i=i$) possuem mais que $168$ elementos então existem dois pontos que possuem suas coordenadas $y$ em algum dos dois conjuntos diferenciando de $84$ módulo $168$ por PCP onde basta colocar $84$ casas com os pares de números que diferenciam de $84$ módulo $168$ e portanto se tivermos mais que $168$ teremos três na mesma casa e logo teremos dois números diferenciando de $84$ ou três números com a mesma congruência módulo $168$ e então $A_i$ ou $A_{i+84}$ terá dois elementos com mesma coordenada $y$ (absurdo pelo lema 1) logo existem dois números diferenciando de $84$, e então por (5) encontramos dois pontos que possuem sua distância múltipla de $2016$, algo que não queremos, logo não podemos ter dois elementos de $A_i$ e $A_{i+84}$ com suas coordenadas $y$ diferenciando de $84$ módulo $168$, e então $A_i$ e $A_{i+84}$ possuem no máximo $168$ elementos.

Vejamos agora que todos os conjuntos terão no máximo $168\cdot84=14112$ elementos, onde se adicionarmos um elemento ou o lema 1 ou o lema 2 deixará de fazer efeito e então teremos que existem dois pontos que possuem sua distância múltipla de $2016$ e com $14112$ elementos um fácil contra exemplo é colocando $84$ pontos em cada $A_i$ de tal modo que a congruência de suas coordenadas $y$ módulo $168$ sejam $0,1,2,3,...83$. Vejamos que nenhum par de pontos satisfaz (4) ou (5). Logo com $14113$ pontos certamente encontraremos dois que satisfazem ou (4) ou (5) e portanto serão múltiplos de $2016$.

Problema 3:

Seja $k$ um inteiro positivo fixado. Alberto e Beralto participam do seguinte jogo: dado um número inicial $N_0$ e começando por Alberto, eles alternadamente fazem a seguinte operação: trocar um número $n$ por um número $m$ tal que $m<n$ e $n$ e $m$ diferem, na sua representação em base $2$, exatamente em $l$ dígitos consecutivos para algum $l$ tal que $1\le l\le k$. Quem não conseguir jogar perde. Dizemos que um inteiro não negativo $t$ é vencedor quando o jogador que recebe o número $t$ tem uma estratégia vencedora, ou seja, consegue escolher os números seguintes de modo a garantir a vitória, não importando como o outro jogador faça suas escolhas. Caso contrário, dizemos que $t$ é perdedor. Prove que, para todo $N$ inteiro positivo, a quantidade de inteiros não negativos perdedores e menores do que $2^{N}$ é $2^{\left \lfloor N-log_2(min(k,N)) \right \rfloor}$.

Observação: $\left \lfloor x \right \rfloor$ é o maior inteiro menor ou igual a $x$. Por exemplo, $\left \lfloor\pi \right \rfloor=3,14$, $\left \lfloor2 \right \rfloor=2$ e $\left \lfloor-4,6 \right \rfloor=-5$.

Solução:

O problema, infelizmente, não possui solução com o enunciado em tais condições, visto a quebra de lógica em que, fazendo os casos iniciais, vemos um contra exemplo. Para um $k>2$, podemos constatar que $0,1$ sempre serão posições perdedoras e $2,3$ sempre serão posições vencedoras, basta colocar $N=1$ e $N=2$ na fórmula, e basicamente isso contradiz o problema já que podemos ir do $1$ para $0$ e portanto $1$ seria vencedor e qualquer outra interpretação do enunciado é contradita a partir destas quatro posições já definidas. A equipe do Noic espera poder corrigir o problema e resolvê-lo. Sstamos aguardando possíveis correções e pedimos desculpas ao leitor, mas esperamos a compreensão, visto o erro da prova.

Problema 4:

Qual é a maior quantidade de inteiros positivos menores ou iguais a $2016$ que podemos escolher de modo que não haja dois números cuja diferença é $1$, $2$ ou $6$?

Solução

A maior quantidade de inteiros positivos menores ou iguais a $2016$ que podemos escolher de modo que não haja dois números cuja diferença é $1$, $2$ ou $6$ é $576$. Suponha que não, então é pelo menos $577$. Divida os números de $1$ a $2016$ em $288$ “grupos” de $7$ números consecutivos:

$(1,2,3,4,5,6,7),(8,9,10,11,12,13,14),(15,16,17,18,19,20,21),...,(2010,2011,2012,2013,2014,2015,2016)$

Como $577 = 2 \times 288 + 1$, pelo Princípio das Casas dos Pombos um dos grupos terá três números escolhidos. Tome apenas os restos dos números desse grupo na divisão por $7$, pela disposição independentemente do grupo teremos:

$(0,1,2,3,4,5,6)$

Vamos mostrar que é impossível escolher três números desta configuração, para isso vamos dividir o problema em casos, onde em cada um vamos explorar as possibilidades a partir de determinado o primeiro dos três escolhidos (lembrando que não podemos escolher números cuja diferença é $1$, $2$ ou $6$ pelo enunciado do problema):

(0) Caso seja $0$: Restam $3,4,5$.

(1) Caso seja $1$: Restam $4,5,6$.

(2) Caso seja $2$: Restam $5,6$.

(3) Caso seja $3$: Restam $0,6$.

(4) Caso seja $4$: Restam $0,1$.

(5) Caso seja $5$: Restam $0,1,2$.

(6) Caso seja $6$: Restam $1,2,3$.

A partir desses dados, basta mostrar que escolher dois números dentre dois ou três consecutivos gera um absurdo, mas isso, de fato, acontece:

- Dois consecutivos têm diferença $1$.

- Dentre os três consecutivos não podemos escolher dois consecutivos pela preposição anterior, logo resta “descartar” o do meio, mas ainda assim os números restantes terão diferença igual a $2$.

 Analisando novamente os casos, o único que não gera absurdo a partir dessas afirmações é o $(3)$, mas $0$ e $6$ têm diferença $6$, o que também não pode pelo enunciado, logo não podemos escolher $577$ números e o máximo é, de fato, $576$.

 Podemos construir um exemplo escolhendo todos números que deixam resto $3$ ou $6$ na divisão por $7$.

Problema 5:

Considere o polinômio do segundo grau $P(x) = 4x^2 +12x-3015$. Defina a sequência de polinômios $P_{1}(x) = \dfrac{P(x)}{2016}$ e $P_{n+1}(x) = \dfrac{P(P_{n}(x))}{2016}$ para todo inteiro $n\ge1$

(a) Prove que existe um número real $r$ tal que $P_{n}(r) < 0$ para todo inteiro positivo $n$.

(b) Determine a quantidade de inteiros $m$ tais que $P_{n}(m) < 0$ para infinitos inteiros positivos $n$.

Solução:

a) Olhando para as raízes do polinômio $Q(x)=P(x)-2016x$ temos que $x$ satisfaz $4x^2+12x-3015-2016x=0$ logo basta resolver a equação do segundo grau: $4x^2-2004x-3015=0$, onde:

$x=\dfrac{2004\pm\sqrt{(-2004)^2-4\cdot4\cdot(-3015)}}{2\cdot4}$
$x=\dfrac{2004\pm\sqrt{4064256}}{8}$
$x=\dfrac{2004\pm\sqrt{2016^2}}{8}$
$x=\dfrac{2004\pm 2016}{8}$

Logo $x=\dfrac{2004+2016}{8}=502,5$ e $x=\dfrac{2004-2016}{8}=-1,5$, portanto $Q(-1,5)=P(-1,5)-2016\cdot (-1,5)=0 \Rightarrow P(-1,5)=2016\cdot (-1,5)$. Coloque $r=-1,5$, então $P_1(-1,5)=\dfrac{P(-1,5)}{2016}=\dfrac{2016\cdot (-1,5)}{2016}=-1,5$ e portanto $P_1(-1,5)=-1,5$ e indutivamente se $P_n(-1,5)=-1,5$ então $P_{n+1}(-1,5)=\dfrac{P(P_n(-1,5))}{2016}=\dfrac{P(-1,5)}{2016}=\dfrac{2016\cdot (-1,5)}{2016}=-1,5$, logo para todo $n$ vale que $P_n(-1,5)=-1,5$, logo se $r=-1,5$ então $P_n(r)=-1,5<0$ para todo $n$, e portanto achamos o $r$ que queríamos.

Obs.: Antes que o leitor pense que "tiramos do bolso" o polinômio $Q(x)$ observe que é extremamente intuitivo pensarmos na ideia de ponto fixo, ou seja, fazer com que $P_n(x)=x$ para todo $n$ e a partir disto chegaríamos no polinômio $Q(x)$.

b) Primeiramente vejamos que segundo o polinômio $Q(x)$ sabemos que se $x<-1,5$ e $x>502,5$ então $Q(x)>0$, ou seja, $P(x)>2016x$. Esqueça temporariamente a condição $x<-1,5$ e trabalhemos agora apenas com números positivos (estamos fazendo isso pois se $x$ for negativo haverá uma troca no sinal da desigualdade, o que não queremos, mas depois ajeitaremos isto). Então se $x$ é positivo e $x>502,5$ então $P(x)>2016x$.

Lema 1: Se $x>502,5$ então $P_n(x)>0$ para todo $n$.

Prova: Vejamos que se $x>502,5$ então $P(x)>2016x$. Logo $P_1(x)=\dfrac{P(x)}{2016}>\dfrac{P(502,5)}{2016}>\dfrac{2016\cdot (502,5)}{2016}=502,5$, portanto $P_1(x)>502,5$, observe que usamos o fato de que $P(x)>P(502,5)$ para todo $x>502,5$, o que é claramente verdade pois a função $P$ forma uma parábola com concavidade para cima. Indutivamente se $P_n(x)>502,5$ então $P_{n+1}(x)=\dfrac{P(P_n(x))}{2016}>\dfrac{P(502,5)}{2016}>\dfrac{2016\cdot (502,5)}{2016}=502,5$, logo $P_{n+1}(x)>502,5$, e assim $P_n(x)>502,5>0$ para todo $n$, logo nunca teremos $P_n(x)<0$ para $x>502,5$.

Agora olhemos para este lema:

Lema 2: $P(x)=P(-3-x)$ para todo $x$ real.

Prova: Olhemos a coordenada $x$ do vértice ($x_V$) da parábola formada pela função $P$, que é uma parábola. Então sabemos que $x_V=\dfrac{-12}{4\cdot2}=-1,5$. Sabemos além disso que $P(a)=P(b)$ para algum par $a,b$ então como $P$ é uma parábola, vale que $a$ e $b$ possuem a mesma diferença em relação ao $x_V$, ou seja, $\dfrac{a+b}{2}=x_V$, logo temos $a+b=-3 \Rightarrow a=-3-b$, ou seja, $P(-3-b)=P(b)$, para todo $b$ real, como queríamos.

Vejamos agora que pelo lema 2 $P(502,5)=P(-505,5)$, logo como para todo $x>502,5$ vale pelo lema 1 que para todo $n$ teremos $P_n(x)>502,5$, então se $x<505,5$ simetricamente e analogamente teríamos $P(x)>502,5$, o que implicaria pelo lema 1 que para todo $n$ teremos $P_n(x)>502,5$ (é como estivéssemos começando do $P_1(x)>502,5$). A partir desta duas informações, nosso universo de candidatos a solução se reduziu para $x$ entre $-505,5$ e $502,5$, provaremos que todos estes números satisfazem as condições propostas pelo enunciado. Basicamente dividiremos os números em dois grupos, analisando o gráfico de $P$ veremos que existem os números $x$ que possuem $P(x)$ positivo (que estão "acima e abaixo" das raízes) e os que possuem $P(x)$ negativo (que estão entre as raízes). Primeiramente vejamos que as raízes de $P(x)$ são $r_1=\dfrac{12-\sqrt{48384}}{8}$ e $r_2=\dfrac{12-\sqrt{48384}}{8}$. Logo, considerando apenas o universo possível de soluções:

Lema 3: Se $x>r_2$ então para algum $t$ teremos $P_t(x)<0$.

Prova: Considerando $P_n(x)$ como uma sequência provaremos que a mesma sempre decresce e nunca converge para algum ponto. Vendo novamente o polinômio $Q(x)$, sabemos que como aqui $x<502,5$ então $P(x)<2016x$, logo para $n$ qualquer teremos $P_{n+1}(x)=\dfrac{P(P_n(x))}{2016}<\dfrac{2016\cdot P_n(x)}{2016}=P_n(x)$, logo $P_{n+1}(x)<P_n(x)$ e como $P(x)$ possui seu coeficiente de $x^2$ e $x$ positivos, esta diferença entre $P_{n+1}(x)$ e $P_n(x)$ empre aumentará a medida que aumentarmos $n$ e portanto $P_n(x)$ irá sempre decrescer e nunca convergir em algum ponto, portanto em algum momento teremos que para alguém $t$, $P_t(x)<0$, como queríamos.

Vejamos agora que se $x<r_1$ pelo lema 2 teremos uma simetria e então podemos aplicar o lema 3, podendo assim afirmar que para qualquer $x$ que escolhermos, então em algum momento teremos $P_t(x)<0$. Agora para finalizar o problema:

Lema 4: Se $r_1<x<r_2$ então $r_1<P_n(x)<r_2$ para todo $n$.

Prova: vejamos que a coordenada $y$ do vértice da parábola é $y_V=-1,5\cdot2016$, basta olhar que $-1,5$ é raiz de $Q(x)$ e portanto $P(x)=2016x$, no caso $x=-1,5$. Portanto para todo $r_1<x<r_2$ vale que $-1,5\cdot2016<P(x)<0$, logo $P_1(x)=\dfrac{P(x)}{2016}$ e $-1,5<P_1(x)<0$ e indutivamente se $-1,5<P_n(x)<0$ então $P_{n+1}(x)=\dfrac{P(P_n(x))}{2016}$ logo $\dfrac{P(-1,5)}{2016}<P_{n+1}(x)<\dfrac{P(0)}{2016}$, mas $P(-1,5)=-1,5\cdot2016$ e $P(0)<0$. Então $-1,5<P_n(x)<0$ e assim temos que para todo $n$ vale que $P_n(x)<0$.

Pelo lema 3 para todo $x$ teremos que existe $t$ tal que $P_t(x)<0$, mas como $P_t(x)=\dfrac{P(P_{t-1}(x))}{2016}$, mas $-1,5\cdot2016<P(x)$, logo $P_t(x)>-1,5$ e $r_1<P_t(x)<r_2$ e podemos aplicar o lema 4 a partir daí e então teremos infinitos $n$ tais que $P_n(x)<0$. Portanto para todo $x$ tal que $-505,5<x<502,5$ temos que $x$ satisfaz o enunciado, logo existem $1008$ inteiros que satisfazem o enunciado.

Problema 6:

Seja $ABCD$ um quadrilátero convexo, não circunscritível, sem lados paralelos. As retas $AB$ e $CD$ se cortam em $E$. Seja $M\ne E$ a intersecção dos circuncírculos de $ADE$ e $BCE$. As bissetrizes internas de $ABCD$ determinam um quadrilátero convexo cíclico de circuncentro $I$ e as bissetrizes externas de $ABCD$ determinam um quadrilátero convexo cíclico de circuncentro $J$. Prove que $I$,$J$ e $M$ são colineares.

Solução:

(Adaptado de Davi Lopes - Professor do Colégio Farias Brito)