Re:Questão de Olimpiada

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxx>]

subscribe obm-rj iolanda_marta@hotmail.com
end
==============================================================================
On Sat, 29 May 1999, Iolanda Brazão wrote:

> Alô
> 
> Sou excelente aluna de matematica. Tentei, tentei e não consegui resolver a 
> questão que a OBM enviuo:
> 
> Ao longo de uma circunferencia dispões de "N" casas. Com "P" cores, de 
> quantas maneiras diferentes é possivel pintar estas casas de forma que, 
> sempre, duas casas quaisquer vizinhas não sejam pintadas com  a mesma cor ?
> 
> Sera que alguém pode me ajudar ? Sera que o Nicolau pode resolver esta 
> questão para mim ?
> 
> Abraços
> 
> Iolanda Marta

Seja f(N) a resposta do problema e g(N) a resposta do problema análogo
quando as casas estão *em fila*.
Temos f(1) = 0, f(2) = P(P-1), f(3) = P(P-1)(P-2).

Temos g(N) = P (P-1)^(N-1).
De fato, temos P opções para a primeira casa, P-1 para a segunda,...,
P-1 para a última.

Por outro lado, g(N) = f(N) + f(N-1).
De fato, se as duas casa nos extremos têm cores diferentes
isto nos dá uma forma de pintar N casas em círculo.
Se as duas casa nos extremos têm cores iguais
isto nos dá uma forma de pintar N-1 casas em círculo
(eliminando uma das casas extremas).

Agora,

f(N) = (f(N) + f(N-1)) - (f(N-1) + f(N-2)) + ... + (-1)^N (f(2) + f(1))
     = g(N) - g(N-1) + ... + (-1)^N g(2)
     = P ((P-1)^(N-1) - (P-1)^(N-2) + ... + (-1)^N (P-1))
     = (P-1)^N + (-1)^N (P-1)

Estou mandando convite para você se inscrever na lista
obm-rj@mat.puc-rio.br, para discussão de problemas de matemática.

[]s, N.
http://www.mat.puc-rio.br/~nicolau