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)