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.