segunda-feira, 26 de julho de 2010

Solução a um problema de probabilidade

O problema é o seguinte:

Uma partícula se desloca sobre a reta real sempre em passos de comprimento unitário, para a direita ou para a esquerda. Estando inicialmente a partícula na origem, se ela vai dar 10 passos, cada um ao acaso para a direita ou para a esquerda, qual é a probabilidade da partícula passar pelo 3?

Este problema foi proposto durante a sessão de perguntas do último PAPMEM. Em princípio tentei algumas ideias simples, mas percebi que nenhuma delas levaria a uma solução correta. Então decidi seguir o caminho trabalhoso, mas seguro. Recomendo ao leitor interessado que tente resolver o problema por conta própria antes de clicar no link a seguir e ler minha solução. Adoraria receber comentários, correções ou soluções alternativas.

[acrescentado em 04/08/10: interpretei passar pelo 3 como ir além do 3, ou seja, atingir o 4]


Solução:

Como símbolos matemáticos mais sofisticados não são necessários, vou tentar escrever direto em texto. Espero que fique claro.

Cada um dos 1024 caminhos possíveis para a partícula tem mesma probabilidade de ocorrer, pois são 10 decisões consecutivas, com duas opções equiprováveis cada uma. Assim, vamos contar quantos desses caminhos passam pelo 3.

Cada caminho pode ser codificado como uma sequência de 10 letras, cada uma delas igual a D (direita) ou E (esquerda), representando cada a decisão correspondente a sua posição na sequência. Como a palavra passar está destacada no texto, vamos admitir que isto signifique não apenas chegar ao 3, mas ir mais além. Com esta interpretação, o problema equivale a determinar a probabilidade de se chegar ao 4.

O número total de caminhos que chegam ao 4 é a união de 4 conjuntos A_4, A_6, A_8 e A_10 definidos por

A_k: conjunto dos caminhos nos quais o 4 é atingido em k passos.

Para calcular o número de elementos dessa união, vamos utilizar o princípio de inclusão e exclusão (e, é claro, muita paciência). Representando por #A o número de elementos (cardinal) do conjunto A, temos:

1) Cardinal de cada conjunto:

#A_4 é igual ao número de sequências que começam por DDDD. Temos 2 opções para cada uma das demais letras, logo #A_4 = 2 x 2 x 2 x 2 x 2 x 2 = 64.

#A_6 é igual ao número de sequências cujas 6 primeiras letras são exatamente 5 D's e um E. Existem 6 maneiras de escolher essas 6 primeiras letras (basta escolher a posição do E), e depois 2 opções para cada uma das outras 4 letras, ou seja, #A_6 = 6 x 2 x 2 x 2 x 2 = 96.

#A_8 é igual ao número de sequências cujas 8 primeiras letras são exatamente 6 D's e 2 E's. Para determinar essas 8 primeiras letras basta escolher as posições das duas letras E, logo há 28 (combinação de 8 objetos tomados 2 a 2) maneiras de fazê-lo. A seguir, restam 2 opções para cada uma das 2 letras restantes, logo #A_8 = 28 x 2 x 2 = 112.

#A_10 é igual ao número de sequências formadas por exatamente 7 D's e 3 E's, logo #A_10 = 120 (combinação de 10 objetos tomados 3 a 3, pois, novamente, basta escolher as posições dos E's).

2) Cardinal de cada uma das 6 interseções dos conjuntos tomados dois a dois:

Interseção entre A_4 e A_6: A sequência deve começar com DDDDDE ou com DDDDED. As outras 4 letras podem ser escolhidas livremente. Logo o cardinal desta interseção é 2 x 2 x 2 x 2 x 2 = 32.

Interseção entre A_4 e A_8: após DDDD devemos ter 2 D's e 2 E's: 6 opções (combinação de 4 objetos tomados 2 a 2). As duas últimas letras são livros, logo o cardinal desta interseção é 6 x 2 x 2 = 24.

