Seja f(n, p) o número de maneiras de pintar Z_n (inteiros módulo n) com p cores de forma que i e i+1 não recebem a mesma cor.

Se o n é pequeno, faça as contas na mão mesmo...
Para n >= 4 já podemos usar uma recorrência:

Imagine que queremos colorir Z_{n+1} com p cores da maneira enunciada. Essa coloração vai induzir uma p-coloração de Z_n (basta considerar as cores dadas aos elementos 0, ..., n-1). Há duas possibilidades:
- a coloração induzida é da maneira enunciada [sabemos que há f(n, p) colorações dessa forma]
- a coloração induzida é tal que n-1 e 0 tem a mesma cor, porém cor(0) != cor(1) != cor(2) != ... != cor(n-2) != cor(n-1) = cor(0), mas então a coloração induzida em 0, ..., n-2 é da maneira enunciada para Z_{n-2}, mas há f(n-1, p) tais colorações.


No primeiro caso, a cor de n pode ser uma das p-2 cores diferentes de cor(0), cor(n-1). No segundo caso, temos de evitar apenas cor(0) e portanto há p-1 cores possíveis.

f(n, p) = (p-2) f(n-1, p) + (p-1) f(n-2, p) para n >= 4.

Abraços,

Domingos.

Olá a todos.
Como sou novo na lista, não sei se o problema que apresentarei já foi
publicado aqui, mas se alguém puder ajudar ficarei muito grato..

"N casas idênticas estão dispostas ao longo de uma praça circular. Um
pintor dispôe de p cores diferentes para pintar as casas. De quantos
modos isso pode ser feito se casas adjacentes não podem ter a mesma
cor?"
Abraços
Paulo Cesar


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

Responder a