Nível 2 - Fase 3

Problema 1:

a) Considere todos os números formados usando os quatro algarismos 1, 2, 3 e 4. Formamos a seguinte expressão numérica S_4 = 4321-4312+4231-4213+...+1243-1234, na qual os números são listados da esquerda para a direita do maior para o menor, e os sinais + e - alternam-se até o final. Calcule o valor de S_4.

b) De modo análogo, tomamos todos os números de nove algarismos distintos e não nulos e formamos a expressão numérica S_9 = 987654321-987654312+987654231-...-123456789, na qual os números são listados da esquerda para a direita do maior para o menor, e os sinais + e - alternam-se até o final. Calcule o valor de S_9.

Solução:

Para calcularmos o valor da expressão em ambas situações vamos utilizar o fato que entre dois números consecutivos (com um sinal negativo entre eles) a única diferença é a permutação dos dois últimos algarismos, que possibilita a menor diferença possível (alterar as centenas, por exemplo, não seria a melhor opção se ainda podemos alterar apenas as dezenas e unidades, que possibilitam um menor acréscimo) requerida para a ordenação dos números.

Defina S_n da mesma forma que S_4 e S_9, sendo n natural e menor ou igual a 9.

Analisando esse fato veja que o valor total de S_n é justamente dado por essas diferenças, logo ao contá-las encontramos a resposta do problema. Vamos fixar os dígitos não permutados e analisar apenas os dois últimos dígitos: suponha que o menor seja a e o maior a+j, então ao trocarmos ambos de lugar, a única diferença entre os números será justamente a diferença resultante da permutação, pois o resto vai “se anular”, assim basta calcularmos:

[10 \cdot (a+j) + a]- [10 \cdot a + (a+j)] = 10 \cdot j - j = 9 \cdot j

Se a diferença entre os dígitos permutados for j, então acrescentamos 9j ao valor total, porém, veja que fixando os algarismos não permutados, a quantidade k de vezes que isso acontece é justamente n-j:

Permutação dos dígitos cuja diferença é j: 1 e j+1, 2 e j+2, ... , k e j+k, mas n é o maior dígito possível, logo j+k = n \Rightarrow k = n-j, justamente o que queremos provar.

Por fim, basta "acrescentarmos" a quantidade de vezes que cada pequena diferença, resultante da permutação dos dois últimos dígitos, ocorre:  (n-2)! , de fato, esse valor resulta da quantidade de maneiras existentes de permutar os (n-2) primeiros dígitos, que durante nossos cálculos estavam fixos.

Assim:

S_n = (n-2)!\cdot[(n-1) \times (9 \cdot 1) + (n-2) \times (9 \cdot 2) + (n-3) \times (9 \cdot 3) + ... + (n-(n-1)) \times (9 \cdot (n-1))].

O que nos possibilita encontrar a resposta de ambos itens:

(a) S_4 = 2! \cdot [(4-1) \times (9 \cdot 1) + (4-2) \times (9 \cdot 2) + (4-3) \times (9 \cdot 3)] = 2! \cdot 90 = 180.

(b) S_9 = 7! \cdot [(9-1) \times (9 \cdot 1) + (9-2) \times (9 \cdot 2) + ... + (1) \times (9 \cdot 8)] = 7! \cdot[72 + 126 + 162 + 180 + 180 + 162 + 126 + 72] = 7! \cdot 1080 = 5443200.

Problema 2:

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 se, e somente se, AB = AC.

Solução:

img2

Se AB = AC, então o triângulo ABC é isósceles de base BC. Por construção, BE e CD são as bissetrizes dos ângulos A\hat{B}C e A\hat{C}B, respectivamente. Chame A\hat{B}C = A\hat{C}B = 2 \theta. Como AD // BE e A\hat{B}E = \theta então B\hat{A}D = \theta (alternos internos), mas A\hat{C}B = 2 \theta e CD é bissetriz, assim B\hat{C}D também é igual a \theta e o quadrilátero ADBC será inscritível (B\hat{A}D = B\hat{C}D = 2 \theta). Da mesma forma, podemos afirmar que C\hat{A}E = C\hat{B}E = \theta, já que AE // CD e BE é bissetriz de A\hat{B}C, assim o quadrilátero AECB também será inscritível e como três pontos formam uma circunferência única (neste caso, A,B,C) temos que A,B,C,D,E são concíclicos.

Por fim, pela última informação D\hat{B}E = D\hat{C}E, mas E\hat{B}C = D\hat{C}B = \theta por definição, logo:

