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

Question

No jogo do Troca-Cor usa-se um tabuleiro com duas linhas e com quantas colunas quisermos, cujas casas podem mudar da cor branca para cinza e vice-versa. As casas da 1^a linha são numeradas com os números ímpares e as da 2^a linha com os números pares. Em cada jogada aperta-se uma casa e, então, essa casa e as casas vizinhas mudam de cor. Uma partida completa começa com todas as casas brancas e termina quando todas ficam cinzas. Veja dois exemplos de partidas completas (os números acima das flechas indicam a casa apertada em cada jogada):

Nota: Casas vizinhas são casas que têm um lado comum.

Exemplos de partidas completas nos tabuleiros 2×3 (jogadas 1 e 6) e 2×2 (jogadas 1, 2, 4 e 3)

(a) Escreva as jogadas de uma partida completa nos tabuleiros ao lado.

Tabuleiro	Jogadas

(b) Explique como jogar uma partida completa no tabuleiro 2 \times 100.

(c) Explique como jogar uma partida completa com exatamente 51 jogadas no tabuleiro 2 \times 101.

(d) Explique por que não é possível jogar uma partida completa com menos que 51 jogadas no tabuleiro 2 \times 101.

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

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

Nível 1 · Matemática: Lógica e raciocínio lógico

No jogo do Troca-Cor usa-se um tabuleiro com duas linhas e com quantas colunas quisermos, cujas casas podem mudar da cor branca para cinza e vice-versa. As casas da 1^a linha são numeradas com os números ímpares e as da 2^a linha com os números pares. Em cada jogada aperta-se uma casa e, então, essa casa e as casas vizinhas mudam de cor. Uma partida completa começa com todas as casas brancas e termina quando todas ficam cinzas. Veja dois exemplos de partidas completas (os números acima das flechas indicam a casa apertada em cada jogada):

Nota: Casas vizinhas são casas que têm um lado comum.

Exemplos de partidas completas nos tabuleiros 2×3 (jogadas 1 e 6) e 2×2 (jogadas 1, 2, 4 e 3)

(a) Escreva as jogadas de uma partida completa nos tabuleiros ao lado.

Tabuleiro	Jogadas

(b) Explique como jogar uma partida completa no tabuleiro 2 \times 100.

(c) Explique como jogar uma partida completa com exatamente 51 jogadas no tabuleiro 2 \times 101.

(d) Explique por que não é possível jogar uma partida completa com menos que 51 jogadas no tabuleiro 2 \times 101.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a) Mostramos abaixo um jogo completo para cada tabuleiro, destacando as casas apertadas.

[Figura: Sequências de tabuleiros mostrando as etapas do jogo. Na primeira linha, um tabuleiro 2 \times 5 com a sequência de jogadas nas casas 1, 9 e 6 até preencher todas as casas de cinza. Na segunda linha, um tabuleiro 2 \times 4 com a sequência de jogadas nas casas 3, 5, 6 e 4 até preencher todas as casas de cinza.]

b) Dividimos o tabuleiro 2 \times 100 em 25 retângulos 2 \times 4 e, em cada um desses retângulos, tornarmos as casas cinzas procedendo como ilustrado no item (a); notamos que ao aplicar este procedimento em um retângulo os demais não são afetados. Desse modo podemos preencher todas as casas do jogo 2 \times 100.

c) Dividimos o tabuleiro como ilustrado na figura a seguir.

[Figura: Esquema de divisão do tabuleiro 2 \times 101 em blocos contornados com traços mais grossos, indicando as casas selecionadas: 1, 9, 17, ..., 193, 201 na primeira linha e 6, 14, ..., 198 na segunda linha.]

Na primeira linha selecionamos as casas 1, 9, 17,... , 193, 201 e na segunda as casas 6, 14, 22,..., 190, 198. Cada uma das casas selecionadas está dentro de uma região destacada com traço mais forte. Ao apertar uma destas casas, ela e todas as outras casas de sua região ficam cinzas, sem afetar as outras regiões. Apertando todas estas casas podemos então preencher todas as casas do jogo 2 \times 101.

Notamos que há uma casa selecionada de duas em duas colunas, começando da primeira à esquerda, e uma na última coluna. Como as colunas são em número de 101, vemos que foram selecionadas 51 casas, que é o número de jogadas que foram necessárias para terminar o jogo do modo descrito.

d) Não é possível acabar o jogo 2 \times 101 com menos de 51 jogadas, pois cada jogada muda a cor de no máximo quatro casas. Assim com 50 jogadas ou menos conseguiremos mudar a cor de no máximo 50 \times 4 = 200 casas, mas no jogo 2 \times 101 devemos mudar a cor de 202 casas. Logo é impossível fazer menos do que 51 jogadas e deixar cinzas todas as casas.

