Nível 1 - Fase 3

Problema 1:

Quatro times de futebol irão disputar um campeonato no qual cada time joga uma única vez com todos os demais times. Cada vitória vale $3$ pontos e cada empate vale $1$ ponto e as derrotas não pontuam. Nesse campeonato,

a) Se o campeão conseguir $9$ pontos, o vice $6$ pontos e o terceiro $3$ pontos, quantos pontos obterá o quarto colocado?

b) Se o campeão conseguir $5$ pontos, dois times acabarem na mesma posição com $3$ pontos cada um e o último obtiver $2$ pontos, quantos empates terão acontecido?

Solução:

a) Vejamos que o campeão ganhou de todos, pois fez $9$ pontos. O vice fez $6$ pontos e como já perdeu para o campeão então certamente ganhou dos outros dois. O terceiro lugar fez $3$ pontos e já perdeu para o campeão e o vice, logo ganhou do último, portanto o último perdeu de todos e fez $0$ pontos.

b) O campeão fez $5$ pontos e portanto certamente ganhou uma partida e empatou duas, já que esta é a única maneira de obter $5$ pontos. O último lugar fez $2$ pontos e certamente empatou duas partidas e perdeu uma, pois esta também é a única maneira de fazer $2$ pontos. Os dois jogadores restantes que fizeram ambos $3$ pontos ou empataram as três partidas ou ganharam uma e perderam duas, já que estas são as duas possibilidades de fazer $3$ pontos.

Caso 1: Os dois jogadores ganharam uma e perderam duas partidas.

Portanto há $3$ vitórias (o campeão + os dois jogadores) e $5$ derrotas (o último + os dois jogadores) no campeonato, ou seja, absurdo!

Caso 2: Um jogador ganhou uma e perdeu duas e o outro empatou as três partidas.

Portanto o que empatou as três partidas, empatou com todos, mas existe um jogador sem nenhum empate: o que ganhou uma e perdeu duas, logo temos um absurdo!

Caso 3: Os dois jogadores empataram as três partidas.

Logo o campeão ganhou do último e todos os outros jogos foram empates, logo houve $6-2=4$ empates no campeonato.

Problema 2:

Janaína desenha uma sequência de figuras conforme a ilustração a seguir. Cada figura tem um quadrado a mais do que a figura anterior e esse quadrado que foi acrescentado tem lado igual à diagonal do maior quadrado da figura anterior. Além disso, todos os quadrados de cada figura têm um vértice comum. O quadrado da figura $1$ tem área de $2$ $cm^2$.

a) Qual é a área do quadrado maior da figura $2$?

b) Qual é a área total da figura $3$?

c) Qual é a área total da figura $6$?

Solução:

Vejamos que a cada figura seguinte adicionamos um quadrado, seja $l_i$ o lado do quadrado adicionado na figura $i$, como o lado $l_i$ sempre será a diagonal do quadrado adicionado na figura $i-1$ então $l_i=\sqrt{2}\cdot l_{i-1}$ por Pitágoras, e como $l_1=\sqrt{2}$, pois o quadrado da figura $1$ possui área $2$ então indutivamente vemos que $l_i=(\sqrt{2})^i$. Como da figura $i-1$ para a figura $i$ adicionamos $\dfrac{3}{4}$ da área do quadrado adicionado na figura $i$ em relação a área total da figura, então se denotarmos por $A_i$ a área total da figura $i$ então $A_i=A_{i-1}+\dfrac{3}{4}\cdot(l_i)^2=A_{i-1}+\dfrac{3}{4}\cdot(2^i)$. Telescopando nossa recorrência podemos obter a fórmula geral:

$A_i=A_{i-1}+\dfrac{3}{4}\cdot(2^i)$
$A_{i-1}=A_{i-2}+\dfrac{3}{4}\cdot(2^{i-1})$

...

$A_2=A_1+\dfrac{3}{4}\cdot(2^2)=2+\dfrac{3}{4}\cdot(2^2)=$

Somando tudo:

$A_i=\dfrac{3}{4}\cdot(2^i+2^{i-1}+...+2^2)+2$

$A_i=\dfrac{3}{4}\cdot(2^{i+1}-4)+2=3\cdot2^{i-1}-3+2=3\cdot2^{i-1}-1$

Logo $A_i=3\cdot2^{i-1}-1$. Aplicando a fórmula para os itens:

a) $(l_2)^2=2^2=4 cm^2$

b) $A_3=12-1=11 cm^2$

c) $A_6=96-1=95 cm^2$

