Ado skrev:Satt å kikket gjennom abeloppgavene fra i år og kom over dette spørsmålet: Hvor mange delmengder av {1, 2, … , 2016} inneholder minst ett oddetall? (Enhver
mengde er en delmengde av seg selv.)
Har fra fasiten at svaret er [tex]2^{2016}-2^{1008}[/tex] men har problemer med å forstå funksjonen til 2-tallet for å representere delmengdene.
Noen som kan hjelpe?
Hvis $S$ er en mengde skriver vi $|\mathcal{P}(S)|$ for antall delmengder av $S$.
Merk først at en mengde med $n$ elementer har $2^n$ mulige delmengder:
Bevis 1:
- [+] Skjult tekst
- La $S$ være en mengde med $n$ elementer. Vi teller antall delmengder av $S$ ved å telle på hvor mange måter vi kan velge ut $k$ elementer i $S$, hvor $0 \leq k \leq n$. For en gitt $k$ er dette gitt ved ${n \choose k}$, så totalt antall delmengder av $S$ er $$\sum_{k=0}^n{n \choose k} = \sum_{k=0}^n{n\choose k}1^k\cdot1^{n-k}
= (1+1)^n = 2^n.$$
Bevis 2:
- [+] Skjult tekst
- La $S$ være en mengde med $n$ elementer. For enhver delmengde $R$ av $S$, vet vi at for ethvert medlem $s\in S$, så har vi at enten $s\in R$ eller $s\notin R$. Altså får vi "to valg per element i $S$", og dermed ser vi at det totale antall mulige delmengder av $S$ er lik $2\cdot 2\dots \cdot 2 = 2^n$
Altså vet vi at $|\mathcal{P}(\{1,2,\dots, 2016\})| = 2^{2016}$ etc.
Så $$\begin{align*} & \#\left(\text{delmengder av }\{1,2,\dots , 2016\}\text{ som inneholder minst ett oddetall}\right) \\
= &\text{ } |\mathcal{P}(\{1,2,\dots,2016\})| - \#\left(\text{delmengder av }\{1,2,\dots , 2016\}\text{ som ikke inneholder noen oddetall}\right) \\
= &\text{ } |\mathcal{P}(\{1,2,\dots,2016\})| - |\mathcal{P}(\{2,4,\dots,2016\})| \\
= &\text{ } 2^{2016} - 2^{\frac{2016}{2}} \\
= &\text{ } 2^{2016} - 2^{1008}. \end{align*}$$
EDIT: Aleks855 kom meg i forkjøpet med et godt svar om samme metode.