D\hat{B}E = D\hat{C}E \Rightarrow D\hat{B}E + E\hat{B}C = D\hat{C}E + D\hat{C}B \Rightarrow D\hat{B}C = E\hat{C}B \Rightarrow F\hat{B}C = F\hat{C}B.

Provamos que o triângulo FBC é isósceles de base BC, logo F está na mediatriz de BC, que também é a bissetriz de ABC, já que este triângulo também é isósceles. Logo, F,A e I são colineares.

img3

Agora resta 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 3:

Os números reais a, b, r e s são tais que as raízes da equação x^2-ax+b=0 são \dfrac{1}{r} e \dfrac{1}{s} e as raízes da equação x^2-rx+s=0 são a e b. Sabendo que a>0, encontre o seu valor.

Solução:

Pelas relações de Girrard:

a=\dfrac{1}{r}+\dfrac{1}{s} (1)

b=\dfrac{1}{r}\cdot\dfrac{1}{s} (2)

r=a+b (3)

s=a\cdot b (4)

Substituindo (1) e (2) em (3) temos:

r=\dfrac{1}{r}+\dfrac{1}{s}+\dfrac{1}{rs}

r=\dfrac{r+s+1}{rs}

r^2s=r+s+1

r^2s-r-(s+1)=0

Calculando por Bháskara as raízes vemos que:

r=\dfrac{1\pm\sqrt{1+4s(s+1)}}{2s}

r=\dfrac{1\pm\sqrt{4s^2+4s+1)}}{2s}

r=\dfrac{1\pm\sqrt{(2s+1)^2}}{2s}

r=\dfrac{1\pm (2s+1)}{2s} Logo r=\dfrac{1-2s-1}{2s}=-1 ou r=\dfrac{1+2s+1}{2s}=\dfrac{s+1}{s}

Caso 1: Se r=-1, pelo enunciado sabemos que a>0, logo de (1):

a=\dfrac{1}{r}+\dfrac{1}{s}>0

Como r=-1:

-1+\dfrac{1}{s}>0 \dfrac{1}{s}>1>0

Portanto \dfrac{1}{s}>0 \Rightarrow s>0, mas de (4) temos b=\dfrac{s}{a}, como a>0 e s>0, então b>0, mas de (3) temos b=\dfrac{1}{rs} \Rightarrow b=-\dfrac{1}{s}, logo b<0 pois s>0, mas 0>b>0 nos implica um absurdo, logo este caso não possui solução.

Caso 2: Se r=\dfrac{s+1}{s}, de (2) temos:

b=\dfrac{1}{r}\cdot\dfrac{1}{s}

b=\dfrac{s}{s+1}\cdot\dfrac{1}{s}

b=\dfrac{1}{s+1}

Aplicando em (4) temos:

s=a\cdot b

s=a\cdot \dfrac{1}{s+1}

s(s+1)=a (5)

Substituindo r em (1):

a=\dfrac{1}{r}+\dfrac{1}{s}

a=\dfrac{s}{s+1}+\dfrac{1}{s}

a=\dfrac{s^2+s+1}{s(s+1)}

a=\dfrac{s(s+1)+1}{s(s+1)}

Mas substituindo por (5) temos:

a=\dfrac{a+1}{a}

a^2=a+1

a^2-a-1=0

Esta equação muito conhecida nos dá como raízes:

a=\dfrac{1\pm\sqrt{5}}{2}

Porém do enunciado a>0, logo a=\phi=\dfrac{1+\sqrt{5}}{2}.

Problema 4:

Considere um triângulo escaleno ABC com AB < AC < BC. A mediatriz do lado AB corta o lado BC no ponto K e o prolongamento de AC no ponto U. A mediatriz do lado AC corta o lado BC no ponto O e o prolongamento do lado AB no ponto G. Prove que o quadrilátero GOKU é cíclico, ou seja, que seus quatro vértices estão em uma mesma circunferência.

Solução:

img1

Chame de M o ponto médio de AB e N o ponto médio de AC. Por definição, MN é base média do triângulo ABC, assim: MN // BC \Rightarrow MN // OK. Voltando ao problema, como MU é mediatriz de AB, então A\hat{M}U é ângulo reto. Analogamente, como NG é mediatriz de AC, então A\hat{N}G é ângulo reto. Por  A\hat{M}U = A\hat{N}G o quadrilátero GNMU é inscritível.

Para provarmos que o quadrilátero GOKU é inscritível, basta mostramos que seus ângulos opostos somam 180, mas isso, de fato, acontece:

U\hat{G}O + U\hat{K}O = 180 \Rightarrow U\hat{G}O + U\hat{M}N = 180

