Fórum PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Desafio de Combinatória

5 participantes

Ir para baixo

Desafio de Combinatória Empty Desafio de Combinatória

Mensagem por arimateiab Seg 25 Jul 2011, 18:36

Seja n um inteiro positivo. Temos uma balança de dois pratos e n pesos cujas massas
são 2^0, 2^1, . . . , 2^n−1. Devemos colocar os pesos na balança, um por um, de tal forma que o prato direito nunca seja mais pesado do que o prato esquerdo. A cada passo, devemos escolher um dos pesos que ainda não estejam na balança e colocá-lo sobre o prato esquerdo ou sobre o prato direito, procedendo assim até que todos os pesos tenham sido colocados nela.Determine o número de maneiras em que isso pode ser feito.

____________________________________________
"Quando recebemos um ensinamento devemos receber como um valioso presente e não como uma dura tarefa. Eis aqui a diferença que transcende."
Albert Einstein
arimateiab
arimateiab
Elite Jedi
Elite Jedi

Mensagens : 776
Data de inscrição : 01/07/2010
Idade : 28
Localização : Estudante de Engenharia de Produção na UFPE.

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por Kongo Seg 25 Jul 2011, 19:18

Caramba impossível
AHSUahushA
Vamos ver se o pessoal consegue =)
Kongo
Kongo
Elite Jedi
Elite Jedi

Mensagens : 916
Data de inscrição : 22/01/2011
Idade : 27
Localização : Juiz de Fora - MG

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por Viniciuscoelho Dom 07 Ago 2011, 22:51


A interpretação deixo às custas de vcs...


Viniciuscoelho
Fera
Fera

Mensagens : 644
Data de inscrição : 25/12/2009
Idade : 33
Localização : Salvador

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por rihan Qua 07 Set 2011, 23:59

1. Supondo-se n=4, teremos os 4 pesos iguais a 1, 2, 4 e 8.

2. Convencionando-se que os pesos colocados no prato direito serão representados por valores negativos (-1,-2,-4,-8 ) e os colocados no prato esquerdo por valores positivos ( 1, 2, 4, 8 ).

3. Sabendo-se que a soma dos termos de uma PG de razão 2 e primeiro termo 1 é dada por (2^n) -1 , ou seja, para nossa hipótese:

1 + 2 + 4 = (2^3) - 1 = 8 - 1 = 7 < 8

Ou seja, o n-ésimo termo, i.e., o maior peso ( 2^(n-1) ), nunca poderá ser colocado à direita ( ser negativo) pois a soma de todos os outros restantes será sempre uma unidade menor.

4. O primeiro peso a ser colocado sempre será colocado à esquerda.

5. Algumas seqüências válidas:

( +1, +2, +4,+8 )
( +8, -4, -2, -1 )

6. Vejamos alguns casos para verificar se a fórmula apresentada por Viniciuscoelho está correta:

n = 1
( 1 )
1 maneira

n = 2
( 2, 1) ; ( 2, -1 ) ; ( 1, 2 )
3 maneiras

n = 3
( 4, 2, 1 ) ; ( 4, 2, -1 ) ; ( 4, -2, 1 ) ; ( 4, -2, -1 ) ;
( 4, 1, 2 ) ; ( 4, 1, -2 ) ; ( 4, -1, 2 ) ; ( 4, -1, -2 ) ;
( 2, 4, 1 ) ; ( 2, 4, -1 ) ; ( 1, 4, 2 ) ; ( 1, 4, -2 );
( 1, 2, 4 ) ; ( 2, 1, 4 ) ; ( 2, -1, 4 )
15 maneiras

O que leva a conclusão de que a referida fórmula não está correta.

7. Com as convenções ( + =: Direito e =: Esquerdo ), o conhecimento da soma da PG, técnicas de contagem ordinárias ( arranjos e combinações ) e observações de recorrências chega-se a:

Maneiras para n pesos = ( 2n )! / ( n! * ( 2^n ) )

