Re: O problema dos cientistas

[Nicolau Corcao Saldanha <nicolau@xxxxxxxxxxxxxxxxxxx>]

> Nove cientistas trabalham num projeto sigiloso. Por questoes de =
> seguranca, os planos sao guardados em um cofre protegiso por muitos =
> cadeados de modo que so e possivel abri-los todos se houve pelo menos 5 =
> cientistas presentes.
> a)Qual o numero minimo possivel de cadeados
> b)Na situacao do item a), quantas chaves cada cientista deve ter?

Segue a solução do problema. Se você preferir pensar sozinho,
pare de ler aqui.

[]s, N.

               <início do espaço em branco>





































































               <fim do espaço em branco>

Interpreto o enunciado como dizendo que há vários cadeados,
cada um tem uma chave diferente (com muitas cópias),
os cadeados são independentes uns dos outros e
o cofre só é aberto se todos os cadeados forem abertos.

Assim, dados quatro cientistas quaisquer, sempre existe
pelo menos um cadeado para o qual nenhum dos quatro tem
a chave. Por outro lado, qualquer um dos cinco cientistas
restantes deve ter a chave de todos estes cadeados.
Assim, ter mais de um cadeado deste tipo é um desperdício
(as mesmas pessoas teriam as chaves) e podemos supor
que para quatro cientistas quaisquer há exatamente um
cadeado tal que nenhum deles tem a chave.
Também, para conjuntos de quatro cientistas distintos
os cadeados devem ser diferentes, já que os outros cinco
têm a chave. Assim, temos pelo menos um cadeado para
cada conjunto de quatro cientistas (que não têm a chave)
ou, equivalentemente, um cadeado para cada conjunto de
cinco cientistas (que eles e só eles têm a chave).
Ou seja, temos pelo menos binomial(9,4) = 126 cadeados.
Mas esta configuração além de necessária é também suficiente.
Ou seja, a resposta do item (a) é 126.

Para o item (b), note que há 5 cópias de cada chave,
igualmente divididas (no total) entre 9 cientistas.
Assim, cada cientista tem 5*126/9 = 70 chaves.

Mais geralmente, se o número total de cientistas for n
e o número exigido para abrir o cofre for m
o número de cadeados será binomial(n,m-1)
e o número de chaves em poder de cada cientista
(n-m+1)*binomial(n,m-1)/n = binomial(n-1,m-1).