IME / ITA ⇒ IME 2010 Análise combinatória

[joaoturchette]

07. O pipoqueiro cobra o valor de R$ 1,00 por saco de pipoca. Ele começa seu trabalho sem qualquer dinheiro para troco. Existem oito pessoas na fila do pipoqueiro, das quais quatro têm uma moeda de R$ 1,00 e quatro uma nota de R$ 2,00. Supondo uma arrumação aleatória para a fila formada pelas oito pessoas e que cada uma comprará exatamente um saco de pipoca, a probabilidade de que o pipoqueiro tenha troco para as quatro pessoas que pagarão com a nota de R$ 2,00 é:

Resposta

---

R:1/5

[Auto Excluído (ID:276)]

Boa noite !

contei as situações favoráveis da seguinte forma :

O número de pessoas com moedas de um real que já compraram pipoca tem que ser maior ou igual a metade do número total de pessoas que já compraram pipoca em todos os momentos. De fato, pois independente da ordem, essa é uma característica que haverá de ser notada para que ele sempre tenha troco.

usei a conotação [tex3]a / b[/tex3] , onde

[tex3]a \Rightarrow[/tex3] pessoas que JÁ COMPRARAM pipoca com moeda.
[tex3]b \Rightarrow[/tex3] pessoas que JÁ COMPRARAM pipoca.

Portanto, são elas :
[tex3]1/1[/tex3]
[tex3]1/2[/tex3] [tex3]2/2[/tex3]
[tex3]2/3[/tex3] [tex3]3/3[/tex3]
[tex3]2/4[/tex3] [tex3]3/4[/tex3] [tex3]4/4[/tex3]
[tex3]3/5[/tex3] [tex3]4/5[/tex3]
[tex3]3/6[/tex3] [tex3]4/6[/tex3]
[tex3]4/7[/tex3]
[tex3]4/8[/tex3]

Portanto, são 14 situações válidas. Definidos os 14 tipos de posicionamento, poderemos substituir uma pessoa por outra, estando as duas no mesmo grupo. E como isso vale para os dois grupos, o número de casos favoráreis é [tex3]14 . 4! . 4![/tex3]. O número de arranjos de 8 pessoas tomadas 8 a 8 é [tex3]8![/tex3]. Logo, a probabilidade é [tex3]\frac{14 . 4! . 4!}{8!}=\frac{1}{5}[/tex3]

[PJMS]

Boa tarde!
Desculpe-me pela intromissão. Porém, no meu ponto de vista sua contagem, por uma infeliz coincidência, levou ao número correto de eventos favoráveis. Para se chegar por exemplo em 4/4, necessariamente temos que passar por 1/1, 2/2 e 3/3. Portanto, os eventos não são excludentes, e não cabe utilizar soma.
É fácil ver que o critério fura para o universo de duas pessoas.
Pelo seu raciocínio teríamos como favoráveis:
1/1 e 1/2. Somando teríamos 2 situações válidas. O que é absurdo pois com duas pessoas só formamos 2 filas de 2, 2! E se o primeiro a chegar requerer troco "quebra as pernas" do pipoqueiro. O erro é que ninguém chega em 1/2, sem passar por 1/1.
Para o caso de 4 pessoas na fila, novamente pelo raciocínio exposto teríamos:
1/1; 1/2; 2/3 e 2/4. Novamente encontrários 4 situações favoráveis (excetuando-se as permutações das pessoas, quando teríamos que multiplicar por (2!)^2). Representando por 0 os que não necessitam de troco e por 1 os que necessitam é fácil ver que só temos duas situações: 0101 ou 0011 e não 4.
Falha para fila de 6 pessoas, de 10 pessoas...
Um aluno normal, resloveria essa situação com árvore e usando a restrição por você observada, que o número de pessoas que já compraram com moeda deverá ser maior ou igual que a metade das pessoas que já compraram.
Como, quando o número de pessoas com moeda atingir quatro a árvore nunca mais bifurca, só restará caminhar acrescentando uma pessoa que necessitará de troco a cada passo até que a folha tenha oito pessoas. Porém para efeito de contagem pode-se parar quando se atingir 4 pessoas com moedas. Portanto o número de situações favoráveis se resumirá ao número de caminhos existentes para se atingir: 4/4; 4/5; 4/6; 4/7 (observar que não se chega a 4/8 sem passar por um dos casos anteriores), repeitando a restrição em negrito acima e a de que não se pode atingir um valor dos listados passando por outro valor listado. Ou seja, não vale contar atingir 4/5 passando por 4/4. Desnehei uma árvore, mas ela perdeu a formatação ao ser copida. Observe que todos os filhos de um dado nó, ou se aumentam o numerador e denominador da fração em uma unidade (significa que chegou alguém com troco) ou se aumenta apenas o denominador em uma unidade (chegou alguém sem troco), tomando o cuidado de não crescer a árvore para um valor que não pertença ao conjunto de valores que você indicou como válidos, V= {1/1, 1/2, 2/2, 2/3, 3/3, 2/4. 3/4, 4/4, 3/5, 4/5, 3/6, 4/6, 4/7}
É obrigatório que árvore comece com 1/1. Aqui vou precisar da ajuda de vocês para que visualisem as ligações entre os nós e outros nós e entre nós e as folhas.
O nó inicial é obrigatoriamente 1/1. Por comodidade quando filho representar uma pessoa sem troco estará a esquerda dos pais e em caso contrário a direita. Quando só houver um filho, para atender a restição em negrito, logicamente será a do filho a direita.
F(a,b) é o par de filhos ou simplesmente um filho do nó a/b
F(1,1) = {1/2, 2/2}; F(1,2)= {2/3} F(2,2) = {2/3; 3/3}Chegamos a dois filhos iguais, por isso só precisamos ver os caminhos oriundos de 2/3 e multiplicálo por dois. E ver os caminhos oriundos de 3/3.
F(2,3) ={2/4,3/4} Pegar os caminhos do filho 2/4 F(2,4)={3/5} F(3,5) ={3/6; 4/5} F(3,6)={4/7}. seguindo o caminho de 3/4: F(3/4)= {3/5;4/5} F(3/5)= {3/6,4/6} F(3,6) = {4/7}.
Dessa forma, temos que para filhos de 2/3 há 5 caminhos. 3 caminhos passando por 3/4 e dois por 2/4. Como há dois caminhos que levam a 2/3. Temos 10 favoráveis.
Faltam ver os caminhos de 3/3.
F(3,3)= {3/4,4/4} como já vimos que há três caminhos oriundos de 3/4. Temos que há quatro caminhos oriundos de 3/3.
Portanto, há ao todo 10 + 4 = 14 sequências favoráveis. Desenhando a árvore fica bem mais fácil.
E um aluno diferenciado resolveria observando que a fila é uma palavra de Dyck de comprimento 2n (no caso n =4) e se valeria do número de Catalan.
Cn = C(2n,n)/(n+1), para n= 4 teríamos C4 = C(8,4)/5= 70/5 = 14. Onde C(n,p) é o número combinatório de n p a p.
O resto do raciocínio está perfeito.

http://es.wikipedia.org/wiki/N%C3%BAmeros_de_Catalan
http://mathworld.wolfram.com/CatalanNumber.html