www.matematica.br

Caixas de Galton (Problema dos Caminhos)

[ Enunciado | Resolução | download | Jogar ]

 
Problema dos caminhos/Caixas de Galton
    
O problema das Caixas de Galton foi apresentado por Francis Galton (16 Fev 1822 - 17 Jan 1911). O dispositivo é composto por um tabuleiro com pinos e caixas na parte inferior, como na figura 1, sendo que:
  1. existe um tabuleiro com N linhas com pinos alinhados ao centro;
  2. a linha 1 tem 1 pino, a linha 2 tem 2 pinos e assim por diante, com a linha N com N pinos;
  3. após a linha N existem N+1 caixas, numeradas de 1 a N+1 (para receber a bola a ser lançada);
  4. é realizado o lançamento de uma bola sobre o pino 1, supondo-se que a bola ao bater em um pino na linha k, tem igual probabilidade de seguir para o pino na linha k+1 à sua esquerda ou à sua direita.
  5. o problema é saber a probabilidade da bola cair na caixa i.
 		                                               
Fig. 1. Ilustração do problema das Caixas de Galton com 5 linhas.
Na seção seguinte está a implementação que preparamos para testar o dispositivo de Galton e na seção seguinte apresentamos algumas pistas de como o problema pode ser resolvido.
 
Como "jogar"
    

A seguir uma implementação em HTML/CSS/JavaScript para simular o dispositivo proposto por Galton. Para visualizar a movimentação da bola caindo, amplie o valor do retardo e "clique" no botão "lançar" (mas neste caso, talvez seja melhor utilizar apenas uma bola, ou seja, o valor 1 para o número de lançamentos).
Para ter uma melhor percepção da "lei dos grandes números" (a frequência deve aproximar-se da probabilidade), amplie o valor do número de lançamentos e "clique" no botão "lançar" (nesse caso é melhor reduzir para 0 o valor na caixa Retardo).

Como resolver
    
Problema dos caminhos
Para resolver esse problema deve-se contar o número de caminhos mínimos distintos desde o pino 1 até cada uma das caixas, fazendo isso, por exemplo, "descobriremos" que as caixas centrais tem mais caminhos distintos quando comparadas com as caixas nos extremos.
Para isso numeremos os pinos pelo par (i,j), sendo i a linha do pino e j sua posição na linha (ou sua coluna). Assim, o pino 1 recebe o rótulo (1,1). Também denotemos por Ci,j o total de caminhos desde o pino (1,1) até o pino (i,j). Essa interpretação gráfica é ilustrada na figura 2.(a). Na 2.(b) apresentamos outra forma de interpretar a rotulação dos pinos: para chegar ao pino (i,j) (a partir do (0,0)) são feitas i escolhas de direção, sendo que em exatamente j delas foi escolhida a direção direita (para mais detalhes examine a seção sobre produtos notáveis).
. . .
Fig. 2. (a) Nomeando os pinos como linhas e diagonais destacando contagem de caminhos;
(b) Nomeando os pinos como número de escolhas de direção esquerda ou direita;
(c) Olhando o produto notável como um problema dos caminhos.

Desse modo pode-se provar o seguinte lema: para todo i e todo j, Ci,j = Ci-1,j-1 + Ci-1,j. Ou seja, o total de caminhos mínimos distintos até o pino (i,j) é igual ao total de caminhos até o pino (i-1,j-1) mais o total de caminhos até o pino (i-1,j).
Esse lema é conhecido na literatura como relação de Stifel.

Problema dos caminhos e Triângulo de Pascal
A relação acima é a mesma que aparece em problemas de combinações como no Triângulo de Pascal: o número de combinações de n tomados de k em k (Cn,k) é igual à soma das combinações de n-1 tomados de k em k (Cn-1,k) com as combinações de n-1 tomados de k-1 em k-1 (Cn-1,k-1). Essa é novamente a relação de Stifel, que usando a notação de combinação resulta na fórmula seguinte:
.
Sabendo que Cn,k = n!/(k! * (n-k)!), experimente provar essa relação para a identidade acima envolvendo combinação.

