Minimalny podzbiór k-el ze zbioru n-el zawierający w sobie..

[Att]

Jaka jest metoda, aby wskazać minimalną ilość podzbiorów \(\displaystyle{ k}\) - elementowych ze zbioru \(\displaystyle{ n}\) - elementowego, które zawierają w sobie wszystkie podzbiory \(\displaystyle{ l}\) - elementowe ze zbioru \(\displaystyle{ n}\) - elementowego, gdzie \(\displaystyle{ n>k>l}\).

Przykład zadania.
Magik wybiera \(\displaystyle{ 2}\) spośród \(\displaystyle{ 6}\) kart - karty są rozróżnialne, określmy zbiór kart następująco \(\displaystyle{ \left\{ 1,2,3,4,5,6\right\}}\). Widzowie muszą napisać na kartce, jakie karty wybrał magik i wrzucić do urny.
Ile minimalnie kartek musi wrzucić jedna osoba, aby mieć pewność, że wskazała poprawne karty?

a) Na kartce można wskazać tylko \(\displaystyle{ 2}\) karty.
W tym przypadku wybieramy podzbiory \(\displaystyle{ 2}\)-el ze zbioru \(\displaystyle{ 6}\)-el, wiec
\(\displaystyle{ {6 \choose 2} = 15}\)
Odp. Minimalna ilość kartek wynosi \(\displaystyle{ 15}\).

b) Na kartce można wskazać \(\displaystyle{ 3}\) karty

Tu mam problem ze wskazaniem minimum.
W tym przypadku poprawną odpowiedzią będzie chyba \(\displaystyle{ 7.}\) Grupowałam podzbiory z podpunktu (a) w "trójki", gdzie każdy podzbiór z (a) należał do innego podzbioru \(\displaystyle{ 3}\)-el ze zbioru \(\displaystyle{ \left\{ 1,2,3,4,5,6\right\}}\). np. \(\displaystyle{ (12,13,23)}\) - "trójką" - \(\displaystyle{ 123}\).
Wykonując w ten sposób zadanie, w przypadku zbioru, którego moc jest liczbą parzystą, nigdy nie ułożymy "idealnych trójek", zawsze pozostaną \(\displaystyle{ 2}\)-el podzbiory, których nie pogrupujemy w powyższy sposób. W tym przypadku będą to \(\displaystyle{ 4}\) - "trójki" i pozostaną \(\displaystyle{ 3}\) różne "dwójki".
Gdybyśmy zmienili w zadaniu jedynie zbiór kart na \(\displaystyle{ 7}\)-el, to powstałoby nam \(\displaystyle{ 7}\) - "idealnych trójek".
Chociaż ten podział na przypadki liczb parzystych i nieparzystych oraz odejmowanie tych liczb od mocy zbioru mnie przybliża do znalezienia minimum, to w niektórych przypadkach, nie potrafię znaleźć danych "trójek", aby potwierdzić, że sposób ten jest dobry.

Potrzebuję poznać metodę, która umożliwiłby mi odnalezienie takiego minimum dla dowolnych zbiorów.
Dobrze by było, gdyby dało się taki sposób przedstawić/opisać (może i trochę nadrabiając pisaniem) za pomocą kombinacji.

[Mruczek]

Dla \(\displaystyle{ l = 2}\) można przedstawić ten problem w teorii grafów: elementy to wierzchołki, krawędzie to pary elementów. Mamy klikę \(\displaystyle{ n}\)-wierzchołkową i chcemy znaleźć minimalną liczbę trójkątów pokrywających ją (przy czym jedna krawędź może być w wielu trójkątach). Np. w przypadku tego zadania mamy klikę \(\displaystyle{ 6}\)-wierzchołkową i chcemy ją pokryć trójkątami.
Pewnie są jakieś oszacowania, ale dokładnego wzoru raczej nie będzie. Może są jakieś algorytmy, ale to może być NP-trudne. Poszukaj po angielsku w internecie.
Tutaj są jakieś oszacowania:

