Olimpíadas ⇒ (Olimpíada do Canadá-2001) Probabilidade

[Auto Excluído (ID:17906)]

Os números [tex3]−10, −9, −8, . . . , 9, 10[/tex3] são arrumados numa linha. Cada jogador coloca uma moeda no [tex3]0[/tex3] e joga a moeda [tex3]10[/tex3] vezes. Para cada cara, a moeda é movida uma casa para a esquerda e para cada coroa, a moeda é movida uma casa para a direita. Se pintarmos um ou mais números de preto e os restantes de branco, encontramos que a chance da moeda acabar num número preto é [tex3]\frac{m}{n}[/tex3] com [tex3]m + n = 2001.[/tex3] Qual é o maior valor possível de números pretos?

[undefinied3]

Consegue ver como o problema é basicamente isso?

GaltonBoard_1000.gif (5.88 KiB) Exibido 1394 vezes

Cada linha de pinos é uma das 10 jogadas da moeda, e cada coluna que ela cai é o número final.

Esse problema segue a distribuição binomial, ou seja, a probabilidade de uma bolinha cair em uma certa coluna é [tex3]C_n^k p^{k}(1-p)^{n-k}[/tex3], no caso, p=1/2 e 1-p=p. Por exemplo, tome um caso reduzido de 5 colunas (-2 -1 0 1 2) e 2 jogadas (o número de colunas é sempre 2j+1, sendo j o número de jogadas). Pra chegar nos cantos, só tem um jeito que é tirando sempre cara ou sempre coroa, pra chegar no 1 ou -1, podíamos estar no zero ou no -2 antes, e enfim, dá pra ver um triângulo de pascal surgindo. A probabilidade de cair no 2 ou -2 é [tex3]C_{0\ ou \ 4}^{4}(\frac{1}{2^2})[/tex3]
Estamos interessados no caso (-10,...,0,...,10), ou seja, 21 colunas e 10 jogadas. As probabilidades de cada coluna serão [tex3]C^{20}_{p}.\frac{1}{2^{10}}[/tex3].

Tá, feita essa análise, vamos continuar com o problema. Queremos pintar alguma quantidade de colunas de preto e calcular a probabilidade da moeda cair em um desses pretos. Isso é escolher algumas colunas e somarmos a probabilidade delas. Só que queremos que o resultado disso seja [tex3]\frac{m}{n}[/tex3] com m+n=2001, e queremos o máximo número de colunas escolhidas.
Repare, vamos, só pra introduzir a ideia, escolher as colunas -1, 0 e 1. A probabilidade [tex3]\frac{m}{n}[/tex3] seria dada por [tex3]C^{20}_{9}.\frac{1}{2^{10}}+C^{20}_{10}.\frac{1}{2^{10}}+C^{20}_{11}.\frac{1}{2^{10}}=\frac{1}{2^{10}}(C^{20}_{9}+C^{20}_{10}+C^{20}_{11})[/tex3]
No geral, a décima potência de 2 sempre estará como fator da expressão, ou seja, temos [tex3]\frac{1}{1024}.\sum C^{20}_{p}=\frac{m}{n}[/tex3]
Bom, suponho que m e n são primos entre si para a fração ser irredutível. Além disso, vou chamar essa probabilidade de x de agora em diante.
Agora ta ficando difícil pra eu continuar... To sem ideia pra achar um jeito de achar uma estratégia pra encontrar a resposta... Vou continuar pensando e qualquer coisa posto algo, mas travei total. Talvez exista um outro caminho mais fácil? Essa analogia ao tabuleiro da imagem foi o mais imediato que me veio à cabeça.

[undefinied3]

Tá, eu vacilei ao converter o problema nesse quadro. Tem alguns detalhes a mais, então vou fazer na raça. A ideia ainda é idêntica, mas as contas mudam um pouco:

Pro caso -2 -1 0 1 2, temos:

Screenshot_4.png (1.17 KiB) Exibido 1392 vezes

Pro -2 e pro 2, temos [tex3]C^2_{0 \ ou \ 2}*\frac{1}{2^2}[/tex3] de chance, e pro zero, [tex3]C^2_{1}*\frac{1}{2^2}[/tex3]
Ou seja, pros 21 números, teremos [tex3]C^{10}_{p}*\frac{1}{2^{10}}[/tex3]. É isso mesmo, pois certos números não tem como obter no final. No exemplo acima, não dá pra cair no -1 e no 1. Se formos pro próximo:

Screenshot_5.png (1.81 KiB) Exibido 1392 vezes

Basicamente, a paridade do número de jogadas define a paridade dos números disponíveis. Repare que aqui temos 3 jogadas, e só podemos cair em números ímpares. No caso de 10 jogadas, só poderemos cair nos pares (-20, -18 ... 0 ... 18, 20)

Queremos [tex3]x=\frac{1}{1024}.\sum C^{10}_p[/tex3], agora notando que p=0 é -20, p=1 é -18 e assim por diante.
Agora as coisas fazem mais sentido, antes tava dando uns números absurdamente altos e eu não estava entendendo o motivo.
Comecemos afirmando que a resposta é pelo menos 10, pois podemos pintar todos os números ímpares já que eles não entram nas contas. Agora, vamos ver se consiguimos poupar algum esforço supondo que a soma dos binomiais não simplifique o 1024 no denominador, de modo que n=1024 e m=977. De fato, isso é uma possibilidade pois 977 não simplifica 1024, resta ver se a soma pode dar 977. Convém termos a décima linha do triângulo de pascal:
1 10 45 120 210 252 210 120 45 10 1
Ora, mas isso é fantástico! Veja que [tex3]977=1024-45-1-1[/tex3], ou seja, podemos pintar TODOS de preto, exceto um de 45 e os dois de 1! De fato:
[tex3]\frac{10+45+120+210+252+210+120+10}{1024}=\frac{977}{1024}, \ 977+1024=2001[/tex3]
Então temos a resposta: podemos pintar 10+11-3=18 números de preto, e lhe afirmo que este é a maior quantidade que podemos pintar, pois veja:
Se pudermos pintar mais do que isso, será 19, 20 ou 21. Pintar todos é um absurdo, pois teríamos [tex3]\frac{m}{n}=1[/tex3]. Pintar 20 é fácil ver que não gera resposta, pois se escolhermos um binomial par, o denominador simplifica e a soma do numerador com denominador irá ficar bem mais distante de 2001. Se escolhermos um ímpar, não irá simplificar e teríamos m+n=1024-C+1024=2048-C=2001, e teríamos que ter um binomial com valor 47, que não está na linha. Finalmente, pintando 21, se a soma for par, o denominador simplifica e a soma cai muito de valor. Se o resultado for ímpar, teríamos necessariamente que pegar uma vez o 45 e algum outro binomial, de modo que m+n=1024-45-C+1024=2003-C=2001, mas não temos um binomial de valor 2.
Segue que podemos pintar no máximo 18 números de preto.