Valeu Lucas Abraços Lucas Mendes Marques Goncalves <[EMAIL PROTECTED]> 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.