Nove cientistas trabalham num projeto sigiloso. Por questões de segurança, os planos são guardados em um cofre protegido por muitos cadeados de modo que só é possível abri-los todos se houver pelo menos 5 cientistas presentes.
a) Qual é o número mínimo possível de cadeados?
b) Na situação do item a), quantas chaves cada cientista deve ter?
a) Qual é o número mínimo possível de cadeados?
b) Na situação do item a), quantas chaves cada cientista deve ter?
Passo 1
O enunciado diz que há nove cientistas e queremos um esquema de cadeados e chaves de modo que qualquer grupo de pelo menos cinco cientistas consiga abrir todos os cadeados, mas qualquer grupo de até quatro não consiga. Este problema é tratado com combinatória aplicada a sistemas de segurança “m-of-n” (aqui
-de-
).
Passo 2
Para impedir que um grupo de quatro cientistas abra o cofre, precisamos garantir que para cada subconjunto de quatro exista pelo menos um cadeado cujas chaves não estejam com nenhum deles. A forma mais econômica é criar exatamente um cadeado para cada subconjunto de quatro cientistas.
O número de subconjuntos de tamanho em um conjunto de
é
O número de subconjuntos de tamanho
Logo, precisamos de
cadeados.
Passo 3
Cada cadeado associado a um subconjunto
de quatro cientistas deve ter suas chaves distribuídas a todos os cientistas que não estão em
. Assim, um cientista qualquer recebe as chaves de todos os cadeados cujos subconjuntos de quatro não o incluem.
Para um cientista fixo, quantos subconjuntos de quatro escolhemos entre os outros oito? É
Para um cientista fixo, quantos subconjuntos de quatro escolhemos entre os outros oito? É
Portanto, cada cientista fica com
chaves.
Resposta
(a)
\n
(b)
(b)