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?

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 5-de- 9).

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 4 em um conjunto de 9 é
binom94 = 9cdot8cdot7cdot64cdot3cdot2cdot1 = 126
Logo, precisamos de 126 cadeados.

Passo 3

Cada cadeado associado a um subconjunto S de quatro cientistas deve ter suas chaves distribuídas a todos os cientistas que não estão em S. 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? É
binom84 = 8cdot7cdot6cdot54cdot3cdot2cdot1 = 70
Portanto, cada cientista fica com 70 chaves.

Resposta

(a) 126\n
(b) 70

Exercícios de Livros Relacionados