Olimpíadas ⇒ (Olimpíada Cearense - 1996) Chaves Tópico resolvido

[ALDRINMOD]

Um hotel possui 100 (cem) apartamentos, estando todos fechados e numerados de [tex3]1[/tex3] a [tex3]100[/tex3]. Um zelador recebe um pacote contendo uma chave de cada apartamento, totalizando [tex3]100[/tex3] chaves diferentes e não numeradas. Sabe-se que a fechadura de cada apartamento pode ser acionada (aberta ou fechada) por mais de uma chave, exceto a do apartamento [tex3]1[/tex3], e que para cada chave existe um único [tex3]n[/tex3] [tex3]\in[/tex3] [tex3]N[/tex3] [tex3](n \leq 100)[/tex3] tal que as fechaduras dos apartamentos numerados com múltiplos de [tex3]n[/tex3] podem ser acionadas. Após o zelador testar cada chave em todos os apartamentos, realizando uma única operação em cada fechadura (abrindo, fechando ou mantendo, conforme o caso), quais os apartamentos que restarão abertos?

[rean]

Olá ALDRIN. Vamos responder.

Para que um apartamento fique aberto é preciso que a fechadura seja acionada uma quantidade ímpar de vezes.
Observe que o apartamento tem o número N, sua fechadura será acionada pela chave n,
toda vez que que n|N, ou seja, o apartamento de número N será acionado d(N) vezes, onde d(N) é o número de divisores de N.

mas, se N = [tex3]p_1^a1 p_2^a2 ...p_k^ak[/tex3]
d(N) = ( [tex3]a_1 + 1)...( a_k + k[/tex3]).
esse número será ímpar se, e somente se, cada [tex3]a_i[/tex3] for par, ou seja, quando N for um quadrado perfeito.
Assim, restarão abertas todos os apartamentos cujo número é um quadrado perfeito
1 , 4 , 9 , 25 , 36 , 49 , 64 , 81 ,e 100

Rean

[ALDRINMOD]

Valeu, obrigado.