KombinatorykaWyzwanieZadanie nr 3844
Pary z 20-elementowego zbioru liczb o średniej nie mniejszej niż średnia całego zbioru
Dany jest zbiór \(X\) złożony z \(20\) różnych liczb rzeczywistych. Dwuelementowy podzbiór \(\{u,v\}\subset X\) nazwiemy dobrym, jeśli średnia arytmetyczna liczb \(u\) i \(v\) jest nie mniejsza niż średnia arytmetyczna wszystkich liczb zbioru \(X\). Jaka jest najmniejsza możliwa liczba dobrych podzbiorów (po wszystkich wyborach zbioru \(X\))?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Przesuń wszystkie liczby tak, by ich średnia była zerem. Rozbij zbiór na 10 rozłącznych par na kilka sposobów tak, aby żadna para nie powtórzyła się w dwóch rozbiciach.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Odejmując od wszystkich liczb ich średnią, możemy założyć, że suma liczb z \(X\) jest równa \(0\); para jest dobra wtedy i tylko wtedy, gdy suma jej elementów jest nieujemna.
- Ponumerujmy elementy \(X\) symbolami \(\infty,0,1,\ldots,18\) (liczby traktujemy modulo \(19\)). Dla \(i\in\{0,\ldots,18\}\) niech \(M_i\) składa się z pary \(\{\infty,i\}\) oraz par \(\{i-j,\,i+j\}\) dla \(j=1,\ldots,9\). Każde \(M_i\) to podział \(X\) na \(10\) rozłącznych par.
- Żadna para nie występuje w dwóch podziałach: para \(\{\infty,a\}\) leży tylko w \(M_a\), a para \(\{a,b\}\) tylko w \(M_i\) z \(2i\equiv a+b\pmod{19}\) (takie \(i\) jest jedno, bo \(2\) jest odwracalne modulo \(19\)).
- W każdym \(M_i\) suma sum dziesięciu par wynosi \(0\), więc co najmniej jedna para ma sumę nieujemną. Otrzymujemy \(19\) różnych dobrych par, zatem dobrych podzbiorów jest zawsze co najmniej \(19\).
- Przykład z dokładnie \(19\): \(X=\{1000,1,2,\ldots,19\}\). Średnia wynosi \(\frac{1190}{20}=59{,}5\); pary zawierające \(1000\) są dobre (jest ich \(19\)), a każda para liczb z \(\{1,\ldots,19\}\) ma średnią co najwyżej \(18{,}5\). Odpowiedź: \(19\).
Odpowiedź: \(19\)
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
- Największa rodzina parami przecinających się 4-elementowych podzbiorów zbioru {1, …, 12}
- Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i