Veja que  U\hat{K}O = U\hat{M}N , já que MN // OK.

Como já tínhamos provado que o quadrilátero GNMU é inscritível, então  U\hat{G}O + U\hat{M}N = 180 e GOKU também é inscritível.

Problema 5:

Uma permutação (a_1, a_2, a_3,..., a_{n?1}, a_{n}) dos números do conjunto {1,2,3,...,n} é legal se não existem dois termos consecutivos cuja soma é um múltiplo de 3 e se os dois vizinhos de um termo qualquer não diferem por um múltiplo de 3. Por exemplo, (4,6,2,5,3,1) é uma permutação legal dos números do conjunto {1,2,3,4,5,6}. Entretanto, (1,2,5,3,4,6) não é uma permutação legal do mesmo conjunto, pois os números 1 e 2 são vizinhos e sua soma é um múltiplo de 3. Além disso, outra razão para ela não ser legal, é que os vizinhos do número 4, que são o 3 e o 6, diferem por um múltiplo de 3.

a) Determine o número de permutações legais do conjunto {1,2,3,4,5,6}.

b) Determine o número de permutações legais do conjunto {1,2,3,...,2016}

 Observação: Uma permutação de um conjunto é uma sequência ordenada contendo cada um de seus elementos uma única vez.

Solução:

Para resolvermos o problema vamos utilizar somente os resíduos dos números do conjunto na divisão por 3. Mostraremos que é possível determinar com base nos resíduos a quantidade de permutações legais:

Se dispomos do dígito 0, então o próximo dígito pode ser 1 ou 2, mas essa será a única escolha possível que poderemos fazer, de fato, determinado o segundo dígito a sequência está definida:

Se 1: o próximo dígito não pode ser 2, já que a soma resultará num múltiplo de 3, também não pode ser 0, já que a diferença de dois vizinhos de um termo também não pode ser divisível por 3, logo só pode ser novamente 1 e o processo se repete. Da mesma forma se escolhermos o 2.  Isso acontece, pois suponha que tenhamos determinado os dois últimos dígitos da sequência e esses sejam a e b, então o próximo dígito não pode ser 3-b (somado com b resulta num múltiplo de 3) nem a (difere zero de a, ou seja, temos uma diferença divisível por 3), logo há dois casos a considerar:

 - a diferente de 3-b, então não temos escolha e o número está determinado, como queremos demonstrar!

 - a igual a 3-b, o que é um absurdo! Note que a e b já são termos definidos da sequência então sua soma não pode ser um múltiplo de 3, exatamente o que acontece quando a=3-b.

Concluímos que escolhidos os dois primeiros dígitos só existe uma forma fixa de termos uma permutação legal, como só estamos analisando os resíduos na divisão por 3 até agora, então existem seis formas de escolhermos os dois primeiros dígitos (não podemos escolhê-los somando um múltiplo de 3, o que elimina as escolhas 0 - 0, 1 - 2, 2 - 1) e consequentemente seis permutações legais possíveis (olhando os restos módulo 3).

Para determinar as permutações legais com base nos números do conjunto basta analisarmos a permutação dos números com mesmo resíduo na divisão por 3. A nossa análise anterior garantiu por meio da marcação dos resíduos como determinar se uma permutação é legal, a partir disso podemos determinar a quantidade total de permutações contando as possibilidades de trocarmos todos números com resíduo 1 de “lugar”, assim como os de resíduo 2 e 3, supondo que a quantidade de números do conjunto seja 3k a quantidade de permutações dentro das posições de um mesmo resíduo será k! , logo determinada uma permutação legal com base nos resíduos há (k!)^3 formas de preenchê-la com os números do conjunto, como há seis permutações legais possíveis dos resíduos, então um conjunto com 3k elementos tem um total de 6 \times (k!)^3 permutações legais.

A partir disso resolvemos ambos itens:

(a) {1,2,3,4,5,6} tem 6 elementos, logo 6 \times (2!)^3 = 48 permutações legais.

(b) {1,2,3,...,2016} tem 2016 elementos, logo 6 \times (672)^3 permutações legais.

Problema 6

Seja a_0=a>1 um inteiro e, para n\ge0, defina a_{n+1}=2^{a_n}-1. Mostre que o conjunto dos divisores primos dos termos da sequência a_{n} é infinito.

Solução:

