Questão 3 olimpíada matemática 2009 fase 2 nível 3
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 1a linha são numeradas com os números ímpares e as da 2a 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):
 |
(a) Escreva as jogadas de uma partida completa nos tabuleiros abaixo.
 |
(b) Explique como jogar uma partida completa no tabuleiro 2 x 100.
(c) Explique como jogar uma partida completa com exatamente 51 jogadas no tabuleiro
2 x 101.
(d) Explique porque não é possível jogar uma partida completa com menos que 51 jogadas no tabuleiro 2 x 101.
Resposta:
Resposta: a) Mostramos abaixo um jogo completo para cada tabuleiro, destacando as casas apertadas.
 |
b) Dividimos o tabuleiro 2 x100 em 25 retângulos 2 x 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 x100.
c) Dividimos o tabuleiro como ilustrado na figura a seguir.
 |
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 x101. 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 x101 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 x 4 = 200 casas, mas no jogo 2 x 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 x 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).