Problema dos caminhos, Triângulo de Pascal e produto notável
O problema dos caminhos também tem relação direta com os produtos notáveis, portanto com a álgebra: determinar (a+b)n corresponde a encontrar o número de termos de potências ai e bj, para i e j variando desde 0 até n. Os 4 primeiros produtos notáveis estão indicados a seguir:
(a+b)0 = 1
(a+b)1 = (a+b) = 1 a1 b0 + 1 a0 b1 = 1 a   + 1 b
(a+b)2 = (a+b)*(a+b) = 1 a2 b0 + 2 a1 b1 + 1 a0 b2 = 1 a2 + 2 a b + 1 b2
(a+b)3 = (a+b)*(a+b)*(a+b) = 1 a3 b0 + 3 a2 b1 + 3 a1 b2 + 1 a0 b3 = 1 a3 + 3 a2 b + 3 a b2 + 1 b3
Note no bloco da direita, que em azul, aparece novamente o Triângulo de Pascal.
De modo muito resumido, a relação do produto notável com o problema dos caminhos pode ser feita assim: o número de caminhos até o pino (i,j) coincide com o número de termos de potências i e j usando a nomeação do pino (i,j) como número de esquerdas e direitas para chegar nele, como indicado nas figuras 2.(b) e 2.(c).
Algumas intuições da razão da equivalência entre os problemas:
  1. Na figura 2.(b), note que para chegar ao pino (3,2) são necessários 3 movimentos, sendo que em exatamente 2 deles foi escolhida a direção "direita" (b). Veja todos os 3 possíveis caminhos: (a,b,b), (b,a,b) e (b,b,a).
  2. É possível provar que a propriedade acima vale em geral, ou seja, para chegar ao (n,k) são necessários exatamente n movimentos, sendo k para a "direita" (ou b).
  3. O produto notável (a+b)n é igual ao somatório c0anb0 + c1an-1b1 + ... + cna0bn   (veremos que cj=Cn,j).
    Exemplo: (a+b)4= (a+b)(a+b)3 = (a+b)(a+b)(a+b)2 = (a+b)(a+b)(a2+2ab+b2) =
    = (a+b)(a3+2a2b+ab2 + a2b+2ab2+b3) =
    = (a+b)(a3+2a2b+a2b+ab2+2ab2+b3) =
    = (a+b)(a3+3a2b+3ab2+b3) = a (a3+3a2b+3ab2+b3) + b (a3+3a2b+3ab2+b3) =
    = (a4+3a3b+3a2b2+ab3) + (a3b+3a2b2+3ab3+b4) =
    = a4+3a3b+a3b+3a2b2+3a2b2+ab3+3ab3+b4 =
    = a4+4a3b+6a2b2+4ab3+b4.
    Logo, c0=1, c1=4, c2=6, c3=4 e c4=1.
  4. Ao expandir o produto notável (a+b)n, teremos n+1 termos e em cada um deles haverá exatamente n "direções" (soma dos expoentes para a e b).
    Exemplo: Para o (a+b)4, cada termo tem exatamente 4 "direções", pois considerando a forma reduzida da expansão (como na da última expressão do item anterior),
        a4 tem 4 direções a; 4a3b tem 3 direções a e 1 b; 6a2b2 tem 2 direções a e 2 b; 4ab3 tem 1 direção a e 3 b; e b4 tem 4 direções b.
  5. Considerando o produto notável (a+b)n, podemos fazer um raciocínio indutivo para obter o total de termos com n "direções" sendo k delas do tipo b (e portanto, n-k delas do tipo a).
    Uma vez que (a+b)n = (a+b)(a+b)n-1, os únicos termos de (a+b)n-1 que, ao ser multiplicado por (a+b) pode gerar an-kbk são:
    1. an-k-1bk: pois multiplicado pelo a, de (a+b), gera an-kbk; e
    2. an-kbk-1: pois multiplicado pelo b, de (a+b), gera an-kbk.
    Portanto, vale a propriedade:
    o número de termos com n direções sendo k delas do tipo b (ou seja, os termos an-kbk) é igual
    ao total de termos com n-1 direções sendo k delas do tipo b (logo an-k-1bk)
    somado aos termos com n-1 direções sendo k-1 delas do tipo b (an-kbk-1).
  6. Mas a relação anterior é precisamente a relação de Stifel para o total de termos de cada potência nos produtos notáveis (essa seria uma razões para eles serem, de fato, notáveis!).
    Podemos rever a propriedade anterior de outra forma. Sendo Cn,k o número de termos com n direções sendo k delas do tipo b, Cn-1,k o número de termos com n-1 direções sendo k delas do tipo b e Cn-1,k-1 o número de termos com n-1 direções sendo k-1 delas do tipo b, então do item anterior podemos afirma que vale a relação
    Cn,k an-kbk = a Cn-1,k an-k-1bk + b Cn-1,k-1 an-kbk-1.
    pois, aplicandos os fatores multiplicativos a e b na soma (do lado direito da identidade), obtemos
    a Cn-1,k an-k-1bk = Cn-1,k an-kbk   e   b Cn-1,k-1 an-kbk-1 = Cn-1,k-1 an-kbk
    que substituindo na identidade anterior resulta que
    Cn,k an-kbk = Cn-1,k an-kbk + Cn-1,k-1 an-kbk = (Cn-1,k + Cn-1,k-1) an-kbk.
    e como an-kbk (desde que n e a+b seja não nulo), podemos dividir ambos os lados por valor preservando a identidade, com isso obtemos novamente a relação de Stifel, dessa vez via produtos notáveis,
    Cn,k = Cn-1,k + Cn-1,k-1.
    Desse modo concluímos a equivalência entre entre produtos notáveis, problema dos caminhos e Caixas de Galton.

Interessado em contribuir com o desenvolvimento (ou personalizar uma versão para você)?
     Essa versão do iGalton foi desenvolvida em JavaScript puro, sem apoio de arcabouços, então pode ser útil para interessados em aprender os fundamentos da programação HTML/CSS/JavaScript.
O iGalton é parte dos sistemas computacionais desenvolvidos pelo LInE: Software livre, dados privados.
O problema das Caixas de Galton tem sido usado no LEM em cursos desde 1999: aprendizado participativo, resolução de problemas.
 
Donwload: Para pegar uma cópia completa do iGalton (incluindo estas páginas), "clique" nesse apontador.
 
Para examinar outros sistemas educacionais livres desenvolvidos no LInE.
Software livre, dados privados.
 

Prof. Leônidas de Oliveira Brandão
Laboratório de Informática na Educação (LInE)
2023/06/28 : apontador para a apostila do LEM para professores
2023/03/01 : primeira versão desta página (e do iGalton)


voltar