Matematyka.pl

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ąć.

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).