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