13 Piratów i skarb

[cardemon]

13 Piratów chciało bezpiecznie schować zagrabiony skarb. Zdecydowali
wspólnie, że skarb będzie zamknięty i niedostępny dla nikogo, jeśli
mniejszość spośród nich będzie chcieć się do niego dobrać. Jednym słowem
zdecydowali, że musi być zgoda większości, by móc otworzyć skrytkę. Żaden z
piratów nie ufał innemu. Postanowili więc, że udadzą się do ślusarza, by ten
dorobił odpowiednią ilość kłódek i kluczy zamykających skrzynię ze skarbem w
taki sposób, że aby otworzyć skrzynię trzeba było wpierw zdjąć wszystkie
kłódki. Ślusarz spełnił żądania piratów i zrobił odpowiednią ilość kłódek i
kluczy. Każda kłódka mogła być otwarta przez więcej niż jeden klucz, ale
każdy klucz mógł otworzyć tylko jedną kłódkę. Ile ślusarz zrobił kłódek
zakładając, że wykonał ich najmniejszą potrzebną ilość?

Życzę powodzenia z tą zagadką, ale zastrzegam, że jest ona trudna.

CdM

[reptar]

Pierwsza mysl, chyba zresztą dosc banalna, to ze ponizej siedmiu klodek zejsc sie nie da.

[reptar]

Czy to będzie liczba kombinacji siedmioelementowych
ze zbioru trzynastoelementowego?

[marchewa4]

reptar napisał:

> Czy to będzie liczba kombinacji siedmioelementowych
> ze zbioru trzynastoelementowego?

Tyle klodek na pewno wystarczy i wydaje mi sie dodatkowo, ze jest to minimalna
liczba.

Proba nieformalnego dowodu:
Wezmy 6 piratow P1 = {a1, b1, c1, d1, e1, f1}. Nie moga oni otworzyc skrzyni,
zatem musi im brakowac co najmniej jednego klucza (niech bedzie to klucz do
klodki k). Wszyscy pozostali piraci musza ten klucz miec, zeby kazda siodemka
{a1, b1, c1, d1, e1, f1, x} mogla skrzynie otworzyc.
Wezmy teraz inna szostke piratow (inna, tzn. co najmniej jeden z nich jest
inny): P2 = {a2, b2, c2, d2, e2, f2}. Im tez musi brakowac co najmniej jedego
klucza. Nie moze to byc k, bo zbior (P1 + P2) liczy co najmniej 7 piratow i
musza oni miec klucze do wszystkich klodek.
Kazdej szostce piratow musi brakowac co najmniej jednego klucza i dla kazdej
szostki musi to byc inny klucz (wynika to z powyzszego rozumowania). Zatem
wszystkich kluczy musi byc co najmniej tyle, ile 6-elementowych podzbiorow
zbioru 13-elementowego. Ze to wystarczy wynika wprost z powyzszego rozumowania,
ktore pokazuje jak te klucze dzielic miedzy piratow.

Pozdrowienia

M.

[Gość: andy._]

reptar napisał:

> Pierwsza mysl, chyba zresztą dosc banalna, to ze ponizej siedmiu klodek zejsc
s
> ie nie da.
No nie byłbym taki pewien. Do wyjaśnień rozumowań wygodny jest model kłódek z
wieloma dziurkami na klucz. Jeden klucz może być obrócony w jednej dziurce,
ale trzeba obrócić odpowiednie klucze we wszystkich dziurkach kłódki aby ona
otworzyła się. Wtedy zgadzam się, że poniżej siedmiu dziurek zejść się nie da.

Pozdr. A.

[reptar]

Jeśli kłódka ma dwie dziurki, to czym to się różni od dwóch kłódek?

[andy._]

reptar napisał:

> Jeśli kłódka ma dwie dziurki, to czym to się różni od dwóch kłódek?
Tym, że jest jedna, a nie dwie. Przecież minimalizujemy liczbę kłódek.
Pozdr. A.

[reptar]

Bardzo pomysłowe, ale chyba nie o to chodzi, bo wtedy wystarczy JEDNA kłódka
z odpowiednio skonstruowanym systemem logicznym w środku.

[andy._]

reptar napisał:

> Bardzo pomysłowe, ale chyba nie o to chodzi, bo wtedy wystarczy JEDNA kłódka
> z odpowiednio skonstruowanym systemem logicznym w środku.
Oczywiście nie to było moją intencją. Chodziło mi tylko o obrazowe oddanie
zdania Cardemona "Każda kłódka mogła być otwarta przez więcej niż jeden klucz,
ale każdy klucz mógł otworzyć tylko jedną kłódkę". Może to być zrealizowane
przez odpowiedni system zapadek wewnątrz kłódki - i to jest ten system logiczny
w środku - albo poprzez moje zobrazowanie: każdy klucz ma swoją dziurkę w
kłódce, którą otwiera.
Pozdr. A.

