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

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

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