Olimpíadas(Olimpíada do Canadá-2001) Probabilidade Tópico resolvido

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
Auto Excluído (ID:17906)
6 - Doutor
Última visita: 31-12-69
Jun 2017 10 16:39

(Olimpíada do Canadá-2001) Probabilidade

Mensagem não lida por 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?

Última edição: Auto Excluído (ID:17906) (Sáb 10 Jun, 2017 16:39). Total de 2 vezes.



Avatar do usuário
undefinied3
4 - Sabe Tudo
Mensagens: 1483
Registrado em: Dom 02 Ago, 2015 13:51
Última visita: 30-09-22
Jun 2017 10 17:56

Re: (Olimpíada do Canadá-2001) Probabilidade

Mensagem não lida por undefinied3 »

Consegue ver como o problema é basicamente isso?
GaltonBoard_1000.gif
GaltonBoard_1000.gif (5.88 KiB) Exibido 1106 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.

Última edição: undefinied3 (Sáb 10 Jun, 2017 17:56). Total de 1 vez.


Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.

Avatar do usuário
undefinied3
4 - Sabe Tudo
Mensagens: 1483
Registrado em: Dom 02 Ago, 2015 13:51
Última visita: 30-09-22
Jun 2017 10 18:34

Re: (Olimpíada do Canadá-2001) Probabilidade

Mensagem não lida por 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
Screenshot_4.png (1.17 KiB) Exibido 1104 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
Screenshot_5.png (1.81 KiB) Exibido 1104 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.

Última edição: undefinied3 (Sáb 10 Jun, 2017 18:34). Total de 3 vezes.


Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem (Canadá) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    3 Respostas
    931 Exibições
    Última msg por NigrumCibum
  • Nova mensagem (Canadá) Recorrência
    por Deleted User 23699 » » em Olimpíadas
    0 Respostas
    563 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem (Canadá) Trigonometria
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    632 Exibições
    Última msg por NigrumCibum
  • Nova mensagem (Canadá) Trigonometria
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    669 Exibições
    Última msg por Ittalo25
  • Nova mensagem (Canadá) Equação
    por AngelitaB » » em IME / ITA
    1 Respostas
    699 Exibições
    Última msg por Fibonacci13

Voltar para “Olimpíadas”