Inclusie-exclusiestelling

Geplaatst op 10 februari 2023 door admin

Veronderstel dat $A_i$ eindige deelverzamelingen zijn van U en noteer met $|A_i|$ het aantal elementen van $A_i$ , dan geldt:

We noemen dit de inclusie-exclusie stelling.

Noteer $S_i$ de som van het aantal elementen in alle mogelijke doorsneden van i verzamelingen $A_i$ . Merk op dat $S_i$ precies ${n} \choose {i}$ termen bevat. Noteer met $S_0$ het aantal elementen van U. Formuleren we nu een algemenere versie van vorig resultaat:

Het aantal elementen van U dat tot precies m verzamelingen $A_i$ behoort, wordt gegeven door de formule:

$\sum_{i=0}^{n-m}(-1)^i \binom{m+i} {m} S_{m+i}$

Voor $m=n$ vinden we het aantal elementen dat tot alle $A_i$ behoren.
Voor $m=0$ vinden we het aantal elementen dat tot geen enkele $A_i$ behoort.

Vind het aantal getallen tussen 1 en 1000 dat niet deelbaar is door 2,3,5 of 7.
Stem $A_m=\{k\leq 1000 \text{ zodat k een m-voud is }\}$ .
Het is eenvoudig na te rekenen dat $|A_2|=500$ , $|A_3|=333$ , $|A_5|=200$ en $|A_7|=142$ . Bijgevolg is $S_1=1175$ .
Er zijn 166 getallen die een 2 en 3 voud zijn. Er zijn 100 getallen die een veelvoud zijn van 2 en 5. Er zijn 71 getallen die een veelvoud zijn van 2 en 7. Er zijn 66 getallen die een veelvoud zijn van 3 en 5. Er zijn 47 getallen die een veelvoud zijn van 3 en 7. Er zijn 28 getallen die een veelvoud zijn van 5 en 7. Dus is $S_2=478$ .
Eenvoudig narekenen geeft dat $S_3=79$ .
Er zijn 4 getallen die zowel deelbaar zijn door 2,3,5 en 7. Dus $S_4=4$ .
Het aantal getallen dat door geen van de cijfers 2,3,5 of 7 deelbaar is, is dan ook gelijk aan: $1000-1175+478-79+4=228$ .
Het aantal getallen dat door één van de cijfers deelbaar is, wordt gegeven door : $1*1175-2*478+3*79-4*4=440$ . Voor twee vinden we 265; voor drie 63 en tenslotte voor vier 4.

AI assistent 4.0 geeft een antwoord, maar dat is duidelijk fout!

Er zijn 720 getallen tussen 1 en 1000 die niet deelbaar zijn door 2, 3, 5 of 7. Je kunt dit aantal berekenen door alle cijfers tussen 1 en 1000 te tellen die deelbaar zijn door 2, 3, 5 of 7:

2: 500
3: 333
5: 200
7: 142

Totaal: 1225 getallen

Aantal getallen tussen 1 en 1000 die niet deelbaar zijn door 2, 3, 5 of 7: 1000 – 1225 = 720

Een patroon zoeken…

Geplaatst op 6 mei 2022 door admin

Stel $f_0(x)=\dfrac{1}{1-x}$ en $f_n(x)=f_0(f_{n-1}(x))$ voor $n=1,2,3,...$ Bereken dan

$f_{2022}(2022)$

Het is onwaarschijnlijk dat je alle functies $f_n(x)$ , waarbij n varieert van 1 tot n, zal moeten berekenen. Waarschijnlijk zit er ergens een patroon in…

Antwoord

$f_1(x)=\dfrac{1}{1-f_0(x)}=\dfrac{x-1}{x}$ .
$f_2(x)=\dfrac{1}{1-f_1(x)}=x$ .
Maar dan is $f_3(x)=f_0(x)$ .
Algemeen is $f_{3n}(x)=f_0(x)$ , $f_{3n+1}(x)=f_1(x)$ en $f_{3n+2}(x)=f_2(x)$ .
Omdat 2022 deelbaar is door 3, zal $f_{2022}(x)=f_0(x)$ .
En dus is $f_{2022}(2022)=-\dfrac{1}{2021}$ .

