Niech \(\displaystyle{ M}\) będzie 10-elementowym podzbiorem zbioru \(\displaystyle{ \{0, 1, 2, ..., 99\}}\). Dowieść, ze zbiór \(\displaystyle{ M}\) posiada dwa rozłączne niepuste podzbiory o takiej samej sumie elementów.
Zadanie pochodzi z warsztatów krakowskiego V LO (). Na forum widziałam dużo podobnych, ale mam nadzieję, że takiego może jednak nie było.
[Kombinatoryka] Równe sumy elementów podzbiorów- Warsztaty V LO
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
[Kombinatoryka] Równe sumy elementów podzbiorów- Warsztaty V LO
Maksymalna suma elementów podzbioru \(\displaystyle{ M}\) jest mniejsza niż \(\displaystyle{ 1000}\), a niepustych podzbiorów \(\displaystyle{ M}\) jest \(\displaystyle{ 2^{10}-1=1023}\). Tak więc na mocy zasady szufladkowej Dirichleta istnieją pewne podzbiory \(\displaystyle{ A,B}\), które mają równą sumę elementów. Żeby zadośćuczynić jeszcze żądaniu rozłączności, wystarczy zauważyć, że spełniają je zbiory \(\displaystyle{ A \backslash B}\) i \(\displaystyle{ B \backslash A}\), które także mają równą sumę elementów oraz są niepuste.
Q.
Q.