Categorie archieven: Geen categorie

Heuristiek : Blikwissel

Geplaatst op door

Door onze wiskundige ervaring beperken we ons soms tot die oplossingsmethoden die in het verleden steeds gewerkt hebben. Daardoor zie je soms een eenvoudige uitkomst over het hoofd. Een belangrijke heuristiek is bijgevolg: het probleem op een andere manier bekijken. We noemen dit blikwissel.

We doen alsof we de oplossing hebben en werken zo terug tot we terechtkomen bij een situatie die we wel meester zijn. We proberen een omgekeerde redenering op te zetten door van achter naar voor werken. We leven ons in in de personen, dieren, zaken die in de vraag voorkomen en bekijken het probleem eens vanuit hun standpunt. We kijken naar andere dingen, die niet rechtstreeks gevraagd zijn. We vragen ons af wat de voorlaatste stap van de oplossing zou kunnen zijn.

Bekijken we volgend voorbeeld:

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

 emmers

We vragen ons af wat de voorlaatste stap van de oplossing zou kunnen zijn. Om 6 liter in de emmer van 9 liter over te houden, willen we die helemaal vullen en er 3 liter uit wegnemen. Dit lukt als we in de kleine emmer 1 liter water hebben staan. Hoe kunnen we nu 1 liter maken met deze twee emmers? Nu is 1=9-4-4. Onze strategie is dus:

  • Vul de grote emmer.
  • Vul hiermee de kleine emmer en ledig die. Je hebt dus 4 liter uit de grote emmer weggegoten.
  • Giet nogmaals 4 liter van de grote emmer in de kleine en ledig die weer.
  • Giet de overblijvende liter in de kleine emmer.
  • Vul de grote emmer met 9 liter.
  • Giet van de grote emmer zoveel water over tot de kleine emmer helemaal gevuld is.
  • Nu blijft er 6 liter over in de grote emmer.

					

		
		
	


				
					
	

		

						
Bewijs door inductie

			
						

				Geplaatst op   door  			

			
					


				

			
domino
Vaak bestaat een probleem erin aan te tonen dat een bepaalde 
eigenschap geldt voor elk natuurlijk getal.
Als je wilt weten of iets waar is voor alle natuurlijke 
getallen n (dus voor n = 1, 2, 3, . . .), kun je ze niet 
allemaal afgaan: daar zou je oneindig lang mee bezig zijn. 

Inductie is eigenlijk een verzameling van bewijstechnieken 
die de waarheid van een stelling voor alle elementen van een 
verzameling aantonen door gebruik te maken van de onderliggende 
structuur van de verzameling. 

Om de geldigheid te bewijzen van een uitspraak van de vorm 
" Voor ieder natuurlijk getal n geldt P(n)", 
waarbij P(n) staat voor een bewering  (propositie) waarin n 
voorkomt, maakt men vaak gebruik van deze  methode. 
Lees  meer hierover in volgend artikel, waar een paar 
voorbeelden worden uitgewerkt en waar ook een heleboel opgaven staan.



					

		
		
	


				
					
	

				
					
	

		

						
Modulorekenen

			
						

				Geplaatst op   door  			

			
					


				

			
De eindige rekenkunde, ook wel modulaire rekenkunde genoemd, wordt beschreven in het boek Disquisitiones Arithmeticae van Gauss, een buitengewoon invloedrijk werk uit 1801, toen de auteur nog maar vierentwintig jaar oud was.


dis


Stel a,b,m \in \mathbb{Z},m>1. Indien a en b bij deling door m dezelfde rest geven, d.w.z. indien a-b=cm voor zekere c \in \mathbb{Z}, heten a en b congruent modulo m. We noteren a\equiv b mod m.Zo is bijvoorbeeld  3\equiv 63 mod 5, 7\equiv -1 mod 8 en 12^2\equiv 1 mod 13.


