Delmengde

[Ado]

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?

[Aleks855]

Tror det vil lønne seg å se på det ekskluderte rommet i stedet.

Enhver delmengde UTEN oddetall vil være en delmengde av {2, 4, 6, 8, ..., 2016}

Det er 2^2016 delmengder av {1, 2, 3, ... , 2016} og 2^1008 delmengder av {2, 4, 6, 8, ..., 2016}

Derav svaret.

[DennisChristensen]

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.

[Ado]

Takk for hjelpen