Dowód suma liczb

[DonElektron]

Udowodnij że wśród 9 nieujemnych liczb całkowitych, których suma wynosi 90:
a) istnieją 3, których suma wynosi co najmniej 30
b) istnieją 4, których suma wynosi co najmniej 40

[Premislav]

Podpunkt a) to jest oczywista nieprawda, weźmy liczby \(\displaystyle{ 0,1,2,3,4,5,6,7,62}\).
Ponieważ suma wszystkich ośmiu nieprzekraczających \(\displaystyle{ 30}\) jest równa \(\displaystyle{ 28<30}\) i wszystkie są nieujemne, to nie da się wybrać tak trzech, by ich suma wynosiła \(\displaystyle{ 30}\).
Podpunkt b) też na podobnej zasadzie się sypie. Na pewno dobrze przepisane?

[DonElektron]

Na pewno dobrze przepisane?

Przepraszam, suma ma wynosić co najmniej 30 w podpunkcie a i co najmniej 40 w podpunkcie b. Edytowałem post

[Premislav]

a) Uszeregujmy te liczby w kolejności rosnącej:
\(\displaystyle{ 0\le a_1\le a_2\le \ldots \le a_9\le 90}\)
Zauważmy, że
\(\displaystyle{ a_1+a_2+a_3\le a_7+a_8+a_9\\ a_4+a_5+a_6\le a_7+a_8+a_9\\ a_7+a_8+a_9\le a_7+a_8+a_9}\)
Dodajemy te trzy nierówności stronami i mamy:
\(\displaystyle{ 3(a_7+a_8+a_9)\ge 90\\ a_7+a_8+a_9\ge 30}\),
co kończy dowód.

-- 22 lis 2018, o 17:56 --

Minimalnie ciekawsze jest to drugie, ale też nic specjalnego.
b)
ponownie \(\displaystyle{ 0\le a_1\le a_2\le \ldots \le a_9\le 90}\) i \(\displaystyle{ a_i}\) sumują się do \(\displaystyle{ 90}\). Odnotujmy, że dla dowolnych \(\displaystyle{ i,j,k,l}\) parami różnych zachodzi
\(\displaystyle{ a_i+a_j+a_k+a_l\le a_6+a_7+a_8+a_9}\)
Jest \(\displaystyle{ {9 \choose 4}}\) możliwości wyboru czterech liczb spośród dziewięciu i każda liczba spośród \(\displaystyle{ a_1\ldots a_9}\) wystąpi łącznie \(\displaystyle{ {8\choose 3}}\) razy, więc ze zsumowania
\(\displaystyle{ {9\choose 4}}\) nierówności postaci
\(\displaystyle{ a_i+a_j+a_k+a_l\le a_6+a_7+a_8+a_9}\)
mamy
\(\displaystyle{ {8\choose 3}(a_1+a_2+\ldots+a_9)\le {9\choose 4}(a_6+a_7+a_8+a_9)\\{8\choose 3}\cdot 90\le {9\choose 4}(a_6+a_7+a_8+a_9)\\ a_6+a_7+a_8+a_9\ge \frac{5!4!}{9!}\cdot \frac{8!}{3!5!}\cdot 90}\),
silnie skracamy i mamy tezę.

Być może istnieje też jakieś rozwiązanie z Dirichleta, ale ja jestem bardzo słaby z kombinatoryki, a coś tam trochę ogarniam z nierówności, stąd taki pomysł na rozwiązanie.