Observação: A solução dos itens (b) e (c) mostra como terminar o jogo no caso de tabuleiros 2 \times n, onde n deixa restos 0 ou 1 quando dividido por 4. É interessante completar a análise nos casos em que os restos são 2 ou 3; deixamos isto para o(a) leitor(a).

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Cada casa tem de ser apertada, ou ter vizinha apertada, um número ímpar de vezes. Apertar uma casa muda a própria casa, a outra casa da mesma coluna e as vizinhas da esquerda e da direita na mesma linha.

Tabuleiro 2×5. Aperte 1, 6 e 9:

a jogada 1 muda as casas 1, 2, 3;
a jogada 6 muda as casas 4, 5, 6, 8;
a jogada 9 muda as casas 7, 9, 10.

São 10 casas diferentes, cada uma mudada uma única vez. Todas ficam cinzas.

Tabuleiro 2×4. Aperte 3, 4, 5 e 6:

a jogada 3 muda as casas 1, 3, 4, 5;
a jogada 4 muda as casas 2, 3, 4, 6;
a jogada 5 muda as casas 3, 5, 6, 7;
a jogada 6 muda as casas 4, 5, 6, 8.

As casas 1, 2, 7 e 8 mudam 1 vez. As casas 3, 4, 5 e 6 mudam 3 vezes. Tudo é ímpar, então todas terminam cinzas.

2×5: 1, 6, 9; 2×4: 3, 4, 5, 6 (outras ordens também servem).

b) Divida o tabuleiro 2\times 100 em 25 blocos de 4 colunas, que são as colunas 1 a 4, 5 a 8, e assim por diante. Em cada bloco, aperte as 4 casas das duas colunas do meio, como no 2\times4 do item (a).

Uma jogada só afeta a própria coluna e as colunas vizinhas. As colunas das pontas de cada bloco não são apertadas. Assim, as jogadas de um bloco não afetam o bloco ao lado, e cada bloco fica todo cinza, como no 2\times 4.

As jogadas são 3, 4, 5, 6, 11, 12, 13, 14, ..., 195, 196, 197, 198. Em geral, são as casas 8j+3,\ 8j+4,\ 8j+5,\ 8j+6 para j=0,1,\dots,24.

Aperte as 4 casas das duas colunas centrais de cada bloco de 4 colunas (3, 4, 5, 6, 11, 12, 13, 14, ..., 195 a 198).

c) Vamos cobrir as 202 casas com 51 jogadas, de modo que cada casa mude exatamente uma vez. Aperte uma casa em cada coluna ímpar, alternando a linha:

coluna 1: casa de cima (1);
coluna 3: casa de baixo (6);
coluna 5: casa de cima (9);
coluna 7: casa de baixo (14);
e assim por diante, até a coluna 99: casa de baixo (198);
coluna 101: casa de cima (201).

A jogada na coluna 1 muda a coluna 1 e a casa de cima da coluna 2. A jogada na coluna 3 (baixo) muda a casa de baixo das colunas 2, 3 e 4 e a casa de cima da coluna 3. A jogada na coluna 5 (cima) muda a casa de cima das colunas 4, 5 e 6 e a casa de baixo da coluna 5. Cada jogada completa a coluna apertada e a metade que faltava de cada coluna vizinha, sem repetir nenhuma casa. A última jogada, na coluna 101, muda a casa de cima da coluna 100 e a coluna 101 inteira.

São as colunas 1,3,5,\dots,101, ou seja, 51 jogadas, e todas as casas mudam exatamente uma vez.

Jogadas: 1, 6, 9, 14, 17, ..., 198, 201 (51 jogadas).

d) O tabuleiro 2\times101 tem 202 casas, e todas precisam mudar de cor pelo menos uma vez.

Cada jogada muda no máximo 4 casas: a casa apertada, a outra da mesma coluna e as duas vizinhas laterais. Com 50 jogadas, no máximo 50\cdot 4=200 mudanças seriam feitas. Isso é menor que 202, então alguma casa ficaria sem mudar e continuaria branca.

Logo, são necessárias pelo menos \lceil 202/4\rceil = 51 jogadas.

Com menos de 51 jogadas, no máximo 4\cdot 50=200<202 casas mudariam, então é impossível.

Assunto: Lógica e raciocínio lógico.

Reportar erro na resolução

Esta questão também caiu em

Ver como caiu na prova

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

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