O Problema das Portas

Essa é uma questão de lógica nada óbvia; é preciso trabalhar e pensar um pocado para solucioná-la; ao mesmo tempo, bem desafiadora. E o particular dela, é que até mesmo para o ginásio ela é cabível.

The Question

Num corredor há 100 portas fechadas e 100 mulheres. A primeira mulher passa pelo corredor abrindo todas as portas. A segunda mulher passa pelo corredor abrindo apenas as portas pares. A terceira mulher, abre apenas as portas que é multipla de três. Então vem a quarta mulher e repete o mesmo processo, até a última porta. Quais as portas que ficaram abertas ao passar a última mulher? E caso o número fosse 1000 portas e mulheres.

Comentários

O primeiro problema está na lógica do texto. Demorou um pouco e tive que consultar o professor Oscar João Abnaour (disciplia "Seminário de Resolução de Problemas", IME-USP), para realmente estar certo da lógica do problema.

A mulher 1, inverte (fechado / aberto) multiplo de 1.

A mulher 2, inverte (fechado / aberto) multiplo de 2.

A mulher 3, inverte (fechado / aberto) multiplo de 3.

A mulher 4, inverte (fechado / aberto) multiplo de 4.

A mulher 5, inverte (fechado / aberto) multiplo de 5.

...

A mulher 100, inverte (fechado / aberto) multiplo de 100.

Geral:

A mulher k, inverte (fechado / aberto) multiplo de k.

Até onde cheguei

Depois de muito quebrar os miolos, consegui chegar numa regra geral para descobrir se a porta no final será aberta ou fechada:

"A porta k, se k = "n. primo", será fechada no final. As portas que k não é primo, se ela possuir um número de divisores (de modo a ser divisível) pares, no final ela vai ser aberta; se impar, será fechada. Exceto a porta 1, a qual será aberta."

Tal resolução verbal está 100% correta. O problema é que ela é insuciente para determinar no final a quantidade de portas abertas; pois necessitaria ver cada caso. E se fossem mil portas, seria chato para dedel. Caso fosse resolver isso usando um programinha bem simples em C, seria fácil. Mas certamente, o que falta é obter-se uma expressão mais profunda de como trabalhar com tal lógica; a apenas informar um número de portas e mulheres, e então o resultado seria o número de portas abertas.

Comecei a trabalhar depois com a idéia de MMC e MDC; o problema é que tais tralham, em essência, com números primos. Mas até hoje ninguém conseguiu descobrir uma fórmula, uma definção algébrica dos números primos; se você conseguir, vai ganhar um prêmio MIT de 2 mulhões de dólares. Portanto, certamente há um outro caminho; não sei qual. Mas uma amiga percebeu alguma coisa com cara de combinação, e está escavando por essas terras.

Ainda não cheguei numa solução. Mas o desafio, lançado está, para o leitor.