Tag archieven: problem solving

Recursie

Geplaatst op door

Een rij van getallen kan je geven met behulp van een recursief  voorschrift zoals bijvoorbeeld : a_1=1 en a_n= 2a_{n-1}+1. Soms kan je uit dit recursief voorschrift een expliciete formule afleiden voor de algemene term van de rij. Soms kan dat niet, maar is het mogelijk, via recursie, de parameters te herleiden tot waarden waarvoor je het probleem wel kan oplossen.

Een eerlijk muntstuk wordt n keer opgeworpen. Wat is de kans op twee opeenvolgende keren kop ergens in de rij worpen?

  • Noteer met P_n de kans dat er nergens twee keer kop na elkaar voorkomt is de rij van n worpen.
  • Het is duidelijk dat P_1=1 en P_2=\frac{3}{4}.
  • Stel n>2. Dan zijn er twee mogelijkheden naargelang de eerste worp kop of munt is.
  • Als je eerst munt gooit, dan is de kans dat je nergens twee keer kop na elkaar hebt in de volgende n-1 worpen gelijk aan P_{n-1}.
  • Gooi je eerst kop, dan moet de tweede worp munt zijn, want anders zou je twee keer kop na elkaar hebben. De kans dat je nergens twee keer kop na elkaar hebt in de volgende n-2 worpen gelijk aan P_{n-2}.
  • Uit de vorige twee punten vinden we tenslotte dat

        \[P_n=\frac{1}{2}P_{n-1}+\frac{1}{4}P_{n-2}\]

  • Dit kan je herleiden tot 2^nP_n=2^{n-1}}P_{n-1}+2^{n-2}P_{n-2}. Of via S_n=2^nP_n:

        \[S_n=S_{n-1}+S_{n-2}\]

  • Dit is de rij van Fibonacci, waarbij S_n het n+2 de getal in de rij van Fibonacci is. Dus S_n=F_{n+2}. De gezochte kans op twee opeenvolgende keren kop ergens in de rij van n worpen, met n>2 is dan X=1-P_n=1-\frac{F_{n+2}}{2^n}.

Bewijs door inductie

Geplaatst op door

Vaak bestaat een probleem erin aan te tonen dat een bepaalde eigenschap geldt voor elk natuurlijk getal. Hiervoor gebruiken we het principe van de  volledige inductie 

  •  Basisstap: Men bewijst P(1)
  • Inductiehypothese: Men bewijst voor elke k dat als P(k) geldt, dan ook P(k+1) geldt.

Er bestaat ook een andere vorm, die we de sterke inductie noemen:

  • Basisstap: Men bewijst P(1) .
  • Inductiehypothese: Men bewijst voor elke k dat als P(1),P(2),\ldots,P(k) gelden, dan ook P(k+1) geldt.

Voor elk natuurlijk getal n geldt :

    \[1^2+2^2+\ldots+n^2=\frac{1}{6}n(n+1)(2n+1)\]

  • De geldigheid van de formule voor n=1 is duidelijk, want  1^2=\frac{1}{6}.1.(1+1)(2+1). Dit is de basisstap.
  • De inductiehypothese : stel dat de formule ook geldt voor n=k. Dan is: 

        \begin{align*}1^2+2^2+\ldots+k^2+(k+1)^2=&(1^2+2^2+\ldots+k^2)+(k+1)^2\\=& \frac{1}{6}k(k+1)(2k+1)+(k+1)^2\\=&\frac{1}{6}(k+1)(2k^2+7k+6)\\=&\frac{1}{6}(k+1)(k+2)(2k+3) \end{align*}

    en dit is precies de formule voor n=k+1


					

		
		
	


				
					
	

		

						
Contradictie

			
						

				Geplaatst op   door  			

			
					


				

			
Redeneren door  tegenspraak gaat uit van de veronderstelling dat de conclusie niet juist is en probeert door argumenteren te komen tot iets wat in tegenspraak is met gegeven is (de indirecte methode) of iets wat in tegenspraak is met iets waarvan we weten dat het waar is (reductio ad absurdum).




Bewijs dat de onderstaande reeks divergeert  


      \[1+\frac{1}{2}+\frac{1}{3}+\cdots\]




    

  •  We veronderstellen dat de reeks niet divergeert maar dus convergeert naar de waarde r.
    • 

  •  Dus r=(1+\frac{1}{2})+(\frac{1}{3}+ \frac{1}{4})+(\frac{1}{5}+ \frac{1}{6})+\cdots.
    • 

  •  De eerste term van elk groepje van twee termen is groter dan de tweede, dus kunnen we schrijven dat

          \[r> (\frac{1}{2}+ \frac{1}{2})+ (\frac{1}{4}+ \frac{1}{4})+ (\frac{1}{6}+ \frac{1}{6})+\cdots = 1+\frac{1}{2}+ \frac{1}{3}+\cdots=r\]
    

    .
    • 

  • Dus is r>r en dat is onmogelijk. Bijgevolg is de harmonische reeks niet convergent, maar wel divergent.
    • 



 

					

		
		
	


				
					
	

		

						
Werk van achter naar voren

			
						

				Geplaatst op   door  			

			
					


				

			
Bij het werken van achter naar voren veronderstellen we dat de conclusie klopt en gaan we daaruit allerlei conclusies trekken tot we ergens terechtkomen bij een bekende situatie of bij iets wat we gemakkelijk kunnen bewijzen.




Een voorbeeld:


Je hebt twee emmers zonder merkstreepjes, één van 9 liter en één van 4 liter. Hoe kan je hiermee precies 6 liter water uit een waterput afmeten?


    

  • De eindsituatie is zes liter in de grote emmer.
    • 

  • Wat is de situatie daarvoor? 6 =9-3, dus die 6 liter kan verkregen worden door 3 liter weg te gieten uit de volle emmer van 9 liter.
    • 

  • Om 3 liter te kunnen afgieten moet er in de kleine emmer juist 1 liter aanwezig zijn.
    • 

  • Maar 1 =9-4-4: dus \’e\’en grote emmer waaruit 2 keer de inhoud van de kleine emmer is weggegoten.
    • 

  • Besluit: we vullen de grote emmer met 9 liter en gieten 2 keer 4 liter over in de kleine emmer. Dan gieten we die ene liter in de kleine emmer. We vullen nu terug de grote emmer met 9 liter en gieten water over in de kleine emmer tot die volledig vol is. Er blijft dan 6 liter water over in de grote emmer.
    • 


					

		
		
	


				
					
	

		

						
Opgave 7

			
						

				Geplaatst op   door  			

			
					


				

			
Toon aan dat volgende veeltermfunctie nooit de getalwaarde 33 aanneemt voor willekeurige gehele waarden van x en y. 


      \[f(x)=x^5+3x^4y-5x^3y^2-15x^2y^3+4xy^4+12y^5\]





				
Antwoord

				


    

  1. We moeten bewijzen dat de vergelijking

          \[x^5+3x^4y-5x^3y^2-15x^2y^3+4xy^4+12y^5 =33\]
    

     geen oplossingen heeft voor gehele waarden van x en y. We stellen onmiddellijk vast dat x en y zeker verschillend van nul moeten zijn.
    2. 

  2. Er bestaan  geen algemene methoden om een vijfde graads vergelijking op te lossen. We zouden  eventueel x^5+3x^4y-5x^3y^2-15x^2y^3+4xy^4+12y^5 -33 kunnen proberen te ontbinden in factoren om zo bovenstaande vergelijking op te lossen. Maar dit lukt niet.
    3. 

  3. Maar de uitdrukking x^5+3x^4y-5x^3y^2-15x^2y^3+4xy^4+12y^5 kunnen we wel ontbinden als

          \[(x-2y)(x-y)(x+y)(x+2y)(x+3y)\]
    

    4. 

  4. Het probleem wordt dus herleid tot : bewijs dat (x-2y)(x-y)(x+y)(x+2y)(x+3y)=33   geen oplossingen heeft voor gehele waarden van x en y.
    5. 

  5. Nu  heeft 33 als delers \pm1, \pm 3,\pm 11,\pm 33. We kunnen 33 dus hoogstens schrijven als het product van 4 verschillende gehele getallen ( vier positieve ofwel 2 negatieve en 2 positieve). Omdat x en y geheel moeten zijn is het linkerlid van vorige vergelijking steeds het product van 5 verschillende gehele getallen.
    6. 

  6. Bijgevolg heeft de vorige vergelijking geen oplossingen voor gehele waarden van x en y.
    7.