Sejf

[Gość: grzesiek]

To raczej pytanie niż zagadka, bo sam nie znam odpowiedzi. Problem
pochodzi z turnieju puzzleup, ale czas na odpowiedź już minął więc
wpuszczam go w Forum (a właściwie swoją redakcję tego problemu).

Jest jeden sejf i N ludzi mających do niego dostęp. Sejf jest zamknięty
na Z zamków. Klucze do zamków są tak rozdzielone między ludzi że
dowolna grupa M ludzi może otworzyć sejf. Mając N i M należy znaleść Z
oraz sposób podziału kluczy (możliwe są kopie kluczy).

Kilka prostych scenariuszy narzuca się od razu:
1) Z=1, każdy człowiek ma do niego klucz ---> M=1
2) Z=N, każdy człowiek ma klucz do innego zamka ---> M=N
3) Z=N, każdy człowiek ma Z-1 kluczy, każdemu brakuje klucza do innego
zamka ---> M=2

Sęk w tym że nie potrafię znaleść żadnego innego scenariusza, t.zn. dla
M innego niż 1,2 lub N.

Kto pomoże?

[Gość: Uważny]

Masz przykład dla 5 osób z których każda trojka ma mieć dostęp o kasy. Kasa
musi mieć wtedy 10 zamków (Tyle jest różnych dwójek wśród tej piątki) Idea
rozdziału kluczy jest następująca: każda dwójka musi nie mieć przynamniej
jednego klucza, który musza mieć pozostali. Widać to w tabeli
1 2 3 4 5 6 7 8 9 10 klucze
osoby
1 o o o o + + + + + +
2 o + + + o o o + + +
3 + o + + o + + o o +
4 + + o + + o + o + o
5 + + + o + + o + o o

o - brak klucza, + klucz przyfzielony. Kazda trójka dysponuje pełnym kompletem
kluczy, a dwójka - nie.Kazdy ma 6 roznych kluczy
Ogólnie - liczba zamkow w kasie jest liczbą kombinacji M-1 elementowych w
zbiorze M elementowym. Liczba kluczy dla jednego też z kombinatoryki.
Tabelka robiona w wordzie nie przeniosła się dokładnie.Pozdrawiam!

[Gość: Uważny]

Oczywiście w zbiorze N elementowym. Wiersz z numerami kluczy przesunął się
nazbyt w lewo.

[Gość: grzesiek]

Dziękuję!

[Gość: Uważny]

Jestes jednym z nielicznych, którzy dziękują za radę. Byłaby obszeniejsza,
gdyby działał tu - jak w mailu - edytor równań. Wielkości N,M,Z są ze soba
ścisle związane, jak rownież liczba kluczy dla kazdego. Sam ich rozdział jest
dosyc skomplikowany, szczególnie kiedy N jest bliskie M/2 i inaczej niż
tabelowo nie umiem go przeprowadzić, ale idea jest taka, jak przedstawiłem.

[bbaju]

Grzesiek, zapomniałeś dodać, że zamków i rozdzielonych kluczy ma dla danego M i
M być minimalna liczba.
Dla N=5 wystarczą 3 zamki, każdy dostaje po dwa klucze (12, 13, 23, 12, 13) i
wtedy kazda trojka ma już dostęp do kasy.

Pozd.
Baju

[pam75]

bbaju napisała:

>
> Dla N=5 wystarczą 3 zamki, każdy dostaje po dwa klucze (12, 13, 23, 12, 13) i
> wtedy kazda trojka ma już dostęp do kasy.
Dowdcipnie, tylko i dwóJi maja dostęp, a nie powinny. (12)(23) lub (12)(13)
plądruja sejf, choc nie kazda para ma to szczęscie.
Projekt uważnego jest optymalny przy postawionych warunkach.