KombinatorykaWyzwanieZadanie nr 3844

Pary z 20-elementowego zbioru liczb o średniej nie mniejszej niż średnia całego zbioru

Zliczanie podwójne i rozbicia na pary Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

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\))?

+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ę

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
  1. 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.
  2. 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.
  3. Ż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\)).
  4. 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\).
  5. 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.

Więcej zadań z kombinatoryki →

Podobne zadania