Úloha 4.u4: Trezor (3 b)

Zadáno v čísle 23.4.

Řešeno v čísle 23.6.

Zadání

Jedenáctičlenné sdružení místních myslivců má v trezoru uložené tajné materiály. Chtějí trezor opatřit zámky tak, aby jej libovolná šestice dokázala otevřít a zároveň žádná pětice otevřít nedokázala. Kolika nejméně zámky je potřeba trezor opatřit a kolika klíči vybavit každého člena sdružení tak, aby se jim to podařilo? (Každý myslivec může mít více klíčů a zároveň od jednoho zámku může mít klíč více myslivců. Zároveň každý klíč otvírá právě jeden zámek.)

Řešení

Ze zadání platí, že pro každou pětici musí existovat alespoň jeden zámek, k němuž nemá klíč. Zároveň k tomuto zámku musí mít klíč všichni zbývající, protože když k této pětici jednoho z nich přidáme, tak už musí trezor otevřít. Navíc každým dvěma různým pěticím musí chybět klíč k jinému zámku, jinak by ani obě dohromady (a protože jsou různé, tak je to alespoň šest lidí) nedokázaly trezor otevřít. Proto je tedy minimální počet zámků roven počtu různých pětic, což je ${11 \choose 5}=462$.

Nyní ukážeme, proč to stačí a kolik klíčů bude mít každá osoba. Víme, že každá pětice má alespoň jeden zámek, který neotevře, a který otevře každý zbývající člověk. To je to samé jako tvrzení, že každá šestice má zámek, který nikdo ze zbývajících neotevře. To znamená, že ke každému zámku má klíč alespoň šest lidí, takže v každé šestici bude pro každý zámek existovat někdo, kdo od něj má klíč. Takže je vidět, že 462 zámků nám stačí a každý člověk bude mít tolik klíčů, v kolika je šesticích, což spočítáme tak, že vybereme jeho (to lze jedním způsobem), a pak vybereme zbylých pět lidí (to lze ${10 \choose 5}$ způsoby), což je 252.

V této úloze jste téměř všichni, kteří jste si přečetli celé zadání, uspěli. Pouze se u několika z vás stalo, že se vám v řešení pletly pojmy „zámek“ a „klíč“, což ho občas znepřehlednilo a občas dokonce spletlo i vás. Vyplatí se proto dávat si na takové věci pozor.

Petr