Rastgele altı korsan seçelim. Bu grup sandığı açamadığına göre sandıkta anahtarı bu grupta bulunmayan en az bir kilit vardır.
Gruba ekleyeceğimiz herhangi bir korsanla beraber sandık açılabileceğine göre kalan yedi korsan da bu kilitlerin anahtarlarına sahip olmalıdır.
Bu kilitler başka bir altılı grubun sandığı açmasına engel olacak kilitler olamaz. Bunun ispatını şöyle yapabiliriz:
Eğer bir kilit iki grubun da ayrı ayrı sandığı açabilmelerini engelliyorsa bu grupların birleşimlerini de engellemeli. Yani eğer iki grupta da bu kilidi açacak anahtar yoksa, bu grupların birleşiminde de bu anahtar eksik olacaktır. Birbirinden farklı iki altı korsan grubu toplamda en az yedi korsandan oluşmalıdır. Soruya göre yedi korsandan oluşan herhangi bir grup sandığı açabilmektedir. Demek ki bir kilit sadece bir altılı grubu engellemektedir.
Bu gözlemlerden şu sonuçları çıkarabiliriz:
Her farklı altılı korsan grubu için bir kilit kullanılmalıdır. Daha fazla kilit kullanımı sadece kullanılan kilit sayısını arttırır. Bizden en az kilit adedi istendiğine göre bir kilit kullanmak en iyi çözümü verecektir. Bu kilidin anahtarları da kalan yedi korsana verilecektir. Yani çilingir her yedi korsan için bir kilit takar ve bu kilidin anahtarlarını bu yedi korsana dağıtır. Toplamda $\binom {13}{7} = 1716$ adet kilit ve $7 \cdot \binom {13}{7} = 12012$ anahtar gerekecektir.
Not: Dikkat edilirse altılı korsan grupları ile yedili korsan grupları eşit sayıdadır, yani $\binom {13}{6} = \binom {13}{7} = 1716$.
Hiç yorum yok:
Yorum Gönder