[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Analise combinatoria - quantas comissoes?
On Tue, Jul 10, 2007 at 04:28:10PM -0300, Paulo Santa Rita wrote:
> Ola Carissimo Prof Nicolau edemais colegas desta lista ... OBM-L,
> Em primeiro lugar me permita explicar o teor da sua critica aos
> nossosleitores para que todos possam entender...
> 1) ESCLARECIMENTO DA CRITICA
> Considerem duas pessoas - Isaac e Vitor - e um "ano" de 3 dias. Umvetor do
> tipo (DIA1,DIA2,DIA3) vai representar o "ano". Como podemocorrer os
> aniversarios destas 2 pessoas ao longo deste "ano" ? Assim:
> (Isaac, Vitor, 0) , (Vitor, Isaac, 0)(Isaac, 0, Vitor) , (Vitor, 0,
> Isaac)(0, Isaac, Vitor) , ((0, Vitor, Isaac)
> (Isaac e Vitor, 0, 0), (0, Isaac e Vitor, 0) e ( 0, 0, Isaac e Vitor)
> Considerando equiprovavel as possibilidades, a probababilidade de cadauma
> seria 1/9, obvio. Entretanto, considerando que as possibilidade
> de(Isaac,Vitor,0) e (Vitor, Isaac,0) corresponde A MESMA SOLUCAO (1,1,0)da
> equacao :
> X1 + X2 + X3 = 2
> Segue que a probabilidade da solucao (1,1,0) e o dobro, isto e, e 2/9.Acho
> que deixei claro a CRITICA CRITERIOSA que o Carissimo ProfNicolau faz.
Até aqui tudo bem, isto é exatamente o que eu tentei dizer.
> 2) COMO EU LI O PROBLEMA
> As solucoes (Isaac, Vitor,0) e (Vitor,Isaac,0) sao diferente porqueeles
> nasceram em dias diferentes. Mas, suponha que eles nasceram nomesmo dia. Um
> poderia ter nascido antes do outro. Neste caso :
> (Isaac e Vitor,0,0) e (Vitor e Isaac,0,0) seriam diferente, pois,
> naprimeira 3-upla, Isaac nasceu antes do Vitor, o contrario tendoocorrido
> na segunda 3-upla. Portanto, a solucao (2,0,0) tambemrepresentaria duas
> possibilidades.
> Portanto, eu considerei INTENCIONALMENTE irrelevante a diferenca deordem,
> o que implica considerar equiprovaveis as diversas solucoes de
> X1 + X2 + ... + X365 = 200
Não acho convincente esta sua leitura do problema.
Não vejo como a presença ou ausência da hora de nascimento
na certidão de nascimento possa afetar a resposta do problema.
Para mim o problema pode ser reformulado assim:
Considere um dado com N = 365 faces.
Jogue o dado M = 200 vezes e tabule quantas vezes A[i] sai a resposta i.
Tome m = max A[i]. Qual a probabilidade de que A[1] = m?
Ou equivalentemente:
Obtenha a lista A como acima.
Ordene a lista A, tome seu máximo m e conte quantas vezes aparece o valor m;
chamemos este número de Y.
Qual a esperança da variável aleatória Y?
Escrevi um programa maple para simular esta última versão do problema:
jojo := proc(N,M) local i, j, roll, A, As, m, Y:
roll := rand(1..N):
A := array(1..N,sparse):
for i to M do j := roll(): A[j] := A[j] + 1: od:
As := sort(convert(A,list)):
m := As[-1]: Y := 1:
for j from 2 to M do
if (As[-j] < m) then break: else Y := Y+1: fi: od:
return(Y); end;
a := array(1..25000): for i to 25000 do a[i] := jojo(365,200): od:
(Aqui espere um pouco até o computador/programa rodar esta coisa 25000 vezes)
pp := 0: for i to 25000 do pp := pp + q^a[i]: od: sort(pp);
41 38 36 35 33 28 15 14 13 12
2 q + q + q + q + 5 q + q + q + 7 q + 20 q + 68 q
11 10 9 8 7 6 5
+ 159 q + 375 q + 685 q + 1092 q + 1605 q + 1788 q + 1837 q
4 3 2
+ 1505 q + 1553 q + 3656 q + 10638 q
(Note que temos um máximo local em Y = 5.
Pelos exemplos que eu vi isto ocorre quando o máximo é 3.
O máximo global em Y = 1 corresponde a um máximo mais alto.)
pd := diff(pp,q): subs(q=1,pd);
81750
evalf(%/25000);
3.270000000
Bom, esta é a resposta aproximada. Ou melhor, a resposta é isso
dividido por 365.
> 3) COMO ATENDER A EXIGENCIA DA CRITICA
> Considerando que a ordem dos nascimento em um mesmo dia saoirrelevantes e
> atendendo somente a diferencas de dias, como computar onumero de
> possibilidades para uma particular solucao numerica ?
> Vou mostrar isso atraves de um exemplo.
> Considere a solucao : (5,4,3,1,1,1,0,0) de X1 + X2 + ...+ X8 = 15. Aquantas
> possibilidades ela corresponde ? Facil : do total de 15pessoas escolho 5
> para colocar na primeira posicao, BI(15,5). Sobram10 pessoas, das quais
> escolho 4 para colocar na segunda posicao,BI(10,4). Sobram 6 pessoas, das
> quais escolho 3 para colocar naterceira posicao, BI(6,3). A seguir permuto
> as tres posicoescorrespondem aos 1's. Isso da :
> T=Bi(15,5) * Bi(10,4) * Bi(6,3) * 3!
> Como vemos, e facil fazer a computacao. O problema ( que ja etrabalhoso )
> vai apenas ficar mais trabalhoso. Eu gosto muito depensar, mas detesto
> fazer calculos.
Acho que isto que você está esboçando é correto para valores menores de M e N
mas para os valores dados no problema é incrivelmente trabalhoso.
> 4) ESTENDENDO O PROBLEMA
> Usando o mesmo contexto e considerando as solucoes de
> X1 + X2 + ... + X365 = 200
> equiprovaveis ( considere nascimentos de 200 coelhos albinos ) qual
> aprobabilidade que num determinado dia "d" NAO SEJA EXTREMO, isto e,nao
> seja maximo e nem seja minimo ?
Para os valores de M e N do problema é óbvio que o mínimo é 0.
Achar o valor esperado do número de 0s não é difícil
então esta variante é tão difícil quanto a outra.
Ou melhor, relendo o que você escreveu e corrigindo esta sua leitura
a meu ver forçada de considerar equiprováveis as soluções.
[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================