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.