Obs.: Essa estratégia só é efetiva até a figura $8$, pois a partir disto as figuras seguintes irão intersectar figuras anteriores.

Problema 3:

Os números inteiros de $1$ a $99$ são divididos em $n$ grupos, obedecendo as seguintes regras:

I- Cada número pertence a somente um grupo;

II- Cada grupo tem pelo menos dois números;

III- Se dois números pertencem a um mesmo grupo, então a sua soma não é um número divisível por $3$.

Sabendo disso:

a) Explique porque o número $n$ de grupos não pode ser $50$.

b) Qual é o menor número $n$ possível?

Solução:

(a) De fato, o número $n$ não pode ser $50$. Note que um número não pode aparecer duas vezes na distribuição em grupos, caso contrário, ele precisaria pertencer a pelo menos dois grupos, mas isso é um absurdo pela regra I. Assim todos inteiros de $1$ a $99$ aparecem uma única vez. Suponha que $n$ seja $50$, entretanto pela regra II, cada grupo tem pelo menos dois números, como temos $50$ grupos precisamos de pelo menos $100$ números, absurdo! Só há $99$ números de $1$ a $99$ e eles aparecem somente uma vez.

(b) Para encontrar o menor $n$ possível vamos utilizar a seguinte preposição: “Dois múltiplos de $3$ não podem pertencer a um mesmo grupo”. De fato, se isso não for verdade, sabemos que a soma deles gera um número divisível por $3$, absurdo pela regra III! Voltando ao problema, pela preposição temos que a quantidade de grupos precisa ser pelos menos a quantidade de múltiplos de $3$, que no caso é $33$, sendo assim, $n$ é pelo menos $33$ e esse é, na verdade, o menor valor possível. Para provar a existência segue um exemplo de distribuição para $n=33$:

$(3,1),(6,2,5,8),(9,4,7)$

$(12,10,13),(18,16,19),(24,22,25),...$

$(15,11,14),(21,17,20),(27,23,26),...$

Padrões para as linhas $2$ e $3$, respectivamente: 

$(3k,3k-2,3k+1)$, para todo $k$ par de $4$ a $32$.

$(3k,3k-4,3k-1)$, para todo $k$ ímpar de $5$ a $33$.

Onde $($ $)$ representa um grupo.

Problema 4:

Carlinhos fez uma lista de todos os números de quatro algarismos distintos nas seguintes condições: a soma dos algarismos é $12$, dois deles são pares e dois são ímpares. O número $2703$, por exemplo, está nessa lista. Lembre-se de que zero é par e nenhum número começa com zero à esquerda.

a) Qual é o número mais próximo de $2016$ que está na lista de Carlinhos?

 b) Determine a soma de todos os números da lista de Carlinhos que são menores que $2016$.

Solução:

(a) O número mais próximo de $2016$ que está na lista de Carlinhos é $2019$, já que os algarismos de $2018, 2017, 2016, 2015, 2014, 2013$ não somam $12$ (não podem estar na lista) e são os únicos números mais próximos de $2016$ que $2019$.

De fato, $2019$ tem dois dígitos pares e dois ímpares e a soma dos algarismos é $12$, todos distintos, logo está na lista!

(b) Note que encontrar a soma de todos os números da lista de Carlinhos que são menores que $2016$ é o mesmo que encontrar a soma de todos os números da lista que são menores que $2000$ (chamaremos essa parte da lista de “sublista”), já que nenhum dos números de $2000$ a $2016$ têm algarismos cuja soma é $12$. Assim, já que todos números de quatro algarismos menores que $2000$ começam com $1$, essa propriedade também é válida para todos números da sublista. Agora vamos encontrar os números da sublista! Veja que em todos eles, dois dígitos são pares e dois são ímpares, como $1$ é ímpar, vamos dividir o problema em casos que abrangem o outro dígito ímpar (não pode ser $1$, já que todos números da sublista têm algarismos distintos):

(1) Se ele for $3$: Então os dígitos pares somam $8$, possibilidades: $0$ e $8$, $2$ e $6$.

($4$ e $4$ não pode, já que teremos algarismos iguais).

(2) Se ele for $5$: Então os dígitos pares somam $6$, possibilidades: $0$ e $6$, $2$ e $4$.

(3) Se ele for $7$: Então os dígitos pares somam $4$, possibilidades: $0$ e $4$.

($2$ e $2$ não pode, já que teremos algarismos iguais).

(4) Se ele for $9$: Então os dígitos pares somam $2$, possibilidades: $0$ e $2$.

Assim, encontramos todos números da sublista:

$1308,1380,1803,1830,1038,1083$

