Mam zbiór A={1, 2, 3, ... , 12}. Mam znaleźć liczbę takich podzbiorów (łącznie z pustym), w których nie znajdziemy takich dwóch liczb, które po zsumowaniu dadzą 13.
Mógłbym zrobić to mozolnie po kolei sprawdzając i wypisując, ale chciałbym znaleźć metodę, by móc to zrobić z innymi zbiorami. Niestety nie mam pomysłu, od czego zacząć.
Liczba możliwych podzbiorów.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Liczba możliwych podzbiorów.
Grupujemy elementy w pary o sumie \(\displaystyle{ 13}\):
\(\displaystyle{ (1, 12)}\)
\(\displaystyle{ (2, 11)}\)
...
\(\displaystyle{ (6, 7)}\).
Z każdej pary można wziąć do podzbioru co najwyżej jeden element (jeżeli weźmiemy oba to dostaniemy dwa elementy o sumie \(\displaystyle{ 13}\)), dlatego liczba podzbiorów w tym wypadku to \(\displaystyle{ 3^{6}}\) - mamy \(\displaystyle{ 6}\) par, a z każdej z tych par możemy wziąć jeden element (pierwszy albo drugi) albo żadnego - trzy sposoby dla każdej z par.
Analogicznie można to rozwiązać dla zbiorów dowolnej wielkości (uważając na element, którego nie da się sparować jeżeli cały zbiór ma nieparzystą liczbę elementów).
\(\displaystyle{ (1, 12)}\)
\(\displaystyle{ (2, 11)}\)
...
\(\displaystyle{ (6, 7)}\).
Z każdej pary można wziąć do podzbioru co najwyżej jeden element (jeżeli weźmiemy oba to dostaniemy dwa elementy o sumie \(\displaystyle{ 13}\)), dlatego liczba podzbiorów w tym wypadku to \(\displaystyle{ 3^{6}}\) - mamy \(\displaystyle{ 6}\) par, a z każdej z tych par możemy wziąć jeden element (pierwszy albo drugi) albo żadnego - trzy sposoby dla każdej z par.
Analogicznie można to rozwiązać dla zbiorów dowolnej wielkości (uważając na element, którego nie da się sparować jeżeli cały zbiór ma nieparzystą liczbę elementów).