[reptar]

andy._ napisał:

> Oczywiście nie to było moją intencją. Chodziło mi tylko o obrazowe oddanie
> zdania Cardemona "Każda kłódka mogła być otwarta przez więcej niż jeden klucz,


Pewnie, że rozumiem, że nie to było Twoją intencją. Sam dałem się złapać w tę
samą pułapkę proponując (co jest nieco niżej) rozważenie możliwości, że z dwóch
kluczy da się zmontować trzeci - wtedy również, przy odpowiednim skomplikowaniu
montażu na poziomie kluczy, wystarczyłaby jedna kłódka   ;-)

Ale wciąż nie daje mi spokoju koncepcja wielu skrzynek jedna w drugiej...

[reptar]

> Sam dałem się złapać w tę samą pułapkę proponując (co jest nieco niżej)


Kurcze, już sam nie wiem. To chyba nie ta sama pułapka.
Twój pomysł przynajmniej był zgodny z brzmieniem zagadki,
mój zaś (z tym kombinowaniem z kluczami) - nie.

[the_ladybird]

1716 :)

[the_ladybird]

aha, spóźniłam się :)
gratulacje dla Marchewy :)

Cardemon zastrzegł, że zadanie jest trudne, więc

[reptar]

zastanawiam się, jak wpłynęłaby na rozwiązanie możliwość ustawienia kłódek
w jakiejś kolejności, np. otwieramy pierwszą skrzynkę zabezpieczoną X kłódkami,
w środku znajdujemy drugą zabezpieczoną Y kłódkami, itd.

Albo inaczej: czy z dwóch kluczy można zmontować trzeci?

To na razie tylko luźne pomysły na skomplikowanie problemu ;-)

[the_ladybird]

ups. To Tobie należą się gratulecje. nie dość że spóźniona to jeszcze gapa :)

[reptar]

Mam taki pomysł, może ktoś go pociągnie.

Liczba kombinacji 7-elementowych ze zbioru 13-elementowego to jest wtedy, kiedy
do wnętrza prowadzi tyle dróg, każda zabezpieczona siedmioma kłódkami.


A zatem dla kombinacji:
{1,2,3,4,5,6,7}
{2,3,4,5,6,7,8}
{3,4,5,6,7,8,9}
{4,5,6,7,8,9,10}
{5,6,7,8,9,10,11}
{6,7,8,9,10,11,12}
{7,8,9,10,11,12,13} potrzebowalibyśmy 49 kłódek.


Ale można by tę liczbę zmniejszyć, konstruując taki mechanizm:

Na obwodzie koła rozmieszczamy w stałej odległości kłódki (wszystkich jest N,
a więc co 360 stopni podzielone przez N). Pod nimi jest ruchoma sztaba - jej
wyjęcie umożliwia dostanie się do wnętrza, a wyjąć ją można tylko wtedy, kiedy
siedem kolejnych kłódek znajdujących się nad nią da się otworzyć. Sztabę można
przesunąć pod siedem dowolnych, ale kolejnych kłódek. Sześciu piratów za
cholerę nie da rady.

Jeśli w tym ciągu kłódek znajdzie się fragment 1,2,3,4,5,6,7,8,9,10,11,12,13,
to wszystkie wymienione poprzednio kombinacje zamiast czterdziestoma
dziewięcioma obsługujemy trzynastoma kłódkami.

Teraz pytanie: jak długi (a właściwie jak krótki) ciąg zapewni nam to, że każda
kombinacja będzie jego fragmentem.

(Numerami od 1 do 13 oznaczyłem piratów; ileś tam liczb 8 rozmieszczonych na
obwodzie oznacza kłódkę otwieraną kluczem pirata 8; to może być za każdym razem
ten sam klucz, ale to by nie było zgodne z brzmieniem zadania, więc powiedzmy,
że każda 8 oznacza *inny* klucz z pęku pirata oznaczonego ósemką).

[andy._]

Gdyby dopuścić komplikacje mechaniczne (dodatkowe sztaby, specjalne zamki) to
można wyobrazić sobie bardzo proste rozwiązanie: siedem niestabilnych
zatrzasków otwieranych tylko kluczem. Wyjęcie klucza pozostawia zatrzask
zamknięty. Taka konstrukcja wymaga obecności 7-miu piratów. Zakładam, że klucze
są niepodrabialne.
Pozdr. A.

[reptar]

