Re: [obm-l] COMBINATÓRIA

[Graciliano Antonio Damazo <bissa_damazo@xxxxxxxxxxxx>]

Valeu Lucas

Abraços

Lucas Mendes Marques Goncalves <lucasmmg@linux.ime.usp.br> escreveu:

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

---

Novo Yahoo! Cadê? - Experimente uma nova busca.