Valeu Henrique..... Agora só faltam mais duas questoes para fechar...muito
obrigado pela ajuda...
abraços
Henrique Rennó <[EMAIL PROTECTED]> escreveu:
Olá Graciliano e Lucas!
Pensei de uma forma diferente mas que chega ao mesmo resultado proposto na 1ª
forma de resolução.
Depois que estacionamos o primeiro carro, os próximos só poderão ser colocados
sempre à esquerda ou à direita daqueles que já estão estacionados. Dessa forma,
temos as seguintes possibilidades:
Estacionando o 1º carro na:
1ª posição: 0 E, n-1 D
2ª posição: 1 E, n-2 D
3ª posição: 2 E, n-3 D
.
.
.
nª posição: n-1 E, 0 D
ou seja, a quantidade de escolhas E (esquerda) ou D (direita) depende de onde
foi posicionado o 1º carro. Portanto o resultado seria o valor das somas das
permutações com repetição: 0E,n-1D + 1E,n-2D + 2E,n-3D + ... + n-1E,0D =
(n-1)!/[0!(n-1)!] + (n-1)!/[1!(n-2)!] + (n-1)!/[2!(n-3)!] + ... +
(n-1)!/[(n-1)!0!] = Cn-1,0 + Cn-1,1 + Cn-1,2 + ... + Cn-1,n-1 = binomial(n-1,0)
+ binomial(n-1,1) + ... + binomial(n-1,n-1) = 2^(n-1) (triângulo de Pascal)
Esse problema é parecido com aqueles em que há um grid regular com 2 pontos
marcados e pode-se movimentar sempre uma unidade para baixo e direita, para
baixo e esquerda, para cima e direita ou para cima e esquerda, e pede-se
quantas são as formas ou caminhos possíveis para chegar no ponto destino
partindo do ponto origem (em alguma das configurações de movimentação).
Abraços!
On 6/11/07, Lucas Mendes Marques Goncalves <[EMAIL PROTECTED]> wrote: >
> 5) Suponha que "n" carros estao em fila para entrar em um estacionamento
> que possui "n" vagas, lado a lado. Se o primeiro carro pode estacionar onde
> quiser e cada um dos outros carros ao estacionar deve justapor_se a um carro
> já estacionado, quantos sao os modos possiveis dos carros ocupararem as "n"
> vagas? OBS: Essa questao eu achei muito de interpretação, pois se for um
> estacionamento por exemplo em circulo, o problema é facil, porem se as vagas
> forem em fila reta, eu acho que fica diferente. Ai foi que eu nao entendi..
>
Vou assumir uma linha reta (e francamente não tenho certeza de como
faria o circulo ...)
E vou apresentar dois raciocinios para resolver o problema.
Possivelmente os dois são trivias ...
Primeiro, podemos tomar isso como uma soma de binomiais.
^
_ _ _ _ _ _ _ _
Se o primeiro carro tomar a primeira posição na fila, não vai caber
ninguém à sua direita.
Se ele estiver na terceira posição
^
- - - - - - - -
haverá dois espaços para carros à direita (notando que, uma vez que eu
escolha quais carros ficam a direita, já escolhi também como eles
estão)
dessa forma, eu acabo com:
binomial (n-1,0) + binomial (n-1,1) + ... binomial (n-1,n-1)
(estou escolhendo os conjutos de "carros à direita")
mas, como sabemos, isso é o mesmo que
2^(n-1)
(isso se prova facilmente calculando (1+1)^k pela expansão binomial)
a segunda forma, terrivelmente mais simples, é simplesmente escolher o
conjuto de carros à direita, sem considerar o tamanho.
Ai, colocamos o primeiro carro convenientemente.
(se houvesse 5 carros, e eu dissesse que o 3 e o 4 estão à direita, já
determinei a coisa toda: 4 3 1 2 5 )
cada carro tem duas opções: direita ou esquerda.
Assim, temos tb 2^(n-1)
(espero que isso esteja certo ^^)
------------------------------------------------------
For three years I had roses, and apologised to nobody.
------------------------------------------------------
=========================================================================
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
=========================================================================
--
Henrique
---------------------------------
Novo Yahoo! Cadê? - Experimente uma nova busca.
