Een telprobleem

Op hoeveel manieren kan je een rijtje van 10 symbolen 0,1 of 2 maken zodat er nooit twee enen of twee twee na elkaar voorkomen?

Goed is dus 1200121001 en fout is 0012011202 omdat hier twee enen na elkaar voorkomen. 

Vorm de matrix

    \[A=\begin{pmatrix} 1&1&1\\1&0&1\\1&1&0\end{pmatrix}\]

Nummer de rijen en de kolommen met 0,1en 2

a_{00}=1 betekent: er is een mogelijkheid om na een 0 een tweede nul te plaatsen.
a_{11}=0 betekent : na een 1 kan er geen 1 komen.
a_{12}=1 betekent: na een 1 kan er een 2 komen.

Het is duidelijk dat de som van de elementen van deze matrix A het aantal goede tweetallen is: 00,01,02,10,12,20,21 . Er zijn 7 goede tweetallen.

Net zoals bij een directe wegenmatrix (soort overgangsmatrix) zal de som van de elementen van A^9 dan het aantal goede tientallen geven:

    \[A^9=\begin{pmatrix} 1393&985&985\\985&696&697\\985&697&696\end{pmatrix}\]

Het antwoord op de gestelde vraag is dan 8119.

Som van opeenvolgende getallen

Op hoeveel manier kan je, bijvoorbeeld, 45 schrijven als som van opeenvolgende getallen? 

  • We stellen een formule op om de som van opeenvolgende getallen te berekenen. Stel n=m+(m+1)+\dots+(m+k-1). Hier bij is n de som, m het eerste getal en k het aantal getallen in die som.
  • Om die som te berekenen kan je de formule voor de som van de termen van een rekenkundige rij gebruiken: n=\dfrac{1}{2}k.(m+m+k-1).
  • Hieruit volgt:

        \[2n=k(2m+k-1)\]

  • Als k even is dan is 2m + k –  oneven en omgekeerd als k oneven is dan is 2m + k – 1 even. Bovendien is k kleiner dan 2m + k  – 1.
  • We moeten 2n dus schrijven als een product van een even getal en een oneven getal. De kleinste van die 2 factoren is k en dat is het aantal termen in de som.
  • Ontbinden we n in priemfactoren: n=2^r.p_1^{r_1}.\cdots .p_s^{r_s}. En dan is 2n=2^{r+1}.p_1^{r_1}.\cdots . p_s^{r_s}. Hierbij zijn p_i verschillende (oneven) priemgetallen. Dit moeten we dan schrijven als product van een oneven en even getal
  • Noteer S(n) het aantal mogelijkheden om n te schrijven als een som van opeenvolgende getallen, dan is het duidelijk dat

        \[S(n)=(r_1+1).\cdots.(r_s+1)-1\]

  • Terug naar ons voorbeeld n=45. dan is 2n=90=2.3^2.5^1 en is S(45)=(2+1)(1+1)-1=5. We kunnen 45 op 5 manieren schrijven als som van opeenvolgende getallen.
  • Hoe vinden we nu die sommen? We kunnen eerst m berekenen uit 2n=k(2m+k-1):  m=\dfrac{1}{2}(n-k+1) en we nemen k opeenvolgend als 2,3,5,6,9. Dit geeft:
  • \begin{array}{c|c|c} k&m&\text{som}\\ \hline 2&22&22+23\\3&14&14+15+16\\5&7&7+8+9+10+11\\6&5&5+6+7+8+9+10\\9&1&1+2+3+4+5+6+7+8+9\end{array}

Marginale kosten

De marginale kostprijs, dit is de kostprijs om de productie van n stuks per dag op te voeren met 1 eenheid, wordt gegeven door

    \[M(n)=10000-2n+0,004n^2\]

Bereken de meerkost,  genoteerd met M(n,m),  om de productie op te voeren van 400 naar 450 stuks.

Noteer met K(n) de totale kostprijs voor de productie van n stuks per dag. De marginale kostprijs op niveau n is dan

    \[M(n)=K(n+1)-K(n)\]

