Re: [obm-l] corredor

[Vinicius Jos� Fortuna <ra992559@xxxxxxxxxxxxx>]

On Fri, 25 Jan 2002, pichurin wrote:

> Em um corredoe existem 900 arm�rios numerados de 1 a
> 900.Novecentas pessoas numeradas de 1 a 900 atravessam
> este corredor ,uma a uma, em ordem crescente de
> numera��o.Cada pessoa deve reverter os arm�rios que
> sA� m�ltiplos de sua numera��o.Por exemplo, a pessoa
> de n�mero 4 deve mexer nor arm�rios 4,8,12,16,20,etc,
> abrindo aqyeles que est�o fechados e fechando aqueles
> que est�o abertos.Ao final, quais arm�rios estar�o
> abertos e quais estar�o fechados?

Um arm�rios s� � revertido por uma pessoa se ele for m�ltiplo dela.
Um arm�rio ser� m�ltiplo de todos os seus divisores.
Ent�o o n�mero de mudan�as de estado de cada arm�rio ser� o n�mero de
divisores dele.
Se esse n�mero for par, ele estar� fechado, se for �mpar ele estar�
aberto.

Considere o arm�rio x fatorado como x=  p1^a1 * p2^a2 * ... * pn^an, onde
pi � primo.
O n�mero de divisores de x ser� d = (a1+1)*(a2+1)+...+(an+1)
Se d == 0 (mod 2), o arm�rio ficar� fechado.
se d == 1 (mod 2), o arm�rio ficar� aberto.

d � par se e somente se existe (ai+1) par.

Ou seja, um arm�rio fica fechado se e somente se possui um fator primo com
pot�ncia �mpar na sua fatora��o.

Ser� que essa resposta j� � o suficiente?

At� mais

Vinicius

=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <nicolau@mat.puc-rio.br>
=========================================================================