Re: [obm-l] COMBINATÓRIA

["Henrique Rennó" <henrique.renno@xxxxxxxxx>]

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 <lucasmmg@linux.ime.usp.br> 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