Siga-nos

Perfil

Expresso

Solução para o Problema da Semana “Cartas em cima da mesa”

  • 333

Na passada sexta-feira deixámos AQUI um problema. Hoje apresentamos-lhe a solução.

Inicialmente, temos um certo número de cartas em cima da mesa. Algumas das cartas têm a face virada para baixo, enquanto outras têm a face virada para cima. Podemos escolher uma, duas ou três cartas consecutivas, desde que a carta mais à esquerda tenha a face voltada para baixo, e virar todas as cartas desse grupo. O processo pode ser repetido, desde que exista pelo menos uma carta com a face voltada para baixo em cima da mesa. Mostre que, independentemente das escolhas efectuadas, a dada altura todas as cartas têm a face voltada para cima.

Vamos associar um número a cada disposição das cartas, da seguinte forma: a cada carta com a face voltada para baixo corresponde o dígito 1, enquanto uma carta com a face voltada para cima representa um 2.

Vamos supor, para simplificar a discussão, que temos apenas 5 cartas (em fila) em cima da mesa. Assim, se tivermos as 5 cartas com a face voltada para baixo, o número associado será 11111. O número 22222 corresponde à situação em que temos as 5 cartas com a face voltada para cima. A cada disposição das cartas corresponde um número distinto com 5 dígitos escolhidos entre os algarismos 1 e 2. Existem 2^5 = 32 disposições possíveis. Vamos agora inverter as cartas e ver o que acontece ao número associado. Por exemplo, a partir da disposição 21122, podemos inverter as 3 últimas cartas. Obtendo a nova configuração 21211. O número obtido na nova disposição é sempre superior ao anterior. Isto porque o algarismo mais significativo passa sempre de 1 para 2.

E agora falta a parte divertida, se o número associado aumenta sempre, este processo tem necessariamente de parar!

Naturalmente, o processo termina quando todas as cartas em cima da mesa tiverem a face voltada para cima. O nosso leitor omnipresente (jpa) resolveu o problema de modo análogo.

Na próxima sexta-feira regressamos com novo Problema da Semana. Esperamos por si