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

["Paulo Santa Rita" <paulo.santarita@xxxxxxxxx>]

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.
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
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.
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 ?

Um AbracaoPaulo Santa Rita3,0F1A,100707








Em 10/07/07, Nicolau C. Saldanha<nicolau@mat.puc-rio.br> escreveu:> 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 negati!
vas 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, c!
om 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> =========================================================================>
=========================================================================
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
=========================================================================