Interseção entre A_4 e A_10: após DDDD devemos ter 3 D's e 3 E's, logo o cardinal desta interseção é igual a 20 (combinação de 6 objetos tomados 3 a 3).

Interseção entre A_6 e A_8: 6 opções para as 6 primeiras letras (como no cálculo de #A_6), em seguida 2 opções para as próximas 2 letras (ED ou DE) e duas últimas letras livres. O cardinal é 6 x 2 x 2 x 2 = 48.

Interseção entre A_6 e A_10: 6 opções para as 6 primeiras letras e depois 6 opções para as 4 últimas (2 D's e 2 E's). O cardinal é 6 x 6 = 36.

Interseção entre A_8 e A_10: 28 opções para as 8 primeiras letras, e 2 opções para as duas últimas (DE ou ED). O cardinal é 28 x 2 = 56.

3) Cardinal de cada uma das 4 interseções dos conjuntos tomados 3 a 3:

Interseção entre A_4, A_6 e A_8: DDDD seguidos de ED ou DE, seguidos de ED ou DE, duas últimas letras livres. O cardinal é 2 x 2 x 2 x 2 = 16.

Interseção entre A_4, A_6 e A_10: DDDD seguidos de ED ou DE, seguidos de 2 D's e 2 E's. O cardinal é 2 x 6 = 12.

Interseção entre A_4, A_8 e A_10: DDDD seguidos de 2 D's e 2 E's, seguidos de ED ou DE. O cardinal é: 6 x 2 = 12.

Interseção entre A_6, A_8 e A_10. Como antes, agora temos 6 opções para as 6 primeiras letras, ED ou DE para as próximas duas e ED ou DE para as duas últimas. O cardinal é: 6 x 2 x 2 = 24.

4) Interseção entre os 4 conjuntos:

DDDD seguidos de ED ou DE, seguidos de ED ou DE, seguidos de ED ou DE. O cardinal é: 2 x 2 x 2 = 8.

Ufa! Agora é só aplicar o princípio de inclusão e exclusão. O cardinal da união é igual à soma dos cardinais calculados em 1), menos a soma dos cardinais calculados em 2), mais a soma dos cardinais calculados em 3), menos o cardinal calculado em 4), ou seja,

64 + 96 + 112 + 120 – 32 – 24 – 20 – 48 – 36 – 56 + 16 + 12 + 12 + 24 – 8 = 232.

Assim, a probabilidade pedida é igual a 232/1024 = 29/128, aproximadamente 23%.

