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?
Delmengde
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
-
- Grothendieck
- Innlegg: 826
- Registrert: 09/02-2015 23:28
- Sted: Oslo
Hvis $S$ er en mengde skriver vi $|\mathcal{P}(S)|$ for antall delmengder av $S$.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?
Merk først at en mengde med $n$ elementer har $2^n$ mulige delmengder:
Bevis 1: Bevis 2: 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.