$1326, 1362, 1263, 1236, 1632, 1623,$

$1506, 1560, 1650, 1605, 1056, 1065,$

$1524, 1542, 1425, 1452, 1254, 1245,$

$1704, 1740, 1407, 1470, 1047, 1074,$

$1902,1920,1209,1290,1029,1092$

Somando temos a resposta: $50652$.

Dica: para somarmos podemos utilizar a permutação de algarismos em cada subcaso aliada ao fato de que a soma dos algarismos diferentes do $1$ é $11$.

Problema 5:

Seja $N$ um inteiro, $N\ge2$. O jogo da OBM tem a participação de dois jogadores $A$ e $B$ e começa com o jogador $A$ recebendo o número $N$. Ele então deve escolher um novo número $n$, com $n$ e $N$ primos entre si e $n$ maior ou igual à metade de $N$ e menor do que $N$. Esse número $n$ é passado para o jogador $B$. O jogador $B$, então, recebe o número $n$ de seu oponente e deve escolher um novo número $m$, com $m$ e $n$ primos entre si e $m$ maior ou igual à metade de $n$ e menor do que $n$. Ele, então, passa para o seu oponente $A$ o número $m$ e o processo se repete até que um dos jogadores somente possa escolher o número $1$. Esse jogador é o vencedor! Por exemplo, para $N = 9$, o jogador $A$ pode escolher o número $5$ (observe que as suas opções são $5$, $7$ ou $8$); o $B$ jogador pode então escolher o número $3$; $A$ é obrigado a escolher o número $2$ (essa é a única opção respeitando as regras do jogo) e, então, $B$ escolhe $1$ e vence. Determine para cada valor de $N$ a seguir, qual jogador possui estratégia vencedora, ou seja, consegue vencer não importando quais sejam as jogadas de seu oponente.

a) $N = 7$.

b) $N = 2016$.

Observação: dizemos que dois números são primos entre si se não possuem um divisor comum maior ou igual a $1$. Veja que $9$ e $6$ não são primos entre si, pois $3$ é um divisor comum.

Solução:

a) A é vencedor. Se A escolhe $6$ então B só pode escolher entre $4$ e $5$. Se B escolhe $4$ então A escolhe $3$, B escolhe $2$ obrigatoriamente e A escolhe $1$ e vence. Se B escolhe $5$ então A escolhe $3$, B escolhe obrigatoriamente $2$ e A escolhe $1$ e vence. Portanto A sempre possui estratégia vencedora.

b) Iremos agora observar o jogo do fim para o começo, ou seja, utilizar de posições vencedoras e perdedoras. Diremos que uma posição é vencedora se aquele que receber tal número sempre vence e perdedora caso contrário. Observe que:

$1$ é perdedor;

$2$ é vencedor;

$3$ é perdedor;

$4$ é vencedor;

$5$ é vencedor;

$6$ é perdedor;

$7$ é vencedor;

$8$ é perdedor;

$9$ é vencedor;

$10$ é perdedor...

Onde nos baseamos na simples lógica de escolha. Indutivamente percebemos que números pares parecem ser sempre perdedores e números ímpares sempre vencedores e portanto provaremos isso por indução para $n>5$ onde $n$ é um número qualquer.

Indução forte em $n$: Tentaremos provar que para todo $n>5$ temos $2n+1$ sendo posição vencedora e $2n+2$ sendo posição perdedora.

Base: Já feita...

Hipótese: Para todo $2 < k\le n$ vale que $2k+1$ é uma posição vencedora e $2k+2$ é uma posição perdedora.

Passo indutivo: De fato $2n+1$ é vencedora, pois basta entregar $2n$ ao outro jogador, já que $mdc(2n,2n+1)=1$, e como $2n$ é posição perdedora por indução forte $(k=n-1)$ então $2n+1$ é posição vencedora.

De mesmo raciocínio vemos que $2n+2$ é posição perdedora, pois $mdc(2n+2,2k+2)=2$, logo nunca podemos entregar uma posição perdedora e somos obrigados a entregar um número ímpar, ou seja, uma posição vencedora, implicando que $2n+2$ é perdedor. Observe que só podemos usar disto pois $k>2$, já que $4$ é posição vencedora, mas como já analisamos até a posição $10$, nossa indução pode ser aplicada a partir de $n=5$ e portanto não temos nenhum problema.

Segue por indução que $2n+1$ é vencedor e $2n$ é perdedor, como $2016$ é par, então quem receber $2016$ é perdedor, logo o jogador $B$ possui a estratégia vencedora.