Re: [obm-l] Analise combinatoria - quantas comissoes?

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

Oi Paulo,

Desculpe-me por criticar uma solução incompleta,
mas se eu bem entendi a sua solução acho que você erra
ao considerar equiprováveis as várias soluções de X1 + ... + X365 = 200.

Para não nos perdermos, aqui vai de novo o problema original:

> Imagine-se num grupo de 200 pessoas, e imagine que todos os anos tenham 365
> dias (isto é: ignore a existência de anos bissextos). Seja f: {dias} -> N
> tal que f(d) = número de aniversariantes no dia d. Seja d_0 o dia de seu
> aniversário. Qual é a probabilidade de que f(d_0) seja um máximo da
> função f?

Vamos trocar os números: são duas pessoas e o "ano" tem 3 dias.
Temos as possibilidades:
(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)
mas elas *não* são equiprováveis!
As três primeiras têm probabilidade 1/9 cada
e as três últimas probabilidade 2/9 cada.
Entendo que o "você" do problema não é membro do grupo de pessoas.
A probabilidade de que f(d_0) seja um máximo nada mais é do que a prob
de que X1 seja máximo que é de 5/9, correspondente aos casos (2,0,0),
(1,1,0) e (1,0,1). Observe que nestes dois últimos casos f(d_0) é 
um máximo empatado com outro máximo.

Isto coincide com a sua solução?

[]s, N.





