Zasada Dirichleta - dowód.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
psimon

Zasada Dirichleta - dowód.

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
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 19 lip 2010, o 03:32
Płeć: Mężczyzna
Pomógł: 1 raz

Zasada Dirichleta - dowód.

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

Zasada Dirichleta - dowód.

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

Dzięki, udało się.

elpopo
Użytkownik
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.

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?

ODPOWIEDZ