[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] COMBINATÓRIA



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.