Kod: Zaznacz cały

https://uwaterloo.ca/combinatorics-and-optimization/sites/ca.combinatorics-and-optimization/files/uploads/files/mike-cavers.pdf

-- 20 września 2016, 22:57 --

Okazuje się, że minimalna liczba zbiorów wielkości \(\displaystyle{ 3}\) to \(\displaystyle{ 6}\).
Nie może ona być \(\displaystyle{ \le5}\), bo wtedy liczba pokrywanych par wynosiłaby \(\displaystyle{ 5 \cdot 3=15}\) i liczba wszystkich par to \(\displaystyle{ 15}\), ale pewna para musi być pokryta dwa razy, chociażby dlatego, że liczba trójek zawierających \(\displaystyle{ 1}\) musi wynosić przynajmniej \(\displaystyle{ 3}\), więc jakaś para się powtórzy.
Tak więc jest ona \(\displaystyle{ \ge6}\). Te zbiory to:
\(\displaystyle{ \left\{ \left\{ 1, 2, 3\right\}, \left\{ 1, 4, 5\right\}, \left\{ 1, 5, 6\right\}, \left\{ 2, 4, 6\right\}, \left\{ 2, 3, 5\right\}, \left\{ 3, 4, 6\right\} \right\}}\)

[kropka+]

Te zbiory to:
\(\displaystyle{ \left\{ \left\{ 1, 2, 3\right\}, \left\{ 1, 4, 5\right\}, \left\{ 1, 5, 6\right\}, \left\{ 2, 4, 6\right\}, \left\{ 2, 3, 5\right\}, \left\{ 3, 4, 6\right\} \right\}}\)

Te zbiory nie są wyznaczone jednoznacznie. Np. inne \(\displaystyle{ 6}\) zbiorów to:
\(\displaystyle{ \left\{ \left\{ 1, 2, 3\right\}, \left\{ 1, 4, 5\right\}, \left\{ 1, 2, 6\right\}, \left\{ 2, 4, 5\right\}, \left\{ 3, 4, 6\right\}, \left\{ 3, 5, 6\right\} \right\}}\)

Sprawdziłam rozwiązania tego zadania dla \(\displaystyle{ n=6}\) kart i dla kilku wariantów \(\displaystyle{ l}\) kart wylosowanych przez magika oraz dla kilku wariantów \(\displaystyle{ k}\) kart zapisywanych na kartce i wyszło mi coś takiego:

\(\displaystyle{ \frac{k}{l} \in N \Rightarrow x= \left\lceil \frac{ {n \choose l} }{ {k \choose l} } \right\rceil}\)

\(\displaystyle{ \frac{k}{l}\notin N \Rightarrow x= \left\lceil \frac{ {n \choose l} }{ {k \choose l} } \right\rceil +1}\)

\(\displaystyle{ \left\lceil \ \right\rceil}\) oznacza sufit liczby.
Może to tylko przypadek ...

[Mruczek]

Te zbiory nie są wyznaczone jednoznacznie. Np. inne \(\displaystyle{ 6}\) zbiorów to:
\(\displaystyle{ \left\{ \left\{ 1, 2, 3\right\}, \left\{ 1, 4, 5\right\}, \left\{ 1, 2, 6\right\}, \left\{ 2, 4, 5\right\}, \left\{ 3, 4, 6\right\}, \left\{ 3, 5, 6\right\} \right\}}\)

To raczej dość oczywiste, że te zbiory nie są wyznaczone jednoznacznie. W zadaniu trzeba było tylko podać jaka jest ich minimalna liczba, a przykład podany przeze mnie (i oszacowanie z dołu) dowodzi, że tą liczbą jest \(\displaystyle{ 6}\). Oczywiście można także przenumerować elementy zbiorów, np. zamienić wszędzie \(\displaystyle{ 1}\) z \(\displaystyle{ 2}\) albo \(\displaystyle{ 5}\) z \(\displaystyle{ 6}\) i wtedy też dostaniemy "inne" sześć zbiorów.