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 é <[EMAIL PROTECTED]> =========================================================================