KombinatorykaWyzwanieZadanie nr 3871
Największa rodzina parami przecinających się 4-elementowych podzbiorów zbioru {1, …, 12}
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\)?
Świetnie.
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
- Przykład: wszystkie czteroelementowe zbiory zawierające \(1\) — jest ich \(\binom{11}{3}=165\) i każde dwa mają wspólny element \(1\).
- 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\).
- 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!\).
- 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\).
- Odpowiedź: \(165\).
Odpowiedź: \(165\)
Czego warto się nauczyć?
Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.
Podobne zadania
- Permutacje liczb od 1 do 8 o naprzemiennie rosnących i malejących wyrazach
- Liczby od 1 do 11 na okręgu i iloczyny liczb stojących co drugie miejsce
- Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i
- Pary z 20-elementowego zbioru liczb o średniej nie mniejszej niż średnia całego zbioru