Bewijzen met verhaaltjes

Geplaatst op 12 mei 2020 door admin

Hoe bewijs je volgende formule?

$k(k-1)\binom{n}{k}=n(n-1)\binom{n-2}{k-2}$

Het gaat zeer snel door gebruik te maken van de definitie van binomiaalcoëfficiënten. Maar er is ook een andere manier, die je ook kan gebruiken als het gebruik van de definitie wat ingewikkelder ligt. We verzinnen gewoon een verhaaltje …

Je wilt op school met n leerlingen een leerlingenraad van k personen oprichten, waarbij een voorzitter en een ondervoorzitter moeten aangeduid worden.

Het linkerlid van bovenstaande vergelijking komt overeen met volgende procedure: kies eerst k leden uit de n leerlingen. Dit kan op $\binom{n}{k}$ manieren. Kies in die groep van k gekozenen een voorzitter ( k mogelijkheden) en een ondervoorzitter ( k-1 mogelijkheden).
Het rechterlid correspondeert met de procedure: kies uit de n leerlingen eerst een voorzitter ( n mogelijkheden), dan een ondervoorzitter( n-1 mogelijkheden) en vul tenslotte aan tot je een groep van k leden hebt. Je moet dus nog k-2 leerlingen kiezen uit de n-2 beschikbare ( $\binom{n-2}{k-2}$ mogelijkheden).
Aangezien beide procedures hetzelfde probleem oplossen , zijn linkerlid en rechterlid gelijk aan elkaar.

Telescopische som

Geplaatst op 30 augustus 2019 door admin

Eén van de technieken bij problem-solving bestaat eruit het probleem van een andere kant te bekijken of een eenvoudiger probleem te nemen. Illustreren we dit even met volgend probleem: Vereenvoudig:

$\sum_{n=1}^{2020}\tan n\tan(n+1)$

We gaan het product herschrijven als een som zodat bij het sommeren van al die termen ze één voor één tegen elkaar wegvallen , op de eerste en laatste na.
Gebruik hiervoor de formule voor het berekenen van de tangens van een verschil: $\tan((n+1)-n)=\tan 1=\frac{\tan(n+1)-\tan n}{1+\tan(n+1)\tan n}$ .
Hieruit volgt dat $\tan n\tan(n+1)=\frac{\tan (n+1)-\tan n }{\tan 1}-1$
Invullen in de opgave geeft :
$\frac{\tan 2021-\tan 1}{\tan 1}-2020=\frac{\tan 2021}{\tan 1}-2021$

Waag eens een gokje

Geplaatst op 15 december 2017 door admin

Je kan een aantal mogelijke oplossingen uitproberen. Misschien kan je zelfs het aantal mogelijke oplossingen beperken. Dan kan je best een gokje wagen en daarna proberen te bewijzen dat jouw voorstel tot oplossing de goede is.

Bepaal de volgende term in de rij:

$-1,-1,1,5,11,19,29,\cdots$

Het is zeker geen rekenkundige rij. Een eerste graadsveelterm zal dus niet kunnen om de algemene term van de rij te bepalen. Het is ook geen meetkundige rij , dus ook een exponentiële functie zal niet volstaan.
Proberen we even met een tweedegraadsfunctie. Dus een uitdrukking van de vorm $P(x)=ax^2+bx+c$ . Proberen we nu de waarden van de onbekenden $a,b$ en $c$ te vinden.
Uit $P(1)=P(2)=-1$ en $P(3)=1$ vinden we een stelsel:
$\left\{ \begin{array}{l}a+b+c=-1 \\ 4a+2b+c=-1\\9a+3b+c=1 \end{array} \right$

.
De oplossing van het stelsel is $a=1$ , $b=-3$ e, $c=1$ .
De vraag is natuurlijk of onze gok goed was! Voldoen de andere termen van de rij ook aan het voorschrift?
Nu is: $P(4)=5$ , $P(5)=11$ , $P(6)=19$ , $P(7)=29$ .
De volgende term in de rij is $P(8)=41$ .

Wiskunde is leuk

Categorie archieven: Heuristieken