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 .
Zasada Dirichleta - dowód.
Zasada Dirichleta - dowód.
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
Nie napisałem wszystkiego krok po kroku żebyś miał trochę zabawy, ale policzyłem to i działa
-
- Użytkownik
- Posty: 99
- Rejestracja: 19 paź 2010, o 22:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 1 raz
Zasada Dirichleta - dowód.
"Z zasady szufladkowej możesz stwierdzić, że pewne dwa zbiory pięcioelementowe mają równe sumy elementów" - skąd to wiemy?