Vamos supor que o conjunto dos divisores primos é finito, e seja este S={p_1,p_2,...,p_{k}}, colocaremos cada subconjunto de S como sendo a definição de uma “casa”, basicamente colocaremos nesta “casa” todos os termos da sequência formados pelos primos deste subconjunto, por exemplo, escolha o subconjunto S {p_1,p_2,p_5}, e então faremos uma “casa” com todos os termos da sequência que possuem somente p_1,p_2,p_5 em sua fatoração. Como os termos da sequência são infinitos, então pelo Princípio da Casa dos Pombos, alguma de nossas “casas” terá infinitos termos, escolha esta “casa”, seja esta formada pelos primos p_1,p_2,...p_i, então existem infinitos termos da nossa sequência formados por somente todos estes primos, tentaremos provar que existem dois termos de nossa sequência tais que um divide o outro. Agora enunciaremos o seguinte algoritimo:

Algoritimo: Seja a_r=p_1^{\theta_1}p_2^{\theta_2}...p_i^{\theta_i} um termo da sequência, fixe \theta_1, \theta_2, ... , \theta_i, agora pegue um termo da sequência qualquer formado por estes mesmos primos, se este numero é da forma a_s=p_1^{\beta_1}p_2^{\beta_2}...p_i^{\beta_i} e \beta_t<\theta_t para todo t=1,2,...,i então a_s divide a_r e acabou, e se \beta_t>\theta_t para todo t=1,2,...,i então a_r divide a_s e acabou, logo resta analisar o caso em que para alguns valores de t temos \beta_t<\theta_t e para outros \beta_t>\theta_t, sejam p_{b_1},p_{b_2},...,p_{b_j} os primos tais que \beta_t<\theta_t para t=b_1,b_2,...,b_j e sejam p_{b_{j+1}},p_{b_{j+2}},...,p_{b_i} os primos tais que \beta_t>\theta_t para t=b_{j+1},b_{j+2},...,b_i, então se \theta_{b_h} é o expoente de p_{b_h} para todo h=1,2,...,i e p_{b_h} seja p_t para algum t=1,2,...,i. Então para todo termo da sequência que é formado pelos primos p_1,p_2,...,p_i podemos separar duas partes deste termo, a parte "menor" formada por p_{b_1},p_{b_2},...,p_{b_j} e seus expoentes e a parte "maior" formada por p_{b_{j+1}},p_{b_{j+2}},...,p_{b_i} e seus expoentes, onde estas duas partes juntas formam o termo da sequência, vejamos que o número de partes "menores" é finito já que como \beta_t<\theta_t, existe um número finito de configurações de \beta_t e como a quantidade de termos da sequência é infinito então em alguma desta partes "menores", suponha s.p.g. p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_w}^{\theta_{c_w}} temos infinitos termos da sequência, então existem infinitas partes maiores tal qual os termos formados por estas possuem como parte menor p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_w}^{\theta_{c_w}}.

Sabemos agora que esta parte "maior" possui no máximo i-1 fatores primos, já que, caso todos fossem maiores, então entraríamos no caso de que \beta_t>\theta_t para todo t=1,2,...,i, absurdo. Como existem infinitas partes "maiores", podemos fixar a parte "menor" p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_w}^{\theta_{c_w}} e aplicar o algoritimo novamente na parte "maior" e assim estaremos fixando cada vez mais partes "menores", até que em algum momento teremos fixados exatamente i-1 fatores primos: p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_{i-1}}^{\theta_{c_{i-1}}} e restará apenas um fator primo como sendo uma parte "maior", mas então pelo algoritimo partes "maiores" sempre possuem infinitos termos, logo existem infinitos termos que possuem p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_{i-1}}^{\theta_{c_{i-1}}} como parte menor fixada e que possuem o último primo, ou seja, existem infinitos termos da forma: p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_{i-1}}^{\theta_{c_{i-1}}}p_v^{\theta_v} onde p_v é o último primo e \theta_v é variável, logo pegue o menor número dentre todos os valores possíveis para \theta_v e portanto este número divide infinitos outros termos da sequência e então teremos um termo que é divisível por este menor termo, e assim podemos iniciar nossa questão (leia atentamente o algoritimo caso não tenha entendido, sei que existem muitas letras mas isto é só questão de formalidade, recomendamos ao leitor que pegue exemplos pequenos para que possa acompanhar a ideia) . Sabendo que existem i,j tais que a_i divide a_j, então temos que:

a_i \mid a_j

2^{a_{i-1}}-1 \mid 2^{a_{j-1}}-1

Lema: mdc(2^n-1,2^m-1)=2^{mdc(m,n)}-1

