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}}\) .Zadanie o rybach
-
mol_ksiazkowy
- Użytkownik
- Posty: 13537
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3436 razy
- Pomógł: 812 razy
Zadanie o rybach
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}}\) .-
Jan Kraszewski
- Administrator
- Posty: 36198
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 5348 razy
-
mol_ksiazkowy
- Użytkownik
- Posty: 13537
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3436 razy
- Pomógł: 812 razy
-
Jan Kraszewski
- Administrator
- Posty: 36198
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 5348 razy
-
arek1357
Re: Zadanie o rybach
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...
\(\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...