PRÁTICA COM QUESTÕES OFICIAIS
Questão 3 (Nível 3) da 2ª fase da OBMEP 2009
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):
Casas vizinhas são casas que têm um lado comum.
(a) Escreva as jogadas de uma partida completa nos tabuleiros ao lado.
(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 porque 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
Resolução comentada
a)
Uma casa termina cinza quando muda de cor um número ímpar de vezes. Vamos escolher as jogadas de modo que isso aconteça com todas as casas.
No tabuleiro 2\times5, aperte as casas 1, 6 e 9. A primeira jogada muda as casas 1,2,3; a segunda, as casas 4,5,6,8; e a terceira, as casas 7,9,10. Assim, cada casa muda de cor exatamente uma vez.
No tabuleiro 2\times4, aperte as casas 3, 4, 5 e 6, que ocupam as duas colunas centrais. Cada casa das colunas externas muda uma vez, enquanto cada casa das colunas centrais muda três vezes. Portanto, todas terminam cinzas.
No tabuleiro 2\times5: casas 1,6,9. No tabuleiro 2\times4: casas 3,4,5,6.
b)
Divida o tabuleiro em 25 blocos de quatro colunas consecutivas. Em cada bloco, use a estratégia do item anterior: aperte as quatro casas das duas colunas centrais.
Como nenhuma casa da primeira ou da última coluna de cada bloco é apertada, essas jogadas não afetam os blocos vizinhos. Dentro de cada bloco, as casas das colunas externas mudam de cor uma vez, e as das colunas centrais, três vezes. Logo, todas ficam cinzas.
No tabuleiro inteiro, isso corresponde a apertar as duas casas de cada uma das colunas 2,3,6,7,\ldots,98,99. São quatro jogadas por bloco, totalizando 25\cdot4=100 jogadas.
Aperte as duas casas das colunas 2,3,6,7,\ldots,98,99: isso completa a partida em 100 jogadas.
c)
Aperte uma casa em cada coluna ímpar, alternando as linhas: na coluna 1, aperte a casa de cima; na coluna 3, a de baixo; na coluna 5, a de cima; e assim por diante, até a coluna 101.
Em cada coluna ímpar, a jogada feita nela muda a cor de suas duas casas. Como suas colunas vizinhas são pares e não recebem jogadas, ambas mudam exatamente uma vez.
Cada coluna par fica entre duas colunas ímpares cujas casas apertadas estão em linhas diferentes. Assim, uma dessas jogadas muda sua casa de cima, e a outra muda sua casa de baixo. Novamente, cada casa muda exatamente uma vez.
Há 51 colunas ímpares entre 1 e 101, portanto são exatamente 51 jogadas.
Aperte, alternadamente, em cima e embaixo nas colunas 1,3,5,\ldots,101: são exatamente 51 jogadas.
d)
O tabuleiro tem 2\cdot101=202 casas. Para que todas passem de brancas a cinzas, cada uma precisa mudar de cor pelo menos uma vez.
Uma jogada muda a cor de, no máximo, quatro casas: a própria casa apertada, a vizinha da outra linha e as duas vizinhas laterais. Nas extremidades, são apenas três casas.
Portanto, com 50 jogadas, seria possível realizar no máximo 50\cdot4=200 mudanças de cor, quantidade insuficiente para atingir as 202 casas. Mais geralmente, se m é o número de jogadas, precisamos ter
Como m é inteiro, não é possível completar a partida com menos de 51 jogadas.
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
Fonte: OBMEP 2ª fase 2009 · Nível 3. Prova oficial ↗