Questão 6 (Nível 2) da 2ª fase da OBMEP 2007

Question

Fernando e Isaura inventaram um jogo diferente, cujas regras são as seguintes:

eles começam uma partida com 128 palitos cada um;
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.
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.

Ilustração de Fernando e Isaura sentados à mesa jogando par ou ímpar, com dois montes de palitos sobre a mesa.

Veja o que acontece em uma partida onde a seqüência das três primeiras jogadas é par, ímpar, par:

Fernando	Isaura		Fernando	Isaura		Fernando	Isaura		Fernando	Isaura
128	128	\xrightarrow[\text{1}^\text{a}\text{ jogada}]{\textbf{par}}	64	192	\xrightarrow[\text{2}^\text{a}\text{ jogada}]{\textbf{ímpar}}	160	96	\xrightarrow[\text{3}^\text{a}\text{ jogada}]{\textbf{par}}	80	176	\dots

(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 seqüê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.

(a)

Fernando	Isaura		Fernando	Isaura		Fernando	Isaura		Fernando	Isaura
128	128	\xrightarrow[\text{1}^\text{a}\text{ jogada}]{\textbf{ímpar}}			\xrightarrow[\text{2}^\text{a}\text{ jogada}]{\textbf{ímpar}}			\xrightarrow[\text{3}^\text{a}\text{ jogada}]{\textbf{par}}			\dots

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 6 (Nível 2) da 2ª fase da OBMEP 2007

Nível 2 · Matemática: Divisibilidade, MMC e MDC

Fernando e Isaura inventaram um jogo diferente, cujas regras são as seguintes:

eles começam uma partida com 128 palitos cada um;
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.
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.

Ilustração de Fernando e Isaura sentados à mesa jogando par ou ímpar, com dois montes de palitos sobre a mesa.

Veja o que acontece em uma partida onde a seqüência das três primeiras jogadas é par, ímpar, par:

Fernando	Isaura		Fernando	Isaura		Fernando	Isaura		Fernando	Isaura
128	128	\xrightarrow[\text{1}^\text{a}\text{ jogada}]{\textbf{par}}	64	192	\xrightarrow[\text{2}^\text{a}\text{ jogada}]{\textbf{ímpar}}	160	96	\xrightarrow[\text{3}^\text{a}\text{ jogada}]{\textbf{par}}	80	176	\dots

(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 seqüê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.

(a)

Fernando	Isaura		Fernando	Isaura		Fernando	Isaura		Fernando	Isaura
128	128	\xrightarrow[\text{1}^\text{a}\text{ jogada}]{\textbf{ímpar}}			\xrightarrow[\text{2}^\text{a}\text{ jogada}]{\textbf{ímpar}}			\xrightarrow[\text{3}^\text{a}\text{ jogada}]{\textbf{par}}			\dots

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

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.

[Figura: Esquema ilustrando as três primeiras jogadas, com o número de palitos de Fernando e Isaura a cada etapa: inicialmente 128 e 128; após a 1ª jogada (ímpar), 192 e 64; após a 2ª jogada (ímpar), 224 e 32; após a 3ª jogada (par), 112 e 144.]

b) 1^a 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 \times 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.

2^a 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 \frac{x}{2} palitos e Isaura com y + \frac{x}{2} palitos, ou seja, Isaura fica com mais palitos do que Fernando;
saiu ímpar: nesse caso Fernando fica com x + \frac{y}{2} palitos e Isaura com \frac{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:

Fernando	Isaura
101	155

Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 \times 101 = 202 palitos e Isaura tinha 256 - 202 = 54 palitos;

Fernando	Isaura
202	54

Fernando tem mais palitos, logo na jogada anterior saiu ímpar; então Isaura tinha 2 \times 54 = 108 palitos e Fernando tinha 256 - 108 = 148 palitos;

Fernando	Isaura
148	108

Fernando tem mais palitos, logo na jogada anterior saiu ímpar; então Isaura tinha 2 \times 108 = 216 palitos e Isaura tinha 256 - 216 = 40 palitos;

Fernando	Isaura
40	216

Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 \times 40 = 80 palitos e Fernando tinha 256 - 80 = 176 palitos;

Fernando	Isaura
80	176

Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 \times 80 = 160 palitos e Fernando tinha 256 - 160 = 96 palitos;

Fernando	Isaura
160	96

Fernando tem mais palitos, logo na jogada anterior saiu ímpar; então Isaura tinha 2 \times 96 = 192 palitos e Fernando tinha 256 - 192 = 64 palitos;

Fernando	Isaura
64	192

Isaura tem mais palitos, logo na jogada anterior saiu par; então Fernando tinha 2 \times 64 = 128 palitos e Isaura tinha 256 - 128 = 128 palitos. Essa é a situação inicial do jogo.

Logo a seqüê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:

Fernando	128 = 2^7 \times 1	64 = 2^6 \times 1	160 = 2^5 \times 5	80 = 2^4 \times 5	40 = 2^3 \times 5	148 = 2^2 \times 37	202 = 2^1 \times 101	101 = 2^0 \times 101
Isaura	128 = 2^7 \times 1	192 = 2^6 \times 3	96 = 2^5 \times 3	176 = 2^4 \times 11	216 = 2^3 \times 27	108 = 2^2 \times 27	54 = 2^1 \times 27	155 = 2^0 \times 155

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 2^n a e 2^n b, 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 2^{n-1}a' e 2^{n-1}b' 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, 2^n a e 2^n b palitos, onde a e b são inteiros ímpares, e que o jogo não acabou, ou seja, que n \ge 1. Se a próxima jogada sair par, então Fernando ficará com \frac{2^n a}{2} = 2^{n-1} a palitos e Isaura ficará com 2^{n-1} a + 2^n b = 2^{n-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 2^{n-1} a e 2^{n-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 = 2^7 \times 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.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Total de palitos: 128+128=256, que não muda durante o jogo.

1ª jogada, ímpar: Isaura dá metade dos seus 128 (64 palitos) a Fernando. Fica (192,\ 64).
2ª jogada, ímpar: Isaura dá metade de 64 (32 palitos). Fica (224,\ 32).
3ª jogada, par: Fernando dá metade de 224 (112 palitos). Fica (112,\ 144).

O esquema fica: (128,128)\to(192,64)\to(224,32)\to(112,144).

Respostas: (192, 64), (224, 32) e (112, 144).

b) No fim Fernando tem 101 palitos e Isaura tem 256-101=155.

Se a última jogada fosse ímpar, Isaura teria dado metade do que tinha. Ela ficaria com 155, ou seja, teria antes 2\cdot155=310 palitos. Isso é impossível, pois o total é 256.

Se foi par, Fernando tinha antes 2\cdot101=202 e Isaura tinha 256-202=54. Tudo é possível e, como os dois números eram pares, o jogo ainda não tinha acabado.

Resposta: saiu par.

c) Vamos desfazer as jogadas a partir de (101,155). Há duas formas de voltar um passo:

se a jogada foi par, Fernando tinha o dobro do que tem agora;
se foi ímpar, Isaura tinha o dobro do que tem agora.

Só vale a opção em que nenhum número passa de 256.

Antes da última jogada (par): (202,\ 54).
Voltando de (202,54): par daria F=404, impossível. Então foi ímpar, e antes era (148,\ 108).
Voltando de (148,108): par daria F=296, impossível. Então foi ímpar, e antes era (40,\ 216).
Voltando de (40,216): ímpar daria I=432, impossível. Então foi par, e antes era (80,\ 176).
Voltando de (80,176): ímpar daria I=352, impossível. Então foi par, e antes era (160,\ 96).
Voltando de (160,96): par daria F=320, impossível. Então foi ímpar, e antes era (64,\ 192).
Voltando de (64,192): ímpar daria I=384, impossível. Então foi par, e antes era (128,\ 128), o início.

Lendo do começo ao fim, a sequência é: par, ímpar, par, par, ímpar, ímpar, par. As três primeiras coincidem com o exemplo do enunciado.

Resposta: par, ímpar, par, par, ímpar, ímpar, par.

d) Vamos mostrar que, depois de k jogadas, os dois números são múltiplos ímpares de 2^{7-k}, isto é, da forma 2^{7-k}\cdot(\text{ímpar}).

Início (k=0): 128=2^7\cdot1 para os dois.
Passo: suponha que, antes de uma jogada, os números sejam x=2^m u e y=2^m v, com u e v ímpares. Depois da jogada, um jogador fica com x/2=2^{m-1}u e o outro com y+x/2=2^{m-1}(2v+u). Como u é ímpar, 2v+u também é ímpar. Logo os dois continuam sendo múltiplos ímpares, agora de 2^{m-1}. O argumento é o mesmo se quem dá os palitos for o outro jogador.

Consequências:

Depois de k\le6 jogadas, os dois números são múltiplos de 2^{7-k} com 7-k\ge1. Logo ambos são pares e o jogo continua.
Depois de 7 jogadas, os dois números são múltiplos ímpares de 2^0=1, isto é, ímpares. O jogo acaba.

Portanto toda partida termina em exatamente 7 jogadas.

Assunto: Divisibilidade, MMC e MDC.

Reportar erro na resolução

Esta questão também caiu em

OBMEP 2ª fase 2007 · Questão 4 (Nível 3)(d) Mostre que qualquer partida acaba com exatamente sete jogadas.

Ver como caiu na prova

Questão 6 no caderno Nível 2 da 2ª fase da OBMEP 2007

Fonte: OBMEP 2ª fase 2007 · Nível 2. Prova oficial ↗