Questão 6 olimpíada matemática 2008 fase 2 nível 3
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.
 |
(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.
Resposta:
a) Vamos calcular a posição ocupada, após um embaralhamento, pela n-ésima carta da pilha. Há dois casos a considerar:
• n ≤ 52 (ou seja, a carta está na metade superior da pilha): neste caso, após um embaralhamento, ficarão acima dela as primeiras n cartas da metade inferior e as primeiras n - 1 cartas da parte superior. Logo, sua posição na pilha passará a ser n + (n - 1) + 1 = 2n.
• n > 52 (ou seja, a carta está na metade inferior da pilha. Após um embaralhamento, ficarão acima dela as cartas precedentes da metade inferior, que são em número de n - 52 - 1 = n - 53 e igual quantidade de cartas da metade superior. Logo, sua nova posição na pilha é (n - 53) + (n - 53)+ 1 = 2n - 105.
Em particular, podemos agora completar a tabela, observando que 55 = 2 x 80 -105 e 5 = 2 x 55 - 105.
 |
b) Como visto acima, a carta que ocupa a posição n passa a ocupar, após um embaralhamento, a posição 2n, se n ≤ 52 ou 2n - 105, se n > 52.
c) Inicialmente, observamos que após um embaralhamento
• as cartas da metade superior da pilha se movem para baixo, pois 2n > n para todo n positivo;
• as cartas da metade inferior da pilha se movem para cima, pois 2n - 105 < n para todo n < 105.
Logo, para que duas cartas troquem de posição entre si, uma delas deverá estar na metade superior da pilha e outra na metade inferior. Suponhamos que existam duas cartas com essa propriedade, e seja n a posição da carta de metade superior. Após um embaralhamento ela se move para a posição 2n , e então a carta na posição 2n deve passar para a posição n. Como a carta na posição 2n está na metade inferior da pilha. devemos ter 2(2n) - 105= n, donde n = 35. E, de fato, as cartas nas posições 35 e 70 trocam de posição entre si a cada embaralhamento, pois 2 x 35 = 70 e 2 x (2 x 35) - 105 = 35. Além disso, concluímos que não há outro par de posições com esta propriedade.
d) Para simplificar a exposição, vamos escrever x → y para indicar que a carta que está na posição x vai para a posição y após um embaralhamento.
Suponhamos que exista um trio fixo, e seja n a posição da primeira carta desse trio a contar do topo da pilha. O argumento do item (c) mostra que as cartas não podem estar todas na metade superior ou todas na metade inferior da pilha; logo a posição n está na metade superior da pilha.
Após um embaralhamento temos n → 2n; se 2n está na parte superior da pilha então o trio fixo deve ser n → 2n → 4 n → n; se 2n está na metade inferior da pilha então o trio fixo deve ser n → 2n → 4n - 105 → n. No primeiro caso, temos n = 2(4n) - 105 = 8n - 105,
donde n = 15; no segundo temos
n = 2(4n - 105) - 105 = 8n - 315
donde n = 45. Agora basta verificar que (15, 30, 60) e (45, 90, 75) são efetivamente trios fixos.
A título de curiosidade e/ou como exercício para o(a) leitor(a), listamos na tabela a seguir todas as k-uplas fixas, incluindo os casos k = 2 e k = 3 trabalhados nos itens (c) e (d) acima.
 |
Observamos ainda que após 12 embaralhamentos todas as cartas voltam à posição inicial.
