Tag archieven: heuristieken

Gebruikmaken van de symmetrie

Geplaatst op door

Soms kan je, door gebruik te maken van de  symmetrie  in de tekening of de symmetrie van de gegevens, de opgave aanzienlijk vereenvoudigen.

Een voorbeeld: Los op in \mathbb{R}:

    \[(x+2013)(x+2014)(x+2020)(x+2021)=44\]

  • Dit is een vierdegraads vergelijking. Hiervoor kennen we geen algemene oplossingsmethode.
  • Dus: haakjes uitwerken en dan ofwel proberen te ontbinden in factoren ofwel de regel van Horner toepassen. Maar dit is niet aantrekkelijk want de getallen in de opgave zijn nogal groot.
  •  De getallen 2013,2014,2020 en 2021 liggen wel symmetrisch rond 2017!
  •  We vervangen x+2017 door een nieuwe variabele t. De opgave wordt nu:

        \[(t-4)(t-3)(t+3)(t+4)=44\]

    .

  • Dit kan je netjes uitrekenen tot:

        \[(t^2-16)(t^2-9)=44\]

  • Verder uitrekenen geeft: t^4-25t+100=0. Hieruit volgt dat t^2=20 of t^2=5.
  • De 4 oplossingen voor t zijn dan: \pm \sqrt{5} en \pm \sqrt{20}. En dus moet \newline x=-2017 \pm \sqrt{5} of x=-2017 \pm \sqrt{20}.

Zoek een patroon

Geplaatst op door

Soms is het erg nuttig om een verband te zoeken tussen de data in de opgave. Kan je een bepaald patroon terugvinden? Dit kan je op weg helpen om de oplossing te vinden van je probleem.

 

Een voorbeeld: f(x) is een veelterm is van graad 4 waarbij de coëfficiënt van x^4 gelijk is aan 1. Bovendien is f(-1)=-1, f(2)=-4, f(-3)=-9 en f(4)=-16. Bereken f(1)

We weten dat f(x)=x^4+ax^3+bx^2+cx+d. Uit de 4 gegevens kunnen we, via het oplossen van een stelsel, de 4 onbekenden a,b,c en d vinden. Eigenlijk is dat zelfs niet nodig, want we moeten enkel f(1) berekenen. Maar gelukkig zien we een patroon  opduiken: -1,2,-3 en 4 zijn allemaal nulwaarden van de veelterm g(x)=f(x)+x^2. Omdat f(x) en dus ook g(x) van de vierde graad is, moet g(x)=(x+1)(x-2)(x+3)(x-4). Bijgevolg is f(1)=g(1)-1^2=23.

 

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

Definieer de functie f die het aantal hoofden berekent modulo 3. Dan is f(t_{begin})=1. Als de ridder 15 hoofden afhakt, dan komen er 24 bij, dus -15+24=+9. De andere gevallen geven ons: -17+2=-15, -20+14=-6 en -5+17=+12. Het aantal hoofden dat verdwijnt of er bij komt is steeds een veelvoud van 3, dus verandert het aantal hoofden, modulo 3 niet. Met andere woorden f is invariant. Hieruit volgt dat f(t_{eind})=1 Maar als de draak dood is, zijn alle hoofden er af en zou f(t_{eind})=0. De draak kan dus niet verslagen worden.

 

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.