Zasada Dirichleta - dowód.

psimon · Post autor: **psimon** » 28 lip 2010, o 14:35

Witam , mam taki problem. Gnębi mnie takie zadanie:

Udowodnij , że w zbiorze dowolnych jedenastu różnych liczb dwucyfrowych można zawsze wybrać takie dwa podzbiory nie mające elementu wspólnego, które mają taką samą ilość elementów i taką samą sumę.

We wskazówkach z książki było : Skorzystaj z zasady szufladkowania Dirichleta. Tu jednak widać utrudnienie, bo taki te podzbiory mogą być zarówno 2-,3-,4-, jak i 5-elementowe.
Jest to zadanie z olimpiady dla pierwszej klasy szkoły średniej z 1995r. Zrobiłem resztę z tego rocznika , tylko te mi zostało .

bm371613 · Post autor: **bm371613** » 28 lip 2010, o 14:49

Z zasady szufladkowej możesz stwierdzić, że pewne dwa zbiory pięcioelementowe mają równe sumy elementów. Część wspólna tych zbiorów ma najwyżej trzy elementy. Zatem jeśli usuniemy z obu zbiorów część wspólną mamy dwa zbiory o co najmniej dwóch elementach i równej sumie.

Nie napisałem wszystkiego krok po kroku żebyś miał trochę zabawy, ale policzyłem to i działa

psimon · Post autor: **psimon** » 28 lip 2010, o 15:16

Dzięki, udało się.

elpopo · Post autor: **elpopo** » 9 paź 2011, o 15:35

"Z zasady szufladkowej możesz stwierdzić, że pewne dwa zbiory pięcioelementowe mają równe sumy elementów" - skąd to wiemy?