wybór 6 liczb z 9

Łukasz_1989 · Post autor: **Łukasz_1989** » 16 wrz 2009, o 19:32

Spośród liczb 1, ... , 9 wybrano sześć. Wykazać, że wśród wybranych liczb jest przynajmniej jedna para, której suma wynosi 10.

Na logikę to rozumiem bo wybierając 6 liczb wybieramy pięć + kolejną z "drugiej strony" i jakaś na pewno dopełni którąś z tych 5 tak by suma była równa 10.
Ale jak to wykazać?

Qń · Post autor: Qń » 16 wrz 2009, o 23:31

Rozważmy zbiory: \(\displaystyle{ \{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}}\)
Skoro wybieramy z całości sześć liczb, a zbiorów jest pięć, to na mocy zasady szufladkowej Dirichleta, z pewnego zbioru musimy wybrać dwie liczby. To zaś oznacza tezę.

Q.

Łukasz_1989 · Post autor: **Łukasz_1989** » 16 wrz 2009, o 23:35

Czyli, liczba elementów to będzie 6, "szufladek" 5 i teraz podłoga z 6/5 = 2.
Tyle, że mały problem jest taki, że musiałeś wypisać te zbiory, jakby elementów było np 100 czy 1000 nie byłoby to takie proste więc może jest jakaś inna bardziej ogólna metoda?

Qń · Post autor: Qń » 16 wrz 2009, o 23:39

Łukasz_1989 pisze:jakby elementów było np 100 czy 1000 nie byłoby to takie proste

Byłoby tak samo proste, na przykład dla tysiąca:
\(\displaystyle{ A_i = \{i, 1001-i\} , \ i=1,2,\dots , 500}\)
jeśli więc wybieramy \(\displaystyle{ 501}\) liczb, to pewne dwie sumują się do \(\displaystyle{ 1001}\) na mocy ZSD.

Q.