On Mon, Jul 09, 2007 at 04:50:46PM -0300, Paulo Santa Rita wrote:
> Ola Pessoal,
> 
> Tentarei fazer um esboco melhor. Os detalhes voces preenchem. Como
> estou escrevendo ao mesmo tempo que faco outras coisas, pode haver
> algum erro de calculo, corrijam por favor. Para facilitar o
> entendimento da minha solucao vou resolver previamente uma outra
> questao. Considere a equacao :
> 
> X1 + X2 + X3 = 12
> 
> Quantas solucoes inteiras e não-negativas tem esta equacao tais que
> para todo i=1,2,3 tenhamos Xi =< 7 ? Facil. Seja Yi= 7 – Xi, i=1,2,3.
> Segue que Xi = 7 – Yi. Daqui :
> 
> (7-Y1) + (7-Y2) + ( 7-Y3) = 12   => Y1 + Y2 + Y3 = 9
> 
> E facil encontrar quantas solucoes inteiras e não negativas tem esta
> ultima equacao. Existe ate uma formulazinha que da o valor direto. E
> igualmente facil perceber que a toda solucao desta ultima equacao
> corresponde uma, e somente uma, solucao para a equacao original.
> Assim, a questao original esta respondida e e facilmente generalizavel
> para um numero arbitrario de incognitas ...
> 
> Voltando ao problema original, seja Xi o numero de pessoas que fazem
> aniversario no dia i, i podendo variar no intervalo 1 =< i =< 365.
> Assim, qualquer configuracao possivel pode ser imaginada como uma
> solucao inteira não-negativa da equacao :
> 
> X1 + X2 + ... + X365 = 200
> 
> Queremos saber em quantas destas solucoes o valor de Xi e maximo. Seja
> Xi um valor arbitrario A tal que 1 =< a =< 200. Entao :
> 
> Xi = A => X1 + X2 + ... + A + ... + X365 = 200
> X1 + X2 + ... + Xi-1 + Xi+1 + ... + X365 = 200 – A
> 
> Procuramos as solucoes inteiras e não negativas desta ultima equacao
> para as quais tenhamos Xk =< A, coisa que já aprendemos a fazer la em
> cima. Fazendo "A" variar de 1 ate 200 e somando tudo chegamos ao total
> de solucoes nas quais no dia "i" ocorreu um maximo. Seja T este total.
> Agora, achamos o total de solucoes inteiras e não-negativas da equacao
> :
> 
> X1 + X2 + ... + X365 = 200
> 
> Seja V o total de solucoes. A probabilidade procurada e T/V.
> 
> FIM DO PRIMEIRO ESBOCO
> 
> 
> 
> 
> Para que o problema fique consistente, vou supor que apenas 7 homens e
> 4 mulheres são simultameamente fluentes em frances e Phd em
> Matematica. O total de comissoes possivel e, obviamente :
> 
> T = BINOM(53,10) * BINOM(47,10)
> 
> 1) NO MAXIMO 7 PESSOAS SAO FLUENTES EM FRANCES
> 
> Deste total vou retirar todas as comissoes nas quais no maximo 7
> pessoas são fluentes em frances. Para ver como e possivel fazer isso,
> considere o par (H,M) onde H+M = 7, H e o total de homens e M o total
> de mulheres fluentes em frances :
> 
> (H1,M1)=(7,0)    =>    U1= BINOM(28,3)*BINOM(25,7)*BINOM(43,10)
> (H1,M1)=(6,1)    =>    U2=BINOM(28,4)*BINOM(25,6)*BINOM(43,9)*BINOM(4,1)
> ...
> (H1,M1)=(3,4)    =>    U5= ... ( complete aqui)
> 
> Agora consideramos o caso em que H+M = 6. Seguira um montao de
> calculos. Depois consideramos o caso em que H+M=5 e assim
> sucessicamente. No final calculamos o somatorio de todos os Ui
> 
> 2) NO MAXIMO 10 PESSOAS SAO PHD EM MATEMATICA
> 
> (H2,M2)=(10,0)  => V1=BINOM(37,10)*BINOM(26,10)
> (H2,M2)=(9,1)    => V2=BINOM(21,1)*BINOM(32,9)*BINOM(21,1)*BINOM(26,9)
> ... (complete aqui)
> 
> e aqui fazemos um raciocinio absolutamente semelhante ao caso acima.
> No final calculamos o somatorio de todos os Vi
> 
> A unica pergunta não obvia e a seguinte : quantas comissoes existem
> tais que, simultaneamente, existam no maximo 7 pessoas fluentes em
> frances e no maximo 10 pessoas com Ph"D" em Matematica ? Se existe
> alguma inteligencia neste problema ela esta aqui. O resto que vimos
> acima e trivial e truculento.
> 
> Se a resposta a pergunta e "nao", entao a resposta ao nosso problema e :
> 
> R = T – somatorio Ui  -  somatorio Vi
> 
> Se a resposta for "sim", seja W o total de comissoes nesta condicoes.
> Entao a resposta ao nosso problema e :
> 
> R = T – somatorio Ui  -  somatorio Vi + W
> 
> Eu afirmo que a resposta e "nao". Para ver isso claramente, consideremos :
> 
> A -> homens que so dominam matematica
> B->homens que so dominam frances
> C-> homens que dominam frances e matematica
> 
> D->mulheres que so dominam frances
> E->mulheres que so dominam matematica
> F-> mulheres que dominam frances e matematica.
> 
> Queremos solucoes que :
> 
> A+B+C =10
> D+E+F=10
> B+C+D+F =< 7   ( no maximo 7 pessoas dominam frances )
> A+C+E+F =< 10 ( no maximo 10 ph"D" em matematica )
> 
> somando as duas ultimas equacoes ( e considerando o valor das duas 
> primeiras ) :
> 
> 20 + C + F =< 17 ... ABSURDO ! Pois C >=0 e F >= 0
> 
> Assim, a resposta ao nosso problema e :
> 
> R = T – somatorio Ui  -  somatorio Vi
> 
> FIM DO SEGUNDO ESBOCO
> 
> A todos, com os melhores
> votos de paz profunda, sou
> Paulo Santa Rita
> 2,1604,090707
> 
> 
> Em 09/07/07, Paulo Santa Rita<paulo.santarita@gmail.com> escreveu:
> >Ola Artur e demais colegas
> >desta lista ... OBM-L,
> >
> >O primeiro problema ( das comissoes com 10 homens e 10 mulheres ) me
> >parece impossivel por combinatoria ou por qualquer outro metodo
> >simplesmente porque e inconsistente : 21 +  25 + 12 = 57 > 53 ... O
> >mesmo para as mulheres ! Se nao fosse essa limitacao e facil fazer por
> >combinatoria.
> >
> >Quanto ao segundo, e trivial. Vou apenas esbocar a solucao. Por favor,
> >complete os detalhes :
> >
> >X1, X2, ..., X365 sao os dias do ano. As solucoes inteiras nao negativas de
> >
> >X1 + X2 + ... + X365 = 200
> >
> >podem ser vistas como as imagens da funcao f que voce cita. Assim, a
> >titulo de exemplo, a solucao (200,0,0,...,0) significa que todas as
> >pessoas fizeram aniversario no primeiro dia do ano. O numero de
> >solucoes inteiras e nao-negativas da equacao acima e bem conhecido.
> >
> >Fixando-se, a titulo de exemplificacao, na variavel X1, precisamos
> >determinar em quantas solucoes ela tem o valor maximo . Assim :
> >
> >Formato : (200,0,0,...,0) -> 1 solucao
> >Formato : (199,1,0,...,0) -> 364 solucoes
> >formato : (198,1,1,0,...,0) -> binom(264,2) -> solucoes
> >
> >Agora e so ir decendo ate 100, pois e impossivel algu outro dia ter
> >mais que 100 aniversariantes dado que ha somente 200 pessoas.
> >
> >ABAIXO DE 100 :
> >
> >Solucoes com 99 na posicao 1 mas que ocupam 3 lugares, tipo
> >(99,99,2,...,0) tambem satirsfazem as condicoes impostas. Isso da um
> >total de binom(364,2), solucoes som 99 na posicao 1 e que ocupam 4
> >lugares, tipo (99,98,1,1,0,0,...,0) tambem satisfazem e assim
> >sucessivamente.
> >
> >Fixado um Numero < 100 basta considerar os casos em que os dias nos
> >quais nao ocorre aniversario impossibilita ocorrer um maximo em outro
> >local diferente do primeiro.
> >
> >Agora retiramos do total de solucoes de X1 + X2 + ...+X365=200 as
> >solucoes que tem maximo em X1 ( na primeira posicao ) isso da a
> >probabilidade para o dia 1. Por simetria, vale para qualquer dia.
> >
> >O primeiro problema tambem e simples, mas trabalhoso. O total de comissoes 
> >e :
> >
> >T = BINOM(53,10)*BINOM(47,10)
> >
> >Agora basta retirar do total acima as comissoes impossiveis, tipo,
> >todas aquelas nas quais no maximo 7 pessoas sao fluentes em frances (
> >facil de calcular ) e assim sucessivamente
> >
> >Um Abracao pra todos
> >Paulo Santa Rita
> >2,1201,090707
> >
> >
> >
> >
> >
> >Em 02/07/07, Artur Costa Steiner<artur.steiner@mme.gov.br> escreveu:
> >> Eu resolvi este problema montando equacoes nas variaveis envolvidas e 
> >recorrendo a um algorimo de programacao inteira. Talvez haja uma solucao 
> >por analise combinatoria, mas me pareceu complicado.
> >>
> >> Numa empresa ha 100 funcionarios, 53 homens, 47 mulheres.  Dentre os 
> >homens, 21 sao fluentes em Frances mas nao sabem Matematica, 25 tem Phd em 
> >matematica mas nao falam Frances e 12 sao fluentes em Frances e tem Phd em 
> >Matematica. Dentre as mulheres, 26 sao fluentes em Frances mas nao sabem 
> >matematica, 17 tem PHD em matematica mas nao falam Frances e 9 sao 
> >fluentes em Frances e tem Phd em matematica.
> >>
> >> O gerente quer formar uma comissao de 20 pessoas com os seguinte 
> >critérios:
> >>
> >> Tem que haver 10 homens e 10 mulheres.
> >> Pelo menos 8 pessoas tem que ser fluentes em Frances.
> >> Pelo menos 11 pessoas tem que ter Phd em matematica.
> >>
> >> Atendendo a tais criterios, quantas comissoes podem ser formadas?
> >>
> >> Artur
> >>
> >> =========================================================================
> >> 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
> >> =========================================================================
> >>
> >
> 
> =========================================================================
> 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
> =========================================================================
=========================================================================
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
=========================================================================