PRÁTICA COM QUESTÕES OFICIAIS
Questão 6 (Nível 3) da 2ª fase da OBMEP 2008
Considere uma pilha de cartas numeradas de 1 a 104. Um embaralhamento dessa pilha consiste em intercalar as 52 cartas de cima com as 52 de baixo, de modo que a carta que estava no topo fique em segundo lugar de cima para baixo. A figura mostra dois embaralhamentos seguidos a partir da situação inicial, na qual as cartas estão dispostas em ordem crescente de cima para baixo.
(a) Complete a tabela.
| número de embaralhamentos a partir da situação inicial |
1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| posição da carta de número 5 a partir do topo da pilha |
10ª |
(b) Partindo da situação inicial, qual será a posição da carta de número n após um embaralhamento?
(c) Partindo da situação inicial, ache duas cartas que trocam de lugar uma com a outra a cada embaralhamento.
(d) Um grupo de três cartas que trocam de lugar entre si a cada embaralhamento é chamado trio invariante. Partindo da situação inicial, encontre todos os trios invariantes.
Reportar erro na questão
Resolução comentada
Resolução comentada
a) Em um embaralhamento, as cartas de 1 a 52 (metade de cima) vão para as posições pares. A carta k vai para a posição 2k. As cartas de 53 a 104 vão para as posições ímpares. A carta 52+j vai para a posição 2j-1.
Em qualquer caso, a nova posição é o resto de 2p na divisão por 105, em que p é a posição anterior. Verificação com a figura: a carta 53 vai para a posição 1, e a carta 1 vai para a posição 2 e depois para a 4.
Para a carta 5, a posição inicial é 5:
- 1º embaralhamento: 2\cdot 5=10.
- 2º: 2\cdot 10=20.
- 3º: 2\cdot 20=40.
- 4º: 2\cdot 40=80.
- 5º: 2\cdot 80=160, e 160-105=55.
- 6º: 2\cdot 55=110, e 110-105=5.
A tabela fica: 10ª, 20ª, 40ª, 80ª, 55ª, 5ª. Resposta: 10ª, 20ª, 40ª, 80ª, 55ª e 5ª.
b) Pelo que vimos no item (a):
- se n\le 52, a carta n vai para a posição 2n;
- se n\ge 53, ela vai para a posição 2(n-52)-1=2n-105.
Resposta: posição 2n se n\le 52, e posição 2n-105 se n\ge 53 (isto é, o resto de 2n na divisão por 105).
c) Como a posição nova é o resto de 2p por 105, a carta n está, após k embaralhamentos, na posição dada pelo resto de 2^k n por 105.
Se as cartas a e b trocam de lugar entre si, então 2a\equiv b e 2b\equiv a \pmod{105}. Logo 4a\equiv a, ou seja, 3a\equiv 0 \pmod{105}. Isso significa que a é múltiplo de 35.
Como a está entre 1 e 104, a=35 ou a=70 (os múltiplos de 35 menores que 105).
Conferência: 2\cdot 35=70 e 2\cdot 70=140-105=35. As cartas 35 e 70 trocam de lugar a cada embaralhamento. Resposta: as cartas 35 e 70.
d) Num trio invariante a\to b\to c\to a, temos b\equiv 2a, c\equiv 4a e a\equiv 8a \pmod{105}. Então 7a\equiv 0 \pmod{105}, ou seja, a é múltiplo de 15. Assim, a\in\{15,30,45,60,75,90\}.
Nenhuma dessas cartas fica parada, pois 2a\not\equiv a para esses valores. Formamos os ciclos:
- 15\to 30\to 60\to 120-105=15;
- 45\to 90\to 180-105=75\to 150-105=45.
Resposta: há exatamente dois trios invariantes, \{15,30,60\} e \{45,75,90\}.
Assuntos: Sequências e padrões, 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 2008 · Nível 3. Prova oficial ↗