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