Fw: [obm-l] duvida

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro Prof. Morgado (e Amurpe):

Antes de mais nada, obrigado pela correção.

Como o Sr. observou muito bem, ao dizer que haviam apenas k-2 alternativas
para a cor do setor n, eu assumi, implicita, indevida e inconscientemente,
que os setores 1 e n-1 têm cores diferentes. Assim, a minha solução está
errada.

A sua idéia é permitir inicialmente que os setores 1 e n possam ter a mesma
cor, o que resultaria em k * (k-1)^(n-1) maneiras de colorir o círculo e, em
seguida, descontar o número de maneiras de colorir nas quais os setores 1 e
n tenham a mesma cor (que, como o Sr. mesmo disse, nada mais é do que
P(n-1): o número de maneiras de colorir um círculo com n-1 setores).

Daí, a recorrência: P(n) = k * (k-1)^(n-1) - P(n-1).

Agora, o mínimo que eu posso fazer é resolver esta recorrência...

P(2) = k*(k-1)    ==>    k cores para o setor 1, e k-1 para o setor 2;

P(3) = k*(k-1)^2 - k*(k-1)
        = k*(k-1)*(k-2)
        = (k-1)*[(k-1)^2 - 1]

P(4) = k*(k-1)^3 - k*(k-1)*(k-2)
        = k*(k-1)*(k^2 - 3*k + 3)
        = (k-1)*[(k-1)^3 + 1]

P(5) = k*(k-1)^4 - k*(k-1)*(k^2 - 3*k + 3)
        = k*(k-1)*(k^3 - 4*k^2 + 6*k - 4)
        = (k-1)*[(k-1)^4 - 1]

Este padrão sugere a seguinte Hipótese de Indução:
P(n) = (k-1)*[ (k-1)^(n-1) + (-1)^n ]

P(n+1) = k*(k-1)^n - P(n)
            = k*(k-1)^n - (k-1)*[ (k-1)^(n-1) + (-1)^n ]
            = k*(k-1)^n - (k-1)^n + (k-1)*(-1)^(n+1)
            = (k-1)^(n+1) + (k-1)*(-1)^(n+1)
            = (k-1)*[ (k-1)^n + (-1)^(n+1) ]

Assim, a fórmula para P(n) é, de fato:

P(n) = (k-1)*[ (k-1)^(n-1) + (-1)^n ]


Um abraço,
Claudio Buffara.

******************

PROBLEMA:
> Um circulo foi dividido em n( maior ou igual a 2)
> setores .de quantos modos podemos colori-los , cada
> setor com uma cor , se dispomos de k ( maior que 2)
> cores diferentes e setores adjacentes não devem ter a
> mesma cor?.

SOLUÇÃO ERRADA:
 > Numere os setores 1, 2, ..., n de forma que k seja adjacente a k+1 (1 <=
k
> <= n-1) e n seja adjacente a 1.
>
> Inicialmente, temos k escolhas para a cor do setor 1.
> Após colorido 1, temos k-1 escolhas para a cor do setor 2, que tem de ser
> diferente da do setor 1.
> Após coloridos 1 e 2, temos k-1 escolhas para a cor do setor 3, que tem de
> ser diferente da do setor 2.
> ......
> Após coloridos 1, 2, ..., n-2, temos k-1 escolhas para a cor do setor n-1,
> que tem de ser diferente da do setor n-2.
> Finalmente, após coloridos 1, ..., n-1, temos apenas k-2 escolhas para a
cor
> do setor n, uma vez que esta cor tem de ser diferente da cor dos setores
n-1
> e 1.
>
> Número de maneiras = k * (k-1)^(n-2) * (k-2)
>

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