7 comentários:

  1. No enunciado original, na frase "passar pelo 3", a palavra "passar" está sublinhada, por isso me parece que a intenção era "atravessar" o 3. Após conversar com um colega professor que interpretou como "atingir" o 3, verifiquei que da maneira como reproduzi o enunciado aqui a palavra "passar" ficou sem destaque, portanto é mais natural a interpretação como "atingir". Vou editar a postagem original para esclarecer este ponto.

    ResponderExcluir
  2. Pelo que entendi, a partícula passa pelo 3 se, e somente se, o número de passos para a direita superar o de passos à esquerda em pelo menos 4 passos. Então, se X for o número de passos dados para a esquerda, a probabilidade pedida seria a soma das probabilidades de X ser igual a 0, 1, 2 e 3, que são, respectivamente, iguais a 1/2^10, 10/2^10, 45/2^10 e 120/2^10. (A probabilidade de qualquer particular sequência de 10 passos é 1/2^10 e o número de sequências de 10 passos que têm k passos para a esquerda é igual ao número de maneiras de se escolher quais dos 10 passos vão ser para a esquerda, ou seja 10!/k!(10-k)!)
    Somando as probabilidades, obtem-se 176/2^10=11/64 ou aproximadamente 17,2%.

    ResponderExcluir
  3. Desculpe. Assim que postei percebi uma falha no meu raciocínio. Estava pensando na partícula terminar a sequência de 10 passos à direita do 3, o que não é necessário.

    ResponderExcluir
  4. Para corrigir minha solução inicial, basta acrescentar os casos em que
    X=6, com os 4 primeiros passos sendo necessariamente para a direita (ocorre com Probabilidade de 1/2^10);
    X=5, e os 4 primeiros passos são à direita ou no máximo um dos passos à esquerda ocorre entre os 6 primeiros passos (isso tem probabilidade 10/2^10)
    X=4 e os 4 primeiros passos são à direita ou no máximo um dos passos à esquerda ocorre entre os 6 primeiros passos ou no máximo 2 dos passos à esquerda ocorrem entre os 8 primeiros passos (isso tem probabilidade 45/2^10),
    e, por fim, acrescentando estas probabilidades às calculadas anteriormente (pois os casos considerados são mutuamente exclusivos), temos P=232/2^10, que concorda com a solução original.

    ResponderExcluir
  5. Então, fiz a primeira vez e errei encontrei 176/1024... lendo as resoluções entendi a ideia. Mas vou ressaltar que sou estudante do ensino médio e não tive probabilidade até então, por isso talvez minha opinião quanto as respostas deva ser desconsiderada, sendo que achei a primeira resposta muito longa e difícil e a segunda sem detalhamento do método usado principalmente para encontrar (x=4 45/2^10). Por isso Mestres gostaria de postar a minha o meu raciocínio de resolução.

    LEGENDA:Maiúscula quando for fixo (A), (B)
    Minúscula quando não for fixa a letra
    D=Direira E=Esquerda e Permutação=[].

    * Todos os passos para a Direita
    dddddddddd = 1 única possibilidade

    * 9 passos para a Direira e 1 para a Esquerda
    [eddddddddd] = Permutando resulta em 10 possibilidades

    * 8 passos para a Direita e 2 para a Esquerda
    [eedddddddd] = Permutando com elementos repetidos resulta em 45 possibilidades

    * 7 passos para a Direita e 3 para a Esquerda
    [eeeddddddd] = Permutando com elementos repetidos resulta em 120 possibilidades

    A partir de agora os passos vão exigir uma ordem prévia para passar pelo "3".
    * 6 passos para a Direita e 4 para a Esqueda
    [eedddddd]EE = Permutando as 8 primeiras letras e fixando as 2 últimas resulta em 28 possibilidades
    AINDA EXISTEM OUTRAS SITUAÇÕES:detalhadas para evitar uma possivel repetição.
    [eddddd]EEDE = 6 possibilidades
    [eddddd]EEED = 6 possibilidades
    DDDDEEDEDE = 1 Possibilidade
    DDDDEEDEED = 1 Possibilidade
    DDDDEEEDDE = 1 Possibilidade
    DDDDEEEDED = 1 Possibilidade
    DDDDEEEEDD = 1 Possibilidade
    TOTAL DE 45 Possibilidades

    * 5 passos para a Direita e 5 para a Esquerda
    [eddddd]eeee = 6 Possibilidades
    DDDDEE[deee] = 4 Possibilidades
    TOTAL DE 10 Possibilidades

    * 4 passos para a Direita e 6 para a Esqueda
    DDDDEEEEEE = 1 possibilidade

    Espaço Amostral= cada passo possibilita duas alternativas direita ou esquerda 2.2.2.2.2.2.2.2.2.2.2= 1024

    Probabilidade: 232/1024

    Por favor Sr. Mestres apontem minhas falhas, pois sou conciente que me faltou um método, mas o resultado bateu, posso considerar certa minha resolução?

    Grato
    claudiomfa@yahoo.com.br

    ResponderExcluir
  6. MAIS EU QUERIA A RESPOSTA PQ EU NAO TENHO LIVRO

    ResponderExcluir

Minha preferência é não moderar os comentários, mas eventualmente poderei excluir os que não acrescentem valor. Recomendo enfaticamente o uso da grafia correta das palavras, evitando abreviações.