Matematyka.pl

Udowodnić, że wśród \(\displaystyle{ 2n-1}\) różnych dodatnich liczb rzeczywistych o sumie \(\displaystyle{ S}\), można na co najmniej \(\displaystyle{ {2n-2 \choose n-1 } }\) sposobów wyjąć \(\displaystyle{ n}\) liczb o sumie co najmniej \(\displaystyle{ \frac{S}{2}}\) .

A co to ma wspólnego z rybami?

JK

Gdyż sumy to ryby...

No jasne! Jak mogłem tego nie zauważyć...

JK

Sprawa jest dość prosta a mianowicie gdyby nie istniało:

\(\displaystyle{ {2n-2 \choose n-1} }\) takich sum, to istniałoby więcej niż: \(\displaystyle{ {2n-2 \choose n-1} }\) sum, których suma: \(\displaystyle{ < \frac{S}{2} }\)

a ponieważ nie da się wybrać \(\displaystyle{ n}\) różnych sum z \(\displaystyle{ 2n-2}\) liczb tak, żeby choć jedno \(\displaystyle{ a_{i}}\) nie należało choć do jednej sumy ( Taki na chłopski rozum Dirichlet)...

Więc muszą istnieć dwie sumy, do których należą wszystkie \(\displaystyle{ a_{i}}\) a do tego istnieje takie i , że: \(\displaystyle{ a_{i}}\) należy do obu sum...

Co da sprzeczność ponieważ istnieją takie: \(\displaystyle{ i, j}\):

\(\displaystyle{ \sum_{1}^{} + \sum_{2}^{} < \frac{S}{2} + \frac{S}{2}=S }\)

A sumy te zawierają wszystkie elementy: \(\displaystyle{ a_{i}}\)

cnd...

Przykład na przykład:

Niech:

\(\displaystyle{ 2n-1=3}\)

\(\displaystyle{ n=2}\)

\(\displaystyle{ {2n-2 \choose n-1} = {2 \choose 1} =2}\)

niech teraz:

\(\displaystyle{ a_{1}+a_{2}+a_{3}=S}\)

\(\displaystyle{ a_{1}<a_{2}<a_{3}}\)

Weźmy dwie sumy nawet jak najmniejsze:

\(\displaystyle{ a_{1}+a_{2}< \frac{S}{2} }\)

\(\displaystyle{ a_{1}+a_{3}< \frac{S}{2} }\)

Zsumujmy te sumy:

\(\displaystyle{ 2a_{1}+a_{2}+a_{3}< \frac{S}{2} +\frac{S}{2}=S }\)

\(\displaystyle{ a_{1}<0}\)

Sprzeczność z założeniem...