Ou, de um modo mais simples, para n = 4, teremos:

1 * 3 * 5 * 7 = 105

Para n = 5:

1 * 3 * 5 * 7 * 9 = 945

...

Isto é, n pesos, n primeiros fatores ímpares multiplicativos.

Para os que gostam de complicar, pode-se usar o duplo fatorial (!!):

(2n -1)!!

rihan
Estrela Dourada
Estrela Dourada

Mensagens : 5049
Data de inscrição : 22/08/2011
Idade : 66
Localização : Rio de Janeiro, RJ, Itabuna-Ilhéus, BA, Brasil

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por Matheus Basílio Qui 08 Set 2011, 00:54

@rihan escreveu:7. Com as convenções ( + =: Direito e =: Esquerdo ), o conhecimento da soma da PG, técnicas de contagem ordinárias ( arranjos e combinações ) e observações de recorrências chega-se a:

Olá amigo, você poderia postar essas partes, para que possamos entender a sua resolução?

Grato,
Matheus Basílio.
Matheus Basílio
Matheus Basílio
Elite Jedi
Elite Jedi

Mensagens : 344
Data de inscrição : 22/10/2010
Idade : 25
Localização : Palmas, Tocantins

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por rihan Ter 13 Set 2011, 04:08

Vou postar sim, Matheus.

Estou esperando qualquer pronunciamento de quem propôs o desafio... Shocked

Se até amanhã ele não se pronunciar eu envio !

rihan
Estrela Dourada
Estrela Dourada

Mensagens : 5049
Data de inscrição : 22/08/2011
Idade : 66
Localização : Rio de Janeiro, RJ, Itabuna-Ilhéus, BA, Brasil

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por Matheus Basílio Ter 06 Dez 2011, 23:43

@rihan escreveu:Vou postar sim, Matheus.

Estou esperando qualquer pronunciamento de quem propôs o desafio... Shocked

Se até amanhã ele não se pronunciar eu envio !

Poderia me ajudar a concluir, Rihan.

Abraços e obrigado.
Matheus Basílio
Matheus Basílio
Elite Jedi
Elite Jedi

Mensagens : 344
Data de inscrição : 22/10/2010
Idade : 25
Localização : Palmas, Tocantins

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por rihan Ter 10 Jan 2012, 14:42

Ops !

Tinha me esquecido dessa Matheus ! Foi mal Rolling Eyes !

Já que arimateiab não comentou nada...

Vamos Lá !!! Very Happy

Vamos começar do fim affraid!

Vamos formar os movimentos, começando pelo último movimento.

Suponha os pesos {1; 2; 4; 8}

Algumas movimentações possíveis:

8;4;2;1

4;8;-2;-1

....

Qual que não pode ser o último movimento ?

O -8, certo ? (8 no prato direito)

Temos então, dos 8 possíveis movimentos (±(1;2;4;8 )), só 7 possíveis.

_ _ _ 7

Vamos para o penúltimo.

Feito um dos 7 possíveis, sobram agora 5 ( ao colocar, por exemplo, +4, tiro o +4 e o -4 e vice-versa...)

_ _ 5 7

E vamos nós !

_ 3 5 7

E:

1
3 5 7

Temos, então:

1.3.5.7 = 8.7.6.5.4.3.2.1/(8.6.4.2) = 8!/(1.2 .2.2 .3.2.4.2)

1.3.5.7 = (2.4!)!/(24.4!)

Para "n":

n(S) = ( 2n )! / ( n! * ( 2n ) )

E Vamos Lá !

rihan
Estrela Dourada
Estrela Dourada

Mensagens : 5049
Data de inscrição : 22/08/2011
Idade : 66
Localização : Rio de Janeiro, RJ, Itabuna-Ilhéus, BA, Brasil

Ir para o topo Ir para baixo

Desafio de Combinatória Empty Re: Desafio de Combinatória

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo


 
Permissões neste fórum
Você não pode responder aos tópicos