PRÁTICA COM QUESTÕES OFICIAIS
Questão 4 (Nível 3) da 2ª fase da OBMEP 2010
No jogo Arrasta Um usa-se um tabuleiro quadriculado e peças redondas, uma preta e as outras brancas. Coloca-se uma peça em cada casa do tabuleiro, exceto em uma que é deixada vazia. Um movimento consiste em deslocar para a casa vazia a peça de uma casa adjacente. O jogo termina quando a peça preta chega ao canto superior direito do tabuleiro. Veja um exemplo de como terminar o Arrasta Um em quatro movimentos em um tabuleiro 2 \times 2.
Esta sequência de movimentos pode ser descrita por (\uparrow, \leftarrow, \downarrow, \rightarrow).
a) Descreva como terminar o Arrasta Um em seis movimentos no tabuleiro 3 \times 3 abaixo.
b) Descreva como terminar o Arrasta Um em dez movimentos no tabuleiro 3 \times 3 abaixo.
c) Mostre que em um tabuleiro n \times n, como na figura, é possível terminar o Arrasta Um em 6n - 8 movimentos.
Reportar erro na questão
Resolução comentada
Resolução comentada
Nas sequências, cada seta indica o sentido em que a peça que se move vai para a casa vazia, como no exemplo do enunciado. Vou usar (linha, coluna), com a linha 1 em cima e a coluna 1 à esquerda. Chamo de V a casa vazia e de P a peça preta.
a) Aqui V=(2,1) e P=(2,2). O objetivo é levar P a (1,3). Precisamos de pelo menos um movimento de P para cima e um para a direita. Para isso, a casa vazia tem de ficar primeiro acima de P e depois à direita dele.
- \downarrow: a peça de (1,1) desce, e V=(1,1).
- \leftarrow: a peça de (1,2) vai para a esquerda, e V=(1,2), acima de P.
- \uparrow: P sobe para (1,2), e V=(2,2).
- \leftarrow: a peça de (2,3) vai para a esquerda, e V=(2,3).
- \downarrow: a peça de (1,3) desce, e V=(1,3).
- \rightarrow: P vai para (1,3).
Sequência: (\downarrow,\leftarrow,\uparrow,\leftarrow,\downarrow,\rightarrow).
b) Aqui V=(2,1) e P=(3,1). A peça preta precisa subir 2 casas e ir 2 casas para a direita, então ela se move 4 vezes. Ela sobe e vai para a direita alternadamente, e a casa vazia a acompanha.
- \uparrow: P sobe para (2,1), e V=(3,1).
- \leftarrow: a peça de (3,2) vai para a esquerda, e V=(3,2).
- \downarrow: a peça de (2,2) desce, e V=(2,2).
- \rightarrow: P vai para (2,2), e V=(2,1).
- \downarrow: a peça de (1,1) desce, e V=(1,1).
- \leftarrow: a peça de (1,2) vai para a esquerda, e V=(1,2).
- \uparrow: P sobe para (1,2), e V=(2,2).
- \leftarrow: a peça de (2,3) vai para a esquerda, e V=(2,3).
- \downarrow: a peça de (1,3) desce, e V=(1,3).
- \rightarrow: P vai para (1,3).
Sequência: (\uparrow,\leftarrow,\downarrow,\rightarrow,\downarrow,\leftarrow,\uparrow,\leftarrow,\downarrow,\rightarrow), com 10 movimentos.
c) Os passos 1 a 6 do item (b) formam um ciclo de 6 movimentos que podemos repetir. Dizemos que a situação é "tipo X" quando a casa vazia está logo acima de P. Ela é exatamente a situação inicial, com P em (n,1).
Se P está em (r,c) na situação tipo X, com r\ge 3 e c\le n-1, fazemos o ciclo:
- \uparrow, \leftarrow, \downarrow, \rightarrow: P sobe e depois vai para a direita, e a casa vazia passa para a esquerda de P.
- \downarrow, \leftarrow: a casa vazia volta para cima de P.
Com isso, P passa para (r-1,c+1) na situação tipo X, gastando 6 movimentos. Todas as casas usadas existem, porque r\ge3 e c+1\le n.
Começando em (n,1), repetimos o ciclo n-2 vezes. Ao final, P está em (2,n-1), com a casa vazia em (1,n-1). Isso gasta 6(n-2) movimentos.
Finalizamos como no item (a), com 4 movimentos:
- \uparrow: P vai para (1,n-1).
- \leftarrow: a peça de (2,n) vai para a esquerda.
- \downarrow: a peça de (1,n) desce.
- \rightarrow: P chega a (1,n), o canto superior direito.
O total é
Para n=2 não há ciclos e restam só os 4 movimentos finais, o que confere com o exemplo. Para n=3 temos 10 movimentos, o que confere com o item (b).
Fica mostrado que é possível terminar em 6n-8 movimentos.
Assuntos: Lógica e raciocínio lógico, Divisibilidade, MMC e MDC.
Reportar erro na resolução
Esta questão também caiu em
Ver como caiu na prova
Fonte: OBMEP 2ª fase 2010 · Nível 3. Prova oficial ↗