Tag archieven: problem solving

Invariantieprincipe

Geplaatst op door

De problemen die we nu zullen bestuderen gaan over processen die zich in een aantal toestanden kunnen bevinden. Laten we voor een gegeven probleem die toestanden even t_{begin},t_1,... noemen. De overgang van de ene toestand naar de andere toestand is eenduidig vastgelegd door een aantal spelregels. Uiteindelijk is de vraag of het mogelijk is van toestand t_0 naar een eindtoestand t_{eind} te gaan door de regels te gebruiken. Een strategie om aan te tonen dat dit onmogelijk is, is gebruik te maken van een functie f die gedefinieerd is op de verschillende toestanden van het probleem en die bij de overgang van de ene toestand naar de andere niet van waarde verandert. De functie blijft invariant gedurende het hele proces. Als uiteindelijk blijkt dat f(t_{begin}) \neq f(t_{eind}) kunnen we besluiten dat het onmogelijk is om van de begintoestand naar de eindtoestand te komen door gebruik te maken van de spelregels.

Een voorbeeld:

Een draak heeft 100 hoofden. Een ridder kan er 15,17,20 of 5 afhakken. maar als hij dat doet, dan groeien er onmiddellijk 24,2,14 of 17 nieuwe hoofden bij. Als alle hoofden er af zijn dan is de draad dood. Kan de ridder de draak doden?

Spoiler

 

Oneindige afdaling

Geplaatst op door

Een bewijs door  oneindige afdaling  is een manier van bewijzen die kan worden toegepast bij aftelbare welgeordende verzamelingen, meestal de natuurlijke getallen. Men bewijst het niet bestaan van een element uit een verzameling met een bepaalde eigenschap, door aan te tonen dat als er zo een element zou bestaan, er ook een kleiner element moet bestaan met die eigenschap. Zo ontstaat een oneindige keten van elementen kleiner dan het veronderstelde element, terwijl er maar eindig veel van dergelijke elementen zijn. Fermat was één van de eersten die deze methode veelvuldig gebruikte.

Een voorbeeld:

Vind alle oplossingen in positieve gehele getallen van x^2+y^2=3(z^2+w^2)

Bewijs:

Stel (x,y,z,w) een oplossing van de gegeven vergelijking waarbij x minimaal is. Omdat 3 een deler is van het rechterlid , moet 3 ook een deler zijn van x^2+y^2. Omdat kwadraten 0 of 1 modulo 3 zijn, kan x^2+y^2 alleen maar deelbaar zijn door 3 als x en y zelf deelbaar zijn door 3. Dus x=3x' en y=3y'. Ingevuld geeft dit 3(x'^2+y'^2)=z^2+w^2. Analoog vinden we dat z=3z' en w=3w', waardoor x'^2+y'^2=3(z'^2+w'^2). Dus is (x',y',z',w') ook een oplossing van de gegeven vergelijking met x'<x. Dit levert een tegenspraak en dus heeft de vergelijking geen oplossingen in de verzameling van de positieve gehele getallen.

Extremaal principe

Geplaatst op door

In essentie betekent deze methode niet meer of minder dan het bekijken van de  meest extreme situatie die zich kan voordoen of zou moeten kunnen voordoen. Als je ooit om een of andere reden het niet bestaan van bepaalde objecten wil aantonen, bijvoorbeeld van het maximum van een verzameling, zal deze techniek zeker een nuttig hulpmiddel zijn. Je bepaalt een verzameling objecten en selecteert een object waarbij een bepaalde eigenschap minimaal of maximaal is. Werk verder tot je een tegenspraak krijgt.

Bekijken we eens een voorbeeld: In een groep van n personen zijn er steeds twee die binnen deze groep evenveel vrienden hebben. We veronderstellen dat vriendschap wederzijds is.

vrienden

Veronderstel dat ze allemaal een verschillend aantal vrienden hebben. Vermits er n personen zijn en omdat iemand maximaal n-1 vrienden kan hebben, hebben die n personen respectievelijk 0,1,2,...,n-1 vrienden. Bekijken we het extreme geval dat iemand dus n-1 vrienden heeft. Met andere woorden hij is met iedereen bevriend. Maar omdat vriendschap wederzijds is, heeft iedereen dus minstens 1 vriend. Bijgevolg is er niemand met 0 vrienden. Dit geeft onze tegenpraak en bijgevolg zijn er minstens twee personen met evenveel vrienden.

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.

					

		
		
	


				
					
	

		

						
Problemen?

			
						

				Geplaatst op   door  			

			
					


				

			
Terwijl de meeste mensen problemen liever uit de weg gaan, worden wiskundigen er juist onweerstaanbaar door aangetrokken.


Lijsten met problemen zijn geen nieuw verschijnsel inde wiskunde. In de Griekse oudheid had men de drie klassieke problemen over constructies met passer en liniaal ( de verdubbeling van de kubus, de kwadratuur van de cirkel en de driedeling van een hoek).


kwadratuur


Befaamd zijn ook de 23  problemen die David Hilbert zijn gehoor voorlegde  in 1900 op het tweede internationaal Wiskunde Congres in Parijs : de millennium problemen. Nu, ruim een eeuw later, zijn de meeste van de 23 problemen van Hilbert opgelost.


hilbert


Zo een lijst met problemen kan je bekijken als een uitbreidingsplan voor het bouwwerk van de wiskunde. Hilberts lijst was een bouwplan voor een hele eeuw, op wereldschaal.


Op kleinere schaal bestaan er ook veel lijsten met problemen. We kunnen die beschouwen als een uitbreidingsplan van onze eigen wiskunde kennis. De ervaring die we opdoen bij het behandelen van die problemen verruimt onze wiskunde ervaring. In dit deel van deze blog willen we technieken en voorbeelden aanreiken om een betere probleemoplosser te worden.