Onze 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á
cientistas e que os planos só podem ser abertos se houver pelo menos
cientistas presentes.
Pede-se:
Pede-se:
- (item a) o número mínimo possível de cadeados que garante que qualquer conjunto de
(ou mais) cientistas consegue abrir o cofre, mas nenhum conjunto de até consegue; - (item b) na situação de número mínimo de cadeados do item (a), quantas chaves cada cientista deve ter.
Informações relevantes: hápessoas, limiar de abertura é , precisamos de um esquema de cadeados/chaves que satisfaça as duas condições (grupos de abrem tudo; grupos de não abrem tudo).
Passo 2
Vamos traduzir a condição para uma linguagem que dá pra contar. Para cada cadeado do cofre, algumas pessoas têm a chave e outras não. Para um cadeado fixo, defina o conjunto
como o conjunto de cientistas que NÃO têm a chave desse cadeado. Observação importante (explicada devagar): se existisse um cadeado cujo conjunto
tivesse
ou mais pessoas, então esse grupo de
pessoas todas não teriam a chave desse cadeado e, portanto, não conseguiriam abrir o cofre — isso violaria a condição de que qualquer grupo de
consiga abrir tudo. Logo, para qualquer cadeado, o conjunto
deve ter tamanho no máximo
. Em outras palavras, cada cadeado pode “bloquear” no máximo
pessoas (essas são as pessoas que não têm sua chave).
Passo 3
Agora pense em qualquer grupo de
pessoas (ou seja, qualquer subset de tamanho
). Essa quadra de cientistas não pode abrir todos os cadeados; portanto, para cada conjunto
de
pessoas deve existir pelo menos um cadeado cujo conjunto
contenha
(ou seja, um cadeado cuja chave não é possuída por nenhuma das pessoas de
). Assim, os conjuntos
associados aos cadeados devem cobrir todos os subconjuntos de tamanho
de um conjunto de
pessoas.
Passo 4
Qual é o número total de subconjuntos de tamanho
em
pessoas? É o binomial
Calculemos:
Passo 5
Cada conjunto
(conjunto de pessoas que NÃO têm a chave de um dado cadeado) tem tamanho
. Quantos subconjuntos de tamanho
estão contidos em um mesmo
?
- Se
, então esse contém zero subconjuntos de tamanho . - Se
, então esse contém exatamente um subconjunto de tamanho (ele próprio).
Portanto, cada cadeado pode “cobrir” no máximo um subconjunto de tamanho. Para cobrir todos os subconjuntos de tamanho é necessário ter pelo menos cadeados. Conclusão parcial: o número mínimo de cadeados é pelo menos .
Passo 6
Mostramos um esquema que atinge esse limite, provando que
é suficiente. Construa um cadeado para cada subconjunto
de
cientistas (há exatamente
tais subconjuntos). Para o cadeado associado a
, entregue a chave a todos os cientistas que não estão em
(ou seja, exatamente aos
cientistas do complemento). Nesse esquema:
- Qualquer grupo de
cientistas: dado um cadeado associado a algum de tamanho , um grupo de não pode estar contido em (pois tem só pessoas). Logo, o grupo de contém pelo menos um cientista do complemento de , isto é, alguém que tem a chave desse cadeado. Como isso vale para todo cadeado, o grupo de tem coletivamente as chaves para abrir todos os cadeados. - Qualquer grupo de
cientistas igual a não tem a chave do cadeado associado a (porque nesse cadeado a chave foi dada a todos que não estão em ). Portanto esse grupo de não abre todos os cadeados.
Assim, o esquema comcadeados funciona, mostrando que o mínimo é exatamente .
Passo 7
Agora contamos quantas chaves cada cientista recebe nesse esquema mínimo. Fixe um cientista qualquer, chame-o de
. Ele recebe a chave de exatamente aqueles cadeados cuja lista
de
pessoas NÃO contém
. Ou seja, o número de cadeados para os quais
tem chave é o número de escolhas de
pessoas dentre as outras
(pois
fica fora do
). Portanto o número de chaves por cientista é
Calculemos:
Verificação alternativa e rápida: há cadeados; cada cadeado tem chaves dadas a
pessoas (os que não pertencem ao
), então o total de cópias de chaves é
. Dividindo uniformemente por
cientistas dá
chaves por cientista.
Verificação alternativa e rápida: há