Questão 4 olimpíada matemática 2007 fase 2 nível 3
Fernando e Isaura inventaram um jogo diferente, cujas regras são as seguintes:
1. eles começam uma partida com 128 palitos cada um;
2. em cada jogada, eles tiram par ou ímpar; se sai par, Fernando dá metade dos palitos que tem para Isaura e, se sai ímpar, Isaura dá a metade dos palitos que tem para Fernando.
3. eles repetem o procedimento da regra 2 até que um deles fique com um número ímpar de palitos, quando a partida acaba. Ganha quem ficar com maior número de palitos.
 |
Veja o que acontece em uma partida onde a sequência das três primeiras jogadas é par, ímpar, par:
 |
(a) Complete o esquema com o número de palitos de Fernando e Isaura, de acordo com as jogadas indicadas.
(b) Uma partida acabou quando Fernando ficou com 101 palitos. Na última jogada saiu par ou ímpar?
(c) Qual foi a sequência de pares e ímpares da partida que acabou quando Fernando ficou com 101 palitos?
(d) Mostre que qualquer partida acaba com exatamente sete jogadas.
Resposta:
(a) 
Como saiu ímpar na primeira jogada, Isaura deu metade dos seus palitos para o Fernando; desse modo, Isaura ficou com 64 palitos, e como o número total de palitos é 256 segue que Fernando ficou com 256 - 64 = 192 palitos. Do mesmo modo, após a segunda jogada Isaura ficou com 32 palitos e Fernando com 256 - 32 = 224 palitos. Na terceira jogada saiu par, e Fernando deu metade de seus palitos para a Isaura; logo, Fernando ficou com 112 palitos e Isaura com 256 -112 = 144 palitos.
| |
(b) 1a solução: Após qualquer jogada, o perdedor não pode ter mais que 127 palitos; de fato, se isso ocorresse, antes dessa jogada ele teria pelo menos 2 x 128 = 256 palitos, o que não pode acontecer. O ganhador terá então no mínimo 256 - 127 = 129 palitos; logo, o ganhador da jogada anterior é aquele que tem mais palitos.
2a solução: Suponhamos que em um dado momento Fernando tem x palitos e Isaura tem y palitos; notamos que como x + y = 256 , que é um número par, então x e y são ambos pares ou ambos ímpares. Se o jogo ainda não acabou, então x e y são pares, e depois da jogada seguinte podem acontecer as seguintes situações:
• saiu par: nesse caso Fernando fica com x/2 palitos e Isaura com y + x/2 palitos, ou seja, Isaura fica com mais palitos do que Fernando;
• saiu ímpar: nesse caso Fernando fica com x + y/2 palitos e Isaura com y/2 palitos, ou seja, Fernando fica com mais palitos do que Isaura.
Isso mostra que basta saber quem tem o maior número de palitos para determinar o resultado da última jogada: se Isaura tiver mais, o resultado foi par e se Fernando tiver mais, o resultado foi ímpar. No nosso caso, a partida acabou quando Fernando ficou com 101 palitos e Isaura com 256 -101 = 155 palitos. Logo o resultado da última jogada foi par.
(c) Aplicamos o raciocínio do item (b) para recuperar as jogadas uma a uma em ordem inversa, do seguinte modo:
Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 x101 = 202 palitos e Isaura tinha 256 - 202 = 54 palitos;
Fernando tem mais palitos, logo na jogada anterior saiu ímpar; então Isaura tinha 2 x 54 = 108 palitos e Fernando tinha 256 -108 = 148 palitos;
Fernando tem mais palitos, logo na jogada anterior saiu ímpar; então Isaura tinha 2 x108 = 216 palitos e Isaura tinha 256 - 216 = 40 palitos;
Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 x 40 = 80 palitos e Fernando tinha 256 - 80 = 176 palitos;
Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 x 80 = 160 palitos e Fernando tinha 256 -160 = 96 palitos;
Fernando tem mais palitos, logo na jogada anterior saiu ímpar; então Isaura tinha 2 x 96 = 192 palitos e Fernando tinha 256 -192 = 64 palitos;
Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 x 64 = 128 palitos e Isaura tinha 256 -128 = 128 palitos. Essa é a situação inicial do jogo.
Logo a sequência de jogadas dessa partida foi par, ímpar, par, par, ímpar, ímpar, par.
(d) Vamos aproveitar o trabalho do item anterior e fazer o seguinte diagrama do número de palitos de Fernando e Isaura, jogada a jogada:
 |
Esse diagrama e outros exemplos semelhantes sugerem que, em um momento qualquer de uma partida, o número de palitos de Fernando e o número de palitos de Isaura se escrevem, respectivamente, como 2na e 2nb, onde a e b são inteiros ímpares. Além disso, se o jogo não acabou, então depois da próxima jogada eles terão 2n-1a' e 2n-1b' palitos, respectivamente, onde a' e b' também são inteiros ímpares.
Vamos mostrar que essas afirmativas são verdadeiras. Suponhamos que em alguma etapa de uma partida os dois jogadores têm, respectivamente, 2na e 2nb palitos, onde a e b são inteiros ímpares, e que o jogo não acabou, ou seja, que n ≥ 1. Se a próxima jogada sair par, então Fernando ficará com 
palitos e Isaura ficará com 2n-1a + 2nb = 2n-1(a + 2b) palitos. Como a é ímpar então b' = a + 2b também é ímpar. Desse modo, após essa jogada, Fernando e Isaura ficarão com 2n-1a e 2n-1 b' palitos, onde a e b' são ímpares. Um argumento idêntico leva à mesma conclusão no caso em que a próxima jogada sair ímpar, e acabamos de provar nossa afirmativa.
O jogo começa com ambos os jogadores com 128 = 27 x 1 palitos, ou seja, com n = 7. Como uma partida acaba quando n = 0 e n decresce de uma unidade a cada jogada, segue imediatamente que qualquer partida acaba depois da sétima jogada.
