szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 20 wrz 2016, o 16:22 
Użytkownik

Posty: 1
Lokalizacja: RPA
Jaka jest metoda, aby wskazać minimalną ilość podzbiorów k - elementowych ze zbioru n - elementowego, które zawierają w sobie wszystkie podzbiory l - elementowe ze zbioru n - elementowego, gdzie n>k>l.

Przykład zadania.
Magik wybiera 2 spośród 6 kart - karty są rozróżnialne, określmy zbiór kart następująco \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 2 karty.
W tym przypadku wybieramy podzbiory 2-el ze zbioru 6-el, wiec
{6 \choose 2} = 15
Odp. Minimalna ilość kartek wynosi 15.

b) Na kartce można wskazać 3 karty

Tu mam problem ze wskazaniem minimum.
W tym przypadku poprawną odpowiedzią będzie chyba 7. Grupowałam podzbiory z podpunktu (a) w "trójki", gdzie każdy podzbiór z (a) należał do innego podzbioru 3-el ze zbioru \left\{ 1,2,3,4,5,6\right\}. np. (12,13,23) - "trójką" - 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ą 2-el podzbiory, których nie pogrupujemy w powyższy sposób. W tym przypadku będą to 4 - "trójki" i pozostaną 3 różne "dwójki".
Gdybyśmy zmienili w zadaniu jedynie zbiór kart na 7-el, to powstałoby nam 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.
Góra
Mężczyzna Offline
PostNapisane: 20 wrz 2016, o 22:32 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Dla l = 2 można przedstawić ten problem w teorii grafów: elementy to wierzchołki, krawędzie to pary elementów. Mamy klikę 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ę 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:
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 3 to 6.
Nie może ona być \le5, bo wtedy liczba pokrywanych par wynosiłaby 5 \cdot 3=15 i liczba wszystkich par to 15, ale pewna para musi być pokryta dwa razy, chociażby dlatego, że liczba trójek zawierających 1 musi wynosić przynajmniej 3, więc jakaś para się powtórzy.
Tak więc jest ona \ge6. Te zbiory to:
\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\}
Góra
Kobieta Offline
PostNapisane: 21 wrz 2016, o 13:33 
Użytkownik
Avatar użytkownika

Posty: 4416
Lokalizacja: Łódź
Mruczek napisał(a):
Te zbiory to:
\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 6 zbiorów to:
\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 n=6 kart i dla kilku wariantów l kart wylosowanych przez magika oraz dla kilku wariantów k kart zapisywanych na kartce i wyszło mi coś takiego:

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

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

\left\lceil   \ \right\rceil oznacza sufit liczby.
Może to tylko przypadek ...
Góra
Mężczyzna Offline
PostNapisane: 22 wrz 2016, o 11:50 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
kropka+ napisał(a):
Te zbiory nie są wyznaczone jednoznacznie. Np. inne 6 zbiorów to:
\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 6. Oczywiście można także przenumerować elementy zbiorów, np. zamienić wszędzie 1 z 2 albo 5 z 6 i wtedy też dostaniemy "inne" sześć zbiorów.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Zasada podwójnego przeliczania] Uzasadnienie mocy zbioru  pelas_91  1
 oszacowac moc zbioru  kriegor  9
 Wyznaczyć ilość wszystkich permutacji zbioru ...  Dobrochoczy  2
 rekurencyjny podział zbioru..  kamzeso  1
 Element największy zbioru (Twierdzenie Ore)  lgtco99  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl