Categorie archieven: Discrete wiskunde

Vrijdag de dertiende

Geplaatst op door

 

Toon aan dat er in ieder jaar minstens 1  en hoogstens 3 keer vrijdag de dertiende   voorkomt.

  • De dertiende van elke maand in een niet-schrikkeljaar hebben als dagnummer:13,44,72,103,133,164,194,225,256,286,317,347.
  • De resten bij deling door 7 zijn: 6,2,2,5,0,3,5,1,4,6,2,4
  • Twee maanden A en B worden in hetzelfde vakje geplaatst als de dertiende van die maanden op dezelfde dag van de week vallen. Omdat elk getal, van 0 tot 6, voorkomt in de laatste rij, zijn de maanden over de 7 vakjes verdeeld.
  • Elk van de 7 vakjes stelt één van de dagen van de week voor. Omdat elk vakje bezet is, komt er minstens 1 vrijdag de dertiende voor in een niet-schrikkeljaar.
  • Een zelfde waarde in dat rijtje resten komt hoogstens 3 maal voor, dus kunnen er hoogstens 3 vrijdagen de dertiende voorkomen.
  • Voor een schrikkeljaar zijn de dagnummers van de dertiende: 13,44,73,104,134,165,195,226,257,287,318 en 348.
  • De resten bij deling door 7 zijn: 6,2,3,6,1,4,6,2,5,0,3 en 5. De redenering is analoog als hierboven

 6 januari 2023 is een vrijdag, dus zijn er in 2023 twee vrijdagen de dertiende, namelijk in januari en oktober: de dagnummers moeten modulo 7 gelijk zijn aan 6 en er komt in het rijtje dagnummers bij niet-schrikkeljaren inderdaad 2 keer een 6 voor.

Een telprobleem

Geplaatst op door

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

Geplaatst op door

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

Geplaatst op door

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

Geplaatst op door

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\]