[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] corredor



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>
=========================================================================