Solução do desafio 24 – As 1000 gavetas

Desafio 24 – As 1000 gavetas

A maneira mais fácil de ver é considerar o que acontece com uma única gaveta. Por exemplo, pense na gaveta 24. Quando muda ela de estado? Obviamente, a 1.ª pessoa abre a gaveta, a 2.ª pessoa fecha-a, a pessoa n.º 3 abre-a, é fechada pela pessoa número 4, a 5.ª pessoa não faz nada, etc. Observe que, se o número da gaveta, neste caso a 24, é divisível pelo número de ordem da pessoa, então a mudança de estado ocorre:

O número 24 tem 8 fatores, isto é, oito números que o dividem. Portanto, a chave é que qualquer número de gaveta com um número par de fatores vai acabar fechada e qualquer com um número ímpar vai acabar aberta. Então, quais são os números têm um número ímpar de fatores?

À primeira vista, parece que todos os números devem ter um número par de divisores, uma vez que ocorrem sempre aos pares:

24 = 1 x 24
24 = 2 x 12
24 = 3 x 8
24 = 4 x 6.

Considere, agora, um número como o 36, no entanto:

36 = 1 x 36
36 = 2 x 18
36 = 3 x 12
36 = 4 x 9
36 = 6 x 6 . <- Aha !!!

Os quadrados perfeitos são os únicos números que podem ter um número ímpar de divisores. Então, as gavetas cujos números são quadrados perfeitos (ou seja, 1, 4, 9, 16, 25, …) ficarão abertas, enquanto os restantes estarão fechadas!

Considerando que a raiz quadrada de 1000 é aproximadamente 31.6222, então concluímos que há 31 quadrados perfeitos até 1000, ou seja, 31 gavetas que terminarão abertas: as gavetas n.os 1, 4, 9, 16, 25, 36, ….. 900 e 961.