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.