Podcišłe� mi skrzydła, Andy           :-(

A ja wła�nie napisałem co� takiego:

Sprawę można jeszcze bardziej rozbudować, wprowadzajšc wspomniane przez zadaniodawcę kłódki otwierane przez wiele kluczy. Oto przykładowy fragment cišgu, osiem kolejnych kłódek:

A - otwiera tylko pirat nr 1
B - otwierajš piraci 2 i 3
C - otwierajš piraci 4 i 5
D - otwierajš piraci 6 i 7
E - otwierajš piraci 8 i 9
F - otwierajš piraci 10 i 11
G - otwierajš piraci 12 i 13
H - otwiera tylko pirat nr 1

Takiego zestawu na pewno nie otworzy sze�ciu piratów, a aż 64 siódemki sobie z nim poradzš.

Ale chyba dobrze by było, jakby�my się dowiedzieli, jak daleko możemy się posunšć w takich kombinacjach mechanicznych. W końcu cudna liczba 1716 też nie daje rozwišzania polegajšcego na otwarciu *wszystkich* kłódek.

[andy._]

reptar napisał:

> Podcišłe� mi skrzydła, Andy           :-(

Absolutnie nie! Wszystkie pomysły mogą prowadzić do nowych, ciekawych rozwiązań
albo mutacji zagadki. Założenia zawsze mozna podretuszować i wygenerować nowa
wersję.

> ...W końcu cudna liczba 1716 ...
No właśnie! Podane zostały dwa dwa rozwiązania: 6 z 13 i 7 z 13. Oba dają ten
sam wynik liczbowy - 1716. A które jest słuszne? A może oba?

Pozdr. A.

[Gość: puciapucia]

Gdyby slusarz znal sie na kombinacjach i systemach logicznych to napewno zrobil
by te 49 lub 1716 klodek. Ja zakladam, ze raczej poszedl po slusarski rozum do
glowy i zobil 13 klodek, kazda z jednym kluczem. Kazdy pirat dostal klucz do
jednej klodki. Natomiast slusarz pomyslal nad skoblem. Dlugosc raczki skobla
dolnego i gornego zrobil dokladnie taka ze miescilo sie 13 klodek. Skoble nie
tworzyly zamknietego kola i kazdy byl uciety na jednym koncu (gorny z
prawej ,dolny z lewej) na dlugosci trzech klodek, czyli zachodzily na siebie na
dlugosci siedmiu klodek. Zdjecie ktorejkolwiek z klodek pozwalalo przesunac
klodki, ale dopiero siodma pozwalala przesunac szesc pozostalych na pojedyncze
czesci skobli i otworzyc skrzynie.
W imieniu slusarza przepraszam za tak przyziemne rozwiazanie.

[Gość: johndoe]

witam!
i pozdrawiam intelektualny kwiat narodu:)
zalozmy ze 6 piratow otworzy wszystkie klodki oprocz jednej /jest to najprostsze zalozenie/. to jedna otworzy kazdy z pozostalej siodemki.
czyli musi istniec x klodek, ktore sa otwierane przez jednego z siedmiu dowolnych piratow. pomijajac srodkowy tok rozumowania :) wychodzi na to, ze klodek musi byc 13 po 7 /to taki wzorek na kombinacje 7 z 13/.
jak by nie bylo 1716 jak w pysk strzelil.
Marchewa juz to rozwiazanie podeal i jemu czesc i chwala.
ale zastanowmy sie nad rozwiazaniem praktycznym.
jak skonstruowac zamkniecie takiej skryni, zeby rozwiazanie bylo maksymalnie proste, o koszt klodek, zamkow czy skobli nie przekroczyl wartosci skarbu.
pzdr

[cardemon]

Oczywiście liczba 1716 (13 nad 7 symbol Newtona) jest jak najbardziej słuszna i
na dzień dzisiejszy powinna być uważana za prawidłowe rozwiązanie zagadki. Ale
po pierwsze - sam nie jestem autorem tej zagadki, więc nie znam autorskiego
rozwiązania, a po drugie - mnie też liczba 1716 wydała się zbyt duża.
Oczywiście możliwe jest, że ślusarz skonstruował bardzo sprytny mechanizm i
skarb zamknięty został np. siedmioma kłódkami, ale nie o takie rozwiązanie tu
chodzi.
Powiem szczerze, ze przez długi czas zastanawiałem się nad kłódką szyfrową, do
otworzenia której potrzeba kodu n-cyfrowego. Pomyślałem sobie, że każdemu
piratowi ślusarz przekazał klucz w postaci jakiejś liczby. Dowolne siedem liczb
z tych trzynastu odpowiednio przetworzone da właśnie tę otwierającą kombinację.
Niestety w tym momencie się poddaję, bo nie potrafię ani obronić tej koncepcji,
ani jej obalić.