On Tue, Jan 13, 2004 at 08:04:54PM -0200, Pedro Costa wrote: > oi, turma > me dê uma ajuda nesta questão: > > 2n pessoas foram ao cinema. Metade dessas pessoas trazia consigo apenas uma > nota de cinco reais cada uma, a outra metade trazia consigo apenas uma nota > de dez reais cada uma. O ingresso custa cinco rais e, inicialmente, o caixa > está absolutamente sem dinheiro. A respeito dessa situação, existem > exatamente quantas maneiras possíveis de se ordenar as 2n pessoas na fila de > modo que sempre haja troco
A condição é que se botarmos o dedo entre duas pessoas da fila, o número de pessoas na nossa frente com notas de 5 deve ser maior ou igual ao número de pessoas com nota de 10. Este é um dos problemas clássicos que têm por resposta os números de Catalan. Ou seja, a resposta é f(n) = binomial(2n,n)/(n+1). Para ver isto, considere o problema análogo com 2n+1 pessoas, n+1 com notas de 10 e n com notas de 5. É bem claro que em algum momento o caixa vai ficar sem troco. Qual a probabilidade de que isto aconteça com a última pessoa da fila? Afirmo que esta probabilidade é 1/(2n+1). De fato, afirmo que dada qualquer arrumação das pessoas em círculo, há sempre exatamente uma maneira de abrir este círculo para montar uma fila com a condição acima. Senão vejamos. Desenhe uma poligonal a partir do ponto (0,0). Para cada pessoa com uma nota de 5, ande 1 para cima e para cada pessoa com uma nota de 10, ande 1 para a direita. A poligonal vai acabar no ponto (n,n+1) e a condição é a de que ela deve estar toda acima da diagonal exceto obviamente pelo último segmento. Equivalentemente, ela deve estar toda acima da reta que liga os extremos (0,0) a (n,n+1). Bem, basta procurar entre os vértices da poligonal aquele vértice para o qual o valor de (n+1)x - ny é mínimo: rodando a fila para trazer este ponto até (0,0) resolve o problema. Acho que você já deve ter entendido pq isto resolve o problema original. Há binomial(2n+1,n)/(2n+1) = binomial(2n,n)/(n+1) maneiras de arrumar a fila em qualquer um dos dois problemas. Há mais ou menos um mês eu mandei estes links para a lista, mas mando de novo: http://www-math.mit.edu/~rstan/ec especialmente http://www-math.mit.edu/~rstan/ec/catalan.ps.gz []s, N. ========================================================================= 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 =========================================================================