Tag archieven: invariantie principe

Opgave 41

Geplaatst op door

Veronderstel dat n een oneven getal en schrijf dan op een blad papier alle  natuurlijke getallen 1,2,3,…., 2n. Dan laat je er twee willekeurige getallen hieruit kiezen  en schrap ze en schrijf erbij het verschil van het grootste men het kleinste van die twee getallen. Toon aan dat, bij herhaling, het laatste overblijvende getal zeker oneven is.

Antwoord

  • Noteer met S de som van alle opgeschreven getallen. Dan is S=1+2+…+2n of

        \[S=n(2n+1)\]

  • Dus S is oneven omdat n oneven is en 2n+1 ook.
  • Neem nu twee willekeurig neergeschreven getallen a en b  en stel a>b , dan wordt de nieuwe som S'=S-a-b+a-b=S-2b. Omdat je een even getal aftrekt van een oneven S, zal de nieuwe som S’ ook oneven zijn. Voor het geval dat a<b is dit analoog.
  • De pariteit van de som van alle nog beschikbare getallen is dus een invariante. Met andere woorden, telkenmale we twee getallen schrappen en vervangen door het verschil blijft de som oneven.
  • Dus het laatst overgebleven getal is oneven.

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.