KombinatorykaWyzwanieZadanie nr 3871

Największa rodzina parami przecinających się 4-elementowych podzbiorów zbioru {1, …, 12}

Rodziny zbiorów Zadania konkursoweZadania olimpijskie

Rodzina \(\mathcal F\) składa się z czteroelementowych podzbiorów zbioru \(\{1,2,\ldots,12\}\), przy czym każde dwa zbiory z \(\mathcal F\) mają co najmniej jeden wspólny element. Ile co najwyżej zbiorów może liczyć rodzina \(\mathcal F\)?

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Ustaw liczby 1, …, 12 na okręgu w dowolnej kolejności i policz, ile zbiorów rodziny może być „łukami” (czwórkami kolejnych liczb) tego ustawienia.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Przykład: wszystkie czteroelementowe zbiory zawierające \(1\) — jest ich \(\binom{11}{3}=165\) i każde dwa mają wspólny element \(1\).
  2. Lemat: jeśli \(12\) liczb ustawimy na okręgu, to co najwyżej \(4\) łuki (zbiory czterech kolejnych liczb) mogą parami się przecinać. Ustalmy taki łuk \(L\); każdy inny przecinający go łuk zaczyna się lub kończy wewnątrz \(L\), czyli „przecina” jedno z \(3\) miejsc między kolejnymi elementami \(L\). Dla każdego miejsca łuk kończący się tuż przed nim i łuk zaczynający się tuż za nim są rozłączne (bo \(12\ge2\cdot4\)), więc z każdego miejsca korzysta co najwyżej jeden łuk rodziny. Razem z \(L\): co najwyżej \(1+3=4\).
  3. Zliczamy pary (ustawienie cykliczne \(\sigma\), zbiór \(A\in\mathcal F\) będący łukiem \(\sigma\)). Ustawień cyklicznych jest \(11!\), a w każdym co najwyżej \(4\) łuki należą do \(\mathcal F\): par jest co najwyżej \(4\cdot11!\).
  4. Z drugiej strony ustalony zbiór \(A\) jest łukiem w dokładnie \(4!\cdot8!\) ustawieniach cyklicznych (układamy \(A\) w blok i resztę). Zatem \(|\mathcal F|\cdot4!\cdot8!\le4\cdot11!\), czyli \(|\mathcal F|\le\frac{4\cdot11!}{4!\cdot8!}=165\).
  5. Odpowiedź: \(165\).

Odpowiedź: \(165\)

Czego warto się nauczyć?

Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.

Więcej zadań z kombinatoryki →

Podobne zadania