zasada szufladkowa Dirichleta
ania21: Niech A będzie pewnym 14−elementowym podzbiorem zbioru B = {1,2,3,...,100} . Wykaż, że
istnieje przynajmniej 8 różnych, 7−elementowych podzbiorów zbioru A, o tej samej sumie
liczb. W zadaniu skorzystaj z zasady szufladkowej Dirichleta
Błagam o pomoc
23 maj 21:21
teofrast: Coś chyba niedobrze z tym zadaniem... Albo ja się mylę!
Spróbujmy oszacować z góry i z dołu owe sumy; Jest oczywiste, że największą możliwą sumą byłoby
94 + 95 + ... + 100 = 679. A najmniejszą 1 + 2+ 3+...+ 7 = 7x4 = 28. Zatem wszystkich
możliwych sum utworzonych z 7 dowolnie wybranych liczb z przedziału [1; 100]∩ℕ jest 679 − 28
+1= 652.
Kazdą możliwą sumą zaetykietujemy jakąś szufladkę: szufladek będzie 652 sztuki.
Teraz co będziemy wkładać do naszych szufladek − otóz sumy elementów podciągów 7 elementowych
wybranych z ciągu 14 elementowego . Takich podciągów jest C( 7, 14) = 3432.
Ponieważ zaś szufladek jest 652z zatem co najmniej ent(3452652) = 5 trafi do jednej
szufladki.
Nie potrafię podać lepszego oszacowania...
24 maj 00:28
teofrast: Może po prostu przy przepisywaniu 5 pomylono z 8 ? Z daleka sa podobne do siebie...
24 maj 00:34
24 maj 01:07
PW: Ja to trochę inaczej rozumiem. Wybierając 14 liczb p
1<p
2<p
3<...<p
14 a następnie 7
spośród nich, mamy najmniejszą sumę siedmiu liczb równą
s
min= p
1+p−2+...+p
7.
a największą
s
max=p
8+p
9+...+p
14.
Wcale nie ma gwarancji, że wszystkie liczby z zakresu <s
min,s
max> będą sumami wybieranych
siódemek. Problem właśnie w tym i w oszacowaniu różnicy s
max−s
min, ale nie umiem tego
zrobić o pierwszej w nocy (a może w ogóle).
24 maj 01:16
PW: Dręczyło mnie to przez parę dni, nic sensownego nie wymyśliłem (a artykułu z linku
teofrasta nie chciałem czytać). W końcu stwierdziłem, że jest to przecież banalne zadanie
informatyczne − wygenerować wszystkie możliwe 7−elementowe podciągi rosnące ze zboru
14−elementowego, zsumować wyrazy każdego podciągu i policzyć powtarzające się sumy.
Dla tego "najbardziej paskudnego" zbioru
A={1,2,3,4,5,6,7,94,95,96,97,98,99,100}
wyniki są niespodziewane, na przykład suma 400 jest osiągana aż 119 razy!
Są to następujące podciągi:
1 2 3 97 98 99 100
1 2 4 96 98 99 100
1 2 5 95 98 99 100
1 2 5 96 97 99 100
1 2 6 94 98 99 100
1 2 6 95 97 99 100
1 2 6 96 97 98 100
1 2 7 94 97 99 100
1 2 7 95 96 99 100
1 2 7 95 97 98 100
1 2 7 96 97 98 99
1 3 4 95 98 99 100
1 3 4 96 97 99 100
1 3 5 94 98 99 100
1 3 5 95 97 99 100
1 3 5 96 97 98 100
1 3 6 94 97 99 100
1 3 6 95 96 99 100
1 3 6 95 97 98 100
1 3 6 96 97 98 99
1 3 7 94 96 99 100
1 3 7 94 97 98 100
1 3 7 95 96 98 100
1 3 7 95 97 98 99
1 4 5 94 97 99 100
1 4 5 95 96 99 100
1 4 5 95 97 98 100
1 4 5 96 97 98 99
1 4 6 94 96 99 100
1 4 6 94 97 98 100
1 4 6 95 96 98 100
1 4 6 95 97 98 99
1 4 7 94 95 99 100
1 4 7 94 96 98 100
1 4 7 94 97 98 99
1 4 7 95 96 97 100
1 4 7 95 96 98 99
1 5 6 94 95 99 100
1 5 6 94 96 98 100
1 5 6 94 97 98 99
1 5 6 95 96 97 100
1 5 6 95 96 98 99
1 5 7 94 95 98 100
1 5 7 94 96 97 100
1 5 7 94 96 98 99
1 5 7 95 96 97 99
1 6 7 94 95 97 100
1 6 7 94 95 98 99
1 6 7 94 96 97 99
1 6 7 95 96 97 98
2 3 4 94 98 99 100
2 3 4 95 97 99 100
2 3 4 96 97 98 100
2 3 5 94 97 99 100
2 3 5 95 96 99 100
2 3 5 95 97 98 100
2 3 5 96 97 98 99
2 3 6 94 96 99 100
2 3 6 94 97 98 100
2 3 6 95 96 98 100
2 3 6 95 97 98 99
2 3 7 94 95 99 100
2 3 7 94 96 98 100
2 3 7 94 97 98 99
2 3 7 95 96 97 100
2 3 7 95 96 98 99
2 4 5 94 96 99 100
2 4 5 94 97 98 100
2 4 5 95 96 98 100
2 4 5 95 97 98 99
2 4 6 94 95 99 100
2 4 6 94 96 98 100
2 4 6 94 97 98 99
2 4 6 95 96 97 100
2 4 6 95 96 98 99
2 4 7 94 95 98 100
2 4 7 94 96 97 100
2 4 7 94 96 98 99
2 4 7 95 96 97 99
2 5 6 94 95 98 100
2 5 6 94 96 97 100
2 5 6 94 96 98 99
2 5 6 95 96 97 99
2 5 7 94 95 97 100
2 5 7 94 95 98 99
2 5 7 94 96 97 99
2 5 7 95 96 97 98
2 6 7 94 95 96 100
2 6 7 94 95 97 99
2 6 7 94 96 97 98
3 4 5 94 95 99 100
3 4 5 94 96 98 100
3 4 5 94 97 98 99
3 4 5 95 96 97 100
3 4 5 95 96 98 99
3 4 6 94 95 98 100
3 4 6 94 96 97 100
3 4 6 94 96 98 99
3 4 6 95 96 97 99
3 4 7 94 95 97 100
3 4 7 94 95 98 99
3 4 7 94 96 97 99
3 4 7 95 96 97 98
3 5 6 94 95 97 100
3 5 6 94 95 98 99
3 5 6 94 96 97 99
3 5 6 95 96 97 98
3 5 7 94 95 96 100
3 5 7 94 95 97 99
3 5 7 94 96 97 98
3 6 7 94 95 96 99
3 6 7 94 95 97 98
4 5 6 94 95 96 100
4 5 6 94 95 97 99
4 5 6 94 96 97 98
4 5 7 94 95 96 99
4 5 7 94 95 97 98
4 6 7 94 95 96 98
5 6 7 94 95 96 97
3 cze 20:26
xx:
a suma=28 jest osiągana dokładnie 1 raz dla zbioru A, który podał PW
11 cze 15:04