Re: [obm-l] Tentei ,tentei.....

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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
=========================================================================