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<[EMAIL PROTECTED]> 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<[EMAIL PROTECTED]> 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 =========================================================================