We weten dus dat K(n+1--K(n)= 10000-2n+0,004n^2. Dit is een recursievergelijking. Eigenlijk is dit de discrete tegenhanger van het begrip afgeleide. Het is dus niet onredelijk te veronderstellen dat K(n) een derdegraadsveelterm is. Noteer K(n)=a+bn+cn^2+dn^3. Invullen is de recursievergelijking geeft de oplossingen voor a,b,c en d. We vinden b = 10001,00067; c = -1,001 en c = 0,0013333.

Dan is M(400,450) = 493632.

Som 28

Op hoeveel manieren N kan je 28  schrijven als som van verschillende natuurlijke getallen ( \neq 0)?

  • Noteer S_k(n) als het aantal mogelijkheden om n te schrijven als som van k verschillende natuurlijke getallen, verschillend van 0.
  • Het is niet zo  moeilijk om S_2(28) uit te rekenen: 1+27,2+26,…13+15. Dus S_2(28)=13.
  • Omdat 1+2+3+4+5+6+7=28 is S_7(28)=1. Bovendien zal voor k>7: S_k(28)=0.
  • Berekenen we eerst S_3(28). Stel dus dat x+y+z=28 en neem x<y<z. Als x>1, dan is x-1,y-1,z-1 een drietal met som 25, dus een mogelijkheid  uit S_3(25). Omgekeerd kan je ook met elke mogelijkheid van S_3(25), een mogelijkheid van S_3(28) laten corresponderen met elementen groter dan 1. 
  • Stel echter dat x=1, dan is  y-1,z-1 een tweetal met som  25 en dus een mogelijkheid uit S_2(25).
  • Uit vorige redeneringen  volgt S_3(28)=S_3(25)+S_2(25) of algemener:

        \[S_3(n)=S_3(n-3)+S_2(n-3)\]

  • Herhaaldelijk toepassen van die formule geeft: S_3(28)=S_2(25)+S_2(22)+S_2(19)+S_2(16)+S_2(13)+S_2(10)+S_2(7)+S_2(4).
  • Maar S_2(n)=\frac{n}{2}-1 als n even is en S_2(n)=\frac{n-1}{2} als n oneven is. Hieruit volgt dat S_3(28)=12+10+9+7+6+4+3+1=52.
  • Om S_4(28) te berekenen gebruiken we een analoge formule S_4(n)=S_3(n-4)+S_2(n-4). Idem voor S_5(28) en S_6(28).
  • Enkele berekingen staan in volgende tabel en zo vinden we

        \[N=13+52+84+57+14+1=221\]

 

Voetbal

 

Op een voetbal komt een netwerk van bogen voor, die de oppervlakte van de bal verdelen in een aantal gebieden. Sommige van die gebieden worden door vijf bogen begrensd en zijn dus vijfhoekig van vorm; de rest van de gebieden is zeshoekig. Bij elk knooppunt van het netwerk komen drie gebieden samen; twee daarvan zijn zeshoekig en het derde is vijfhoekig. De vijfhoekige gebieden zijn zwart en de zeshoekige zijn wit. Elk vijfhoekig gebied omgeven wordt door een krans van vijf zeshoekige gebieden. 

Noemen we het aantal knooppunten V ( vertrices), E het aantal bogen (edges) en F het aantal gebieden (faces). Euler zegt dat

    \[V-E+F=2\]

  • Stel x het aantal vijfhoeken en y het aantal zeshoeken. Er zijn dus 5x , maar ook 6y knooppunten ( want in elk hoekpunt komen 2 zeshoeken samen). Bijgevolg is y=\frac{5}{3}x.
  • Alle vijfhoeken en zeshoeken hebben samen 5x + 6y = 5x + 10x= 15x zijden. Bij elke boog van het netwerken vallen twee zijden samen dus E=\frac{15}{2}x.
  • Het aantal gebieden wordt gegeven door F=x+y=\frac{8}{3}x .

De formule van Euler voor veelvlakken wordt nu : 5x-\frac{15}{2}x+ \frac{8}{3}x=2 of x=12

Onze voetbal is dus opgebouwd uit 12 vijfhoeken en 20 zeshoeken, dus 32 zijvlakken; Verder zijn er 60 knooppunten en 90  bogen.

In de wiskunde noemt men deze figuur : de afgeknotte isocaëder.