PRÁTICA COM QUESTÕES OFICIAIS
Questão 6 (Nível 2) 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):
(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. Se mudar um número par de vezes, volta a ficar branca.
No tabuleiro 2\times5, aperte as casas 1, 6 e 9. A jogada na casa 1 muda as casas 1,2,3; a jogada na casa 6 muda 4,5,6,8; e a jogada na casa 9 muda 7,9,10. Assim, cada casa muda de cor exatamente uma vez.
No tabuleiro 2\times4, aperte 3, 4, 5 e 6, isto é, todas as casas das duas colunas centrais. Cada casa das colunas externas muda uma vez, e cada casa das colunas centrais muda três vezes. Portanto, todas terminam cinzas.
Uma resposta possível é: 2\times5: jogadas 1,6,9; 2\times4: jogadas 3,4,5,6.
b)
Divida as 100 colunas em 25 blocos consecutivos de quatro colunas. Em cada bloco, use a solução do tabuleiro 2\times4 do item anterior: aperte as quatro casas das duas colunas centrais.
Essas jogadas não alteram casas de outros blocos, pois nenhuma casa apertada está na primeira ou na última coluna de seu bloco. Assim, podemos resolver cada bloco independentemente: suas casas externas mudam uma vez, e suas casas centrais, três vezes.
As colunas centrais dos blocos são 2,3; depois 6,7; depois 10,11; e assim por diante, até 98,99. Como são quatro jogadas por bloco, fazemos 25\cdot4=100 jogadas.
Aperte as duas casas de cada coluna 4k+2 e 4k+3, para k=0,1,\ldots,24, totalizando 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, as duas casas mudam de cor pela jogada realizada nessa própria coluna. Elas não recebem outras mudanças, pois nenhuma casa das colunas pares é apertada.
Cada coluna par fica entre duas colunas ímpares cujas casas apertadas estão em linhas diferentes. Por isso, sua casa de cima muda uma vez, e sua casa de baixo também muda uma vez.
Logo, todas as casas mudam exatamente uma vez. Há (101+1)/2=51 colunas ímpares.
Aperte as casas 1,6,9,14,17,\ldots,193,198,201, nessa ordem: são exatamente 51 jogadas.
d)
O tabuleiro possui 2\cdot101=202 casas. Para terminar cinza, cada uma delas precisa mudar de cor pelo menos uma vez.
Uma jogada muda, no máximo, quatro casas: a própria casa apertada, sua vizinha vertical e suas duas possíveis vizinhas horizontais. Portanto, em 50 jogadas, no máximo
casas distintas poderiam ser atingidas, mesmo que não houvesse nenhuma repetição. Como 200<202, pelo menos duas casas continuariam brancas. Com menos jogadas, também não seria possível atingir todas as casas.
São necessárias pelo menos 51 jogadas; portanto, a partida do item (c) tem o menor número possível de 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 2. Prova oficial ↗