Tag archieven: problem solving

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}.

Opgave 5

Geplaatst op door

Voor welke waarde van m \in \mathbb{N}_0 is x^{3m}+x^{2m}+x^m+1 deelbaar door x^3+x^2+x+1?

Antwoord

  1. Een veelterm A is deelbaar door een veelterm B als alle nulwaarden van B ook nulwaarden zijn van A.
  2. Nu is B=x^3+x^2+x+1=(x+1)(x^2+1), dus de nulwaarden van B zijn :-1,i,-i.
  3. Omdat A=x^{3m}+x^{2m}+x^m+1 enkel gehele coëfficiënten heeft kunnen we de stelling van d’Alembert gebruiken die zegt dat als a+bi een nulwaarde is, dan is a-bi dat ook.
  4. We moeten dus enkel  eisen dat -1 en i nulwaarden zijn van A.
  5. Dan moet (-1)^{3m}+(-1)^{2m}+(-1)^m+1=0 of (-1)^m+1+(-1) ^m+1=2+2(-1) ^m=0. Hieruit volgt dat m oneven moet zijn.
  6. Verder moet ook i^{3m}+i^{2m}+i^m+1=0. Dus moet (-i)^m+(-1) ^m+i^m+1=0. Als m=4k dan is A(i) \neq 0. In alle andere gevallen is A(i) wel gelijk aan 0.
  7. De twee voorwaarden samen geven dat m gewoon oneven moet zijn.
  8. Dus is x^{3m}+x^{2m}+x^m+1 deelbaar door x^3+x^2+x+1=(x+1)(x^2+1 als m oneven is.

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.

 

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.