Enkele eigenschappen :


    

  • Als a\equiv b mod m en b\equiv c mod m, dan is a\equiv c mod m.
    • 

  • Als a\equiv b mod m en c\equiv d mod m, dan is a+c\equiv b+d mod m.
    • 

  • Als a\equiv b mod m en n \in \mathbb{N}, dan is a^n\equiv b^n mod m.
    • 

  • Als a\equiv b mod m dan is voor elke c \in \mathbb{Z} : ac\equiv bc mod m.
    • 

  • Als a\equiv b mod m en c\equiv d mod m, dan is ac\equiv bd mod m.
    • 



Rekenen met congruenties lijkt erg op het rekenen met vergelijkingen. Er is echter een belangrijk verschil: uit ac\equiv bc mod m met c\neq 0 mod m hoeft niet te volgen dat a\equiv b mod m. Zo is 6.12\equiv 6.7 mod 10 maar 12 is niet congruent met 7 modulo 10. In andere gevallen gaat het wel op. De voorwaarde waarop de vereenvoudiging met c wel kan, is dat c onderling ondeelbaar is met m.

Dus als ac\equiv bc mod m en ggd(c,m) = 1, dan is a\equiv b mod m.

Als ggd(c,m) = d, dan volgt uit ac\equiv bc mod m dat a\equiv b mod( \frac{m}{d}).


Rekent men modulo m, dan zijn er m verschillende soorten getallen, al naar gelang ze verschillende resten geven bij deling door m. De verzameling van alle gehele getallen die eenzelfde rest geven heet een restklasse modulo m. Er zijn dus precies m verschillende restklassen modulo m. De restklasse die een getal a bevat, noteert men als \overline{a}. Deze notatie is natuurlijk niet eenduidig bepaald, want als a\equiv b mod m, stellen \overline{a} en \overline{b} dezelfde restklasse modulo m voor en omgekeerd.


Werken we modulo 4 dan is \overline{0}=\left\{0,4,8,12,\cdots}\right\}, \overline{1}=\left\{1,5,9,13,\cdots\right\}, \overline{2}=\left\{2,6,10,14,\cdots\right\}, \overline{3}=\left\{3,7,11,15,\cdots\right\} .


Men kan in de verzameling restklassen modulo m, genoteerd door \mathbb{Z}_m, een optelling en een vermenigvuldiging defini\”eren via \overline{a}+\overline{b}=\overline{a+b} en \overline{a}.\overline{b}=\overline{ab}. Deze rekenregels lijken erg op de regels van optelling en vermenigvuldiging van gehele getallen.


Eigenschappen :


    

  • \forall \overline{a},\overline{b}\in \mathbb{Z}_m : \overline{a}+\overline{b}=\overline{b}+\overline{a}.
    • 

  • \forall \overline{a},\overline{b}\in \mathbb{Z}_m : \overline{a}.\overline{b}=\overline{b}.\overline{a}.
    • 

  • \forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : (\overline{a}+\overline{b})+\overline{c}=\overline{a}+(\overline{b}+\overline{c}).
    • 

  • \forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : (\overline{a}.\overline{b}).\overline{c}=\overline{a}.(\overline{b}.\overline{c}).
    • 

  • \forall \overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m : \overline{a}.(\overline{b}+\overline{c})=\overline{a}.\overline{b}+\overline{a}.\overline{c}.
    • 

  • \forall \overline{a}\in \mathbb{Z}_m : \overline{a}+\overline{0}=\overline{a}.
    • 

  • \forall \overline{a}\in \mathbb{Z}_m : \overline{a}.\overline{1}=\overline{a}.
    • 

  • Er is een unieke restklasse \overline{x} met \overline{a}+\overline{x}=\overline{0}, namelijk \overline{x}=\overline{-a}.
    • 



Veronderstel dat  we de rest willen bepalen van 73\times52 bij deling door 7. Omdat 73 \equiv 3 mod 7 en 52 \equiv 3 mod 7, moet 73\times52 \equiv 3\times 3 mod 7 \equiv 9 mod 7 \equiv 2 mod 7. Dus de rest bij deling van 73\times52 door 7 is 2. We moeten daarvoor het product niet uitrekenen.