Carrocel.
Página 1 de 1
Carrocel.
por Igor Kauan Souza da Mata Ter 06 Nov 2018, 20:16
Oito crianças estão sentadas em torno de um carrossel. De quantos modos eles podem trocar de lugar de modo que cada criança passe a ter uma criança diferente a sua direita?
Gabarito: 1625
Encontrei a seguinte resolução, todavia não consegui compreende-la. Alguém pode me ajudar com outra resolução, ou tornar essa resolução de forma que eu possa entender? Desde já agradeço.
"olha ...
por inclusao e exclusao me parece que ficaria complicado.
o que eu fiz foi o seguinte: numere as crianças de 1 a n (vou ter que
resolver o problema geral ...) (a roda começa com as crianças em ordem:
1234...n. diremos que 2 está a direita de 1)
o que eu consegui foi uma relacao de recorrencia.
a relacao é a seguinte:
F(x) = F(x-1) (x-1 -2) + F(x-2)*(x-1 -1)+F(x-2)*(x-1 -1)+F(x-3)*(x-1 -1)
a idéia é, tomando uma ordenação de tamanho menor, gerar uma de tamanho
maior.
o primeiro termo, por exemplo é "pegue uma sequencia válida, com uma criança
a menos, e coloque a enésima criança, mas nao do lado esquerdo da criança de
numero 1"
o segundo, uma seguencia inválida, mas só com uma violação, do tipo "criança
b do lado da b+1" ai, nós colocamos a enésima criança entre elas
o terceiro, uma seguencia invalida, pq a criança n-1 está do lado da 1 (e
ai, podemos colocar a nésima em qq lugar que nao seja do lado da 1)
o quarto, ambas as violações ao mesmo tempo.
a tabela fica assim:
f(2)=0
f(3)=1
f(4)=1
f(5)=8
f(6)=36
f(7)=229
f(
=1625 (que é o valor que vc queria)
(note que, usando os 3 primeiros valores, fáceis de descobrir na mão, é
simples calcular os demais)"
Fonte: https://www.mail-archive.com/obm-l@mat.puc-rio.br/msg45520.html
Gabarito: 1625
Encontrei a seguinte resolução, todavia não consegui compreende-la. Alguém pode me ajudar com outra resolução, ou tornar essa resolução de forma que eu possa entender? Desde já agradeço.
"olha ...
por inclusao e exclusao me parece que ficaria complicado.
o que eu fiz foi o seguinte: numere as crianças de 1 a n (vou ter que
resolver o problema geral ...) (a roda começa com as crianças em ordem:
1234...n. diremos que 2 está a direita de 1)
o que eu consegui foi uma relacao de recorrencia.
a relacao é a seguinte:
F(x) = F(x-1) (x-1 -2) + F(x-2)*(x-1 -1)+F(x-2)*(x-1 -1)+F(x-3)*(x-1 -1)
a idéia é, tomando uma ordenação de tamanho menor, gerar uma de tamanho
maior.
o primeiro termo, por exemplo é "pegue uma sequencia válida, com uma criança
a menos, e coloque a enésima criança, mas nao do lado esquerdo da criança de
numero 1"
o segundo, uma seguencia inválida, mas só com uma violação, do tipo "criança
b do lado da b+1" ai, nós colocamos a enésima criança entre elas
o terceiro, uma seguencia invalida, pq a criança n-1 está do lado da 1 (e
ai, podemos colocar a nésima em qq lugar que nao seja do lado da 1)
o quarto, ambas as violações ao mesmo tempo.
a tabela fica assim:
f(2)=0
f(3)=1
f(4)=1
f(5)=8
f(6)=36
f(7)=229
f(
=1625 (que é o valor que vc queria)(note que, usando os 3 primeiros valores, fáceis de descobrir na mão, é
simples calcular os demais)"
Fonte: https://www.mail-archive.com/obm-l@mat.puc-rio.br/msg45520.html
Igor Kauan Souza da Mata- Padawan
- Mensagens : 67
Data de inscrição : 26/10/2018
Idade : 25
Localização : Belo Horizonte, MG, Brasil
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos|
|
|
