Zasada szufladkowa Dirichleta
-
Eno_
- Użytkownik
- Posty: 55
- Rejestracja: 13 sty 2018, o 13:56
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 33 razy
Zasada szufladkowa Dirichleta
Witam, w zadaniu muszę udowodnić, że jeśli mam dowolny zbiór złożony z 8 różnych liczb dwucyfrowych <37, to wewnątrz tego zbioru można wybrać dwa rozłączne podzbiory o tej samej sumie. Nie widzę jednak co w tym wypadku będzie pełniło rolę szufladek. Z góry dziękuję za pomoc.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Zasada szufladkowa Dirichleta
Niech tymi liczbami będą \(\displaystyle{ x_1<x_2<\ldots<x_8}\).
Największa możliwa suma to \(\displaystyle{ x_1+x_2+\ldots+x_8\le 260}\) (jak dobrze zsumowałem \(\displaystyle{ 29+30+\ldots+36}\)), a najmniejsza może być równa \(\displaystyle{ x_1}\) (singleton najmniejszego elementu), stąd jest nie więcej (tak naprawdę zwykle mniej) niż \(\displaystyle{ x_2+\ldots+x_8+1}\) wartości, jakie może przyjmować suma (czyli nie więcej niż \(\displaystyle{ 232}\)).
Dwa rozłączne podzbiory zbioru ośmioelementowego możemy zaś wybrać na
\(\displaystyle{ 3^8}\) sposobów: po prostu dla każdego elementu decydujemy, czy element ten trafi do pierwszego podzbioru, do drugiego podzbioru, czy też do żadnego z nich.
Zatem rozwiązanie wynika z zasady szufladkowej i z nierówności \(\displaystyle{ 3^8>232}\).
Ale mogłem coś zepsuć, bo jestem bardzo słaby z kombinatoryki…
-- 7 lis 2018, o 22:01 --
No jasne: możemy wybrać dwa rozłączne podzbiory na \(\displaystyle{ 3^8}\) sposobów, ale to wcale nie znaczy, że aby się nie powtórzyły sumy, musimy mieć co najmniej \(\displaystyle{ 3^8}\) możliwych wartości sumy. Prześledźmy to na mniejszym przykładzie: mamy
trójelementowy zbiór liczb jednocyfrowych i zastanawiamy się, czy zawsze da się tak wybrać dwa rozłączne podzbiory, by miały one tę samą sumę elementów. I mogłoby się wydawać, że z analogicznego rozumowania odpowiedź brzmi „tak", gdyż możliwych sum jest nie więcej niż \(\displaystyle{ 7+8+9+1=25}\), zaś \(\displaystyle{ 3^3>25}\), a tymczasem dla zbioru \(\displaystyle{ \left\{ 2,5,8\right\}}\) jak byśmy dzielili, nie podzielimy tak, by sumy były równe. Przepraszam.
Wniosek odnośnie maksymalnej liczby możliwych sum był poprawny (choć to szacowanie przeważnie powinno dać się poprawić, to z drugiej strony winno wystarczyć), zliczenie możliwości wyborów rozłącznych zbiorów także, ale konkluzję z tego wyciągnąłem błędną. Ale to nie szkodzi, bo wystarczy to, że \(\displaystyle{ 2^8>232}\). Już tłumaczę: każdemu podzbiorowi tego zbioru ośmioelementowego przypisujemy jego sumę. Jeśli udowodnimy, że znajdziemy dwa różne zbiory (niekoniecznie rozłączne) o tej samej sumie, to możemy wyrzucić liczby, które się powtarzają w obu zbiorach i wciąż otrzymamy w ten sposób podzbiory o tej samej sumie elementów (w końcu „odjęliśmy" tyle samo), tylko że już rozłączne.
Największa możliwa suma to \(\displaystyle{ x_1+x_2+\ldots+x_8\le 260}\) (jak dobrze zsumowałem \(\displaystyle{ 29+30+\ldots+36}\)), a najmniejsza może być równa \(\displaystyle{ x_1}\) (singleton najmniejszego elementu), stąd jest nie więcej (tak naprawdę zwykle mniej) niż \(\displaystyle{ x_2+\ldots+x_8+1}\) wartości, jakie może przyjmować suma (czyli nie więcej niż \(\displaystyle{ 232}\)).
Dwa rozłączne podzbiory zbioru ośmioelementowego możemy zaś wybrać na
\(\displaystyle{ 3^8}\) sposobów: po prostu dla każdego elementu decydujemy, czy element ten trafi do pierwszego podzbioru, do drugiego podzbioru, czy też do żadnego z nich.
Zatem rozwiązanie wynika z zasady szufladkowej i z nierówności \(\displaystyle{ 3^8>232}\).
Ale mogłem coś zepsuć, bo jestem bardzo słaby z kombinatoryki…
-- 7 lis 2018, o 22:01 --
No jasne: możemy wybrać dwa rozłączne podzbiory na \(\displaystyle{ 3^8}\) sposobów, ale to wcale nie znaczy, że aby się nie powtórzyły sumy, musimy mieć co najmniej \(\displaystyle{ 3^8}\) możliwych wartości sumy. Prześledźmy to na mniejszym przykładzie: mamy
trójelementowy zbiór liczb jednocyfrowych i zastanawiamy się, czy zawsze da się tak wybrać dwa rozłączne podzbiory, by miały one tę samą sumę elementów. I mogłoby się wydawać, że z analogicznego rozumowania odpowiedź brzmi „tak", gdyż możliwych sum jest nie więcej niż \(\displaystyle{ 7+8+9+1=25}\), zaś \(\displaystyle{ 3^3>25}\), a tymczasem dla zbioru \(\displaystyle{ \left\{ 2,5,8\right\}}\) jak byśmy dzielili, nie podzielimy tak, by sumy były równe. Przepraszam.
Wniosek odnośnie maksymalnej liczby możliwych sum był poprawny (choć to szacowanie przeważnie powinno dać się poprawić, to z drugiej strony winno wystarczyć), zliczenie możliwości wyborów rozłącznych zbiorów także, ale konkluzję z tego wyciągnąłem błędną. Ale to nie szkodzi, bo wystarczy to, że \(\displaystyle{ 2^8>232}\). Już tłumaczę: każdemu podzbiorowi tego zbioru ośmioelementowego przypisujemy jego sumę. Jeśli udowodnimy, że znajdziemy dwa różne zbiory (niekoniecznie rozłączne) o tej samej sumie, to możemy wyrzucić liczby, które się powtarzają w obu zbiorach i wciąż otrzymamy w ten sposób podzbiory o tej samej sumie elementów (w końcu „odjęliśmy" tyle samo), tylko że już rozłączne.