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?

Passo 1

O enunciado diz que há 11 cientistas e que os planos só podem ser abertos se houver pelo menos 5 cientistas presentes.
Pede-se:
  1. (item a) o número mínimo possível de cadeados que garante que qualquer conjunto de 5 (ou mais) cientistas consegue abrir o cofre, mas nenhum conjunto de até 4 consegue;
  2. (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á 11 pessoas, limiar de abertura é 5, precisamos de um esquema de cadeados/chaves que satisfaça as duas condições (grupos de \ge 5 abrem tudo; grupos de \le 4 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 B 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 B tivesse 5 ou mais pessoas, então esse grupo de 5 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 5 consiga abrir tudo. Logo, para qualquer cadeado, o conjunto B deve ter tamanho no máximo 4. Em outras palavras, cada cadeado pode “bloquear” no máximo 4 pessoas (essas são as pessoas que não têm sua chave).

Passo 3

Agora pense em qualquer grupo de 4 pessoas (ou seja, qualquer subset de tamanho 4). Essa quadra de cientistas não pode abrir todos os cadeados; portanto, para cada conjunto S de 4 pessoas deve existir pelo menos um cadeado cujo conjunto B contenha S (ou seja, um cadeado cuja chave não é possuída por nenhuma das pessoas de S). Assim, os conjuntos B associados aos cadeados devem cobrir todos os subconjuntos de tamanho 4 de um conjunto de 11 pessoas.

Passo 4

Qual é o número total de subconjuntos de tamanho 4 em 11 pessoas? É o binomial
\binom{11}{4}.
Calculemos: \binom{11}{4}=\dfrac{11\cdot10\cdot9\cdot8}{4\cdot3\cdot2\cdot1}=330.

Passo 5

Cada conjunto B (conjunto de pessoas que NÃO têm a chave de um dado cadeado) tem tamanho \le 4. Quantos subconjuntos de tamanho 4 estão contidos em um mesmo B?
  • Se |B|<4, então esse B contém zero subconjuntos de tamanho 4.
  • Se |B|=4, então esse B contém exatamente um subconjunto de tamanho 4 (ele próprio).
    Portanto, cada cadeado pode “cobrir” no máximo um subconjunto de tamanho 4. Para cobrir todos os \binom{11}{4}=330 subconjuntos de tamanho 4 é necessário ter pelo menos 330 cadeados. Conclusão parcial: o número mínimo de cadeados é pelo menos 330.

Passo 6

Mostramos um esquema que atinge esse limite, provando que 330 é suficiente. Construa um cadeado para cada subconjunto S de 4 cientistas (há exatamente \binom{11}{4}=330 tais subconjuntos). Para o cadeado associado a S, entregue a chave a todos os cientistas que não estão em S (ou seja, exatamente aos 11-4=7 cientistas do complemento). Nesse esquema:
  • Qualquer grupo de 5 cientistas: dado um cadeado associado a algum S de tamanho 4, um grupo de 5 não pode estar contido em S (pois S tem só 4 pessoas). Logo, o grupo de 5 contém pelo menos um cientista do complemento de S, isto é, alguém que tem a chave desse cadeado. Como isso vale para todo cadeado, o grupo de 5 tem coletivamente as chaves para abrir todos os cadeados.
  • Qualquer grupo de 4 cientistas igual a S não tem a chave do cadeado associado a S (porque nesse cadeado a chave foi dada a todos que não estão em S). Portanto esse grupo de 4 não abre todos os cadeados.
    Assim, o esquema com 330 cadeados funciona, mostrando que o mínimo é exatamente 330.

Passo 7

Agora contamos quantas chaves cada cientista recebe nesse esquema mínimo. Fixe um cientista qualquer, chame-o de x. Ele recebe a chave de exatamente aqueles cadeados cuja lista S de 4 pessoas NÃO contém x. Ou seja, o número de cadeados para os quais x tem chave é o número de escolhas de 4 pessoas dentre as outras 10 (pois x fica fora do S). Portanto o número de chaves por cientista é
\binom{10}{4}.
Calculemos: \binom{10}{4}=\dfrac{10\cdot9\cdot8\cdot7}{4\cdot3\cdot2\cdot1}=210.
Verificação alternativa e rápida: há 330 cadeados; cada cadeado tem chaves dadas a 7 pessoas (os que não pertencem ao S), então o total de cópias de chaves é 330\cdot7=2310. Dividindo uniformemente por 11 cientistas dá 2310/11=210 chaves por cientista.

Resposta

330
210

Exercícios relacionados