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

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

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
=========================================================================