Prova: se d=mdc(2^n-1,2^m-1) então 2^n-1 \equiv 0 (mod \ d) \Rightarrow 2^n \equiv 1 (mod \ d) e 2^m-1 \equiv 0 (mod \ d) \Rightarrow 2^m \equiv 1 (mod \ d), portanto se t é a ordem de 2 módulo d, vale que t \mid m e t \mid n, logo t \mid mdc(m,n), e portanto 2^{mdc(m,n)} \equiv 1 (mod \ d) \Rightarrow 2^{mdc(m,n)}-1 \equiv 0 (mod \ d), então d \mid 2^{mdc(m,n)}-1, mas vejamos que se d=2^{mdc(m,n)}-1 então d \mid 2^m-1 e d \mid 2^n-1, logo d=2^{mdc(m,n)}-1.

Pelo nosso lema, mdc(2^{a_{i-1}}-1,2^{a_{j-1}}-1)=2^{mdc(a_{i-1},a_{j-1})}-1, mas como 2^{a_{i-1}}-1 \mid 2^{a_{j-1}}-1, então mdc(a_{i-1},a_{j-1})=a_{i-1} e portanto temos que a_{i-1} \mid a_{j-1}. Indutivamente vemos que a_{i-2} \mid a_{j-2},...,a_{0} \mid a_{j-i}. Chame j-i=k, então a \mid a_k, logo a \mid 2^{a_{k-1}}-1. Agora seja p o menor primo divisor de a (*), então vejamos que:

2^{a_{k-1}}-1 \equiv 0 (mod \ p)

2^{a_{k-1}} \equiv 1 (mod \ p)

Mas pelo pequeno Teorema de Fermat:

2^{p-1} \equiv 1 (mod \ p)

Logo, vale que (pelo lema):

2^{mdc(a_{k-1},p-1)} \equiv 1 (mod \ p)

Agora tome q_{k-1} como um divisor primo do mdc(a_{k-1},p-1) (note que isto só pode ocorrer se mdc(a_{k-1},p-1) é diferente de 1) (**), vejamos que q_{k-1}\le p-1<p e q_{k-1} \mid a_{k-1} e portanto q_{k-1} \mid 2^{a_{k-2}}-1, e de modo análogo teremos que:

2^{mdc(a_{k-2},q_{k-1}-1)} \equiv 1 (mod \ q_{k-1})

Agora tome q_{k-2} como um divisor primo do mdc(a_{k-2},q_{k-1}-1) (note que isto só pode ocorrer se mdc(a_{k-2},q_{k-1}-1) é diferente de 1) (**), vejamos que q_{k-2}<q_{k-1}<p e q_{k-2} \mid a_{k-2} e portanto q_{k-2} \mid 2^{a_{k-3}}-1. Indutivamente podemos definir a sequência de primos q_{k-3}, q_{k-4}, ... , q_1, q_0 da mesma forma, mas perceba que q_0 \mid a, mas p>q_{k-1}>q_{k-2}>...>q_1>q_0, logo achamos um primo menor que p que divide a, absurdo por (*), já que p é o menor primo que divide a. Porém vejamos que em algum momento poderíamos ter tido mdc(a_{k-t-1},q_{k-t}-1=1 por (**), o que nos impediria de montar a sequência de primos que nos levaria a um absurdo por (*), mas se t é o menor número (***) tal que mdc(a_{k-t-1},q_{k-t}-1)=1 então:

2^{mdc(a_{k-t-1},q_{k-t}-1)} \equiv 1 (mod \ q_{k-t}) (já demonstramos isto pelo lema) 2^1 \equiv 1 (mod \ q_{k-t}) 2 \equiv 1 (mod \ q_{k-t}) 1 \equiv 0 (mod \ q_{k-t})

Logo q_{k-t}=1, mas q_{k-t} divide o mdc(a_{k-t-2},q_{k-t-1}-1), logo se não existe q_{k-t} primo que divide o mdc(a_{k-t-2},q_{k-t-1}-1), então mdc(a_{k-t-2},q_{k-t-1}-1)=1, mas então por (***) temos um absurdo pois achamos um número menor que t tal que mdc(a_{k-r-1},q_{k-r}-1)=1. Portanto o que supomos no início na verdade era falso e o conjuntos de primos que dividem os termos da sequência a_n é infinito, como queríamos demonstrar.

Obs.: Gostaríamos de salientar que o problema ficaria mais fácil se pudéssemos usar teoremas um pouco mais avançados, como o Teorema de Zsigmondy, mas isto foge do nosso contexto olímpico já que este teorema é tão forte que o problema ficaria quase uma aplicação direta do mesmo, apenas restando prova-lo, porém sua prova é bem complicada e por isso achamos melhor esta resolução utilizando de argumentos relativamente mais simples.