Tag archieven: probleem oplossend denken

Opgave 19

Geplaatst op door

Controleer voor elk natuurlijk getal vanaf 7 of {n} \choose {7} deelbaar is door 12 en bereken de fractie van dergelijke getallen. Zoek de limiet van die fractie als je steeds meer getallen controleert.

Antwoord
  • We weten dat {n} \choose {7} = \dfrac{n!}{7!(n-7)!}=\dfrac{n(n-1)\cdots(n-6)}{2^4.3^2.5.7}
  • Om deelbaar te zijn door 12 moet de teller deelbaar zijn door {2^6.3^3.5.7}. Omdat de teller betsaat uit zeven opeenvolgende getallen is die zeker al deelbaar door 7 en 5.
  • Bekijken we nu de factoren 3. De teller is zeker deelbaar door 9, want zeven opeenvolgende getallen bevatten zeker twee veelvouden van 3.
  • Als n \equiv 0,1,2,3,4,5 \text{ of } 6 \text{ mod } 9, dan is zeker één van de zeven getallen uit de teller deelbaar door 9 en een ander door 3, zodat de teller deelbaar is door 3^3.
  • Nu de factoren 2: Als n even is dan zijn n,n-2,n-4 en n-6 allemaal deelbaar door 2 en juist twee getallen zijn een viervoud, zodat de teller dan deelbaar is door 2^6.
  • Als n oneven is dan zijn n-1,n-3 en n-5 deelbaar door 2. Als n-3 het enige getal is dat deelbaar is door 4, dan moet het zelfs deelbaar zijn door 16 anders kan de teller niet deelbaar zijn door 2^6. Dus moet n \equiv 3 \text{ mod } 16. Als n-1 en n-5 beiden deelbaar zijn door 4, dan moet opdat de teller  deelbaar zou  zijn door 2^6, een van die getallen deelbaar zijn door 8. Dus moet n \equiv 1,5 \text{ mod } 8 of n \equiv 1,5,9,13 \text{ mod } 16.
  • Brengen we nu alle informatie samen: {n} \choose {7} is deelbaar door 12 als en slechts als

        \[\begin{cases} n \equiv 0,1,2,3,4,5,6 \text{ mod } 9 \\ n \equiv 0,1,2,3,4,5,6 ,8,9,10,12,13,14 \text{ mod } 16\]

  • Er zijn 7 mogelijkheden modulo 9 en 13 mogelijkheden modulo 16, dus zijn er volgens de Chinese reststelling 9.13=91  oplossingen modulo 9.16=144.
  • De waarschijnlijkheid dat {n} \choose {7}  deelbaar is door 12 nadert dus de waarde \frac{91}{144}.

Opgave 15

Geplaatst op door

Zoek het algemeen voorschrift van de rij a_{n+1}-2a_n=F_n met a_0=0, waarbij F_n de rij van Fibonacci is met F_0=0,F_1=1,F_2=1,...

Antwoord

  • Het rechterlid van de formule is niet nul, zodat we geen lineaire recurrente rij krijgen. Maar dat kunnen we verhelpen door ook te schrijven dat  a_{n+2}-2a_{n+1}=F_{n+1} en a_{n+3}-2a_{n+2}=F_{n+2}.
  • De laatste vergelijking verminderd met de vorige en de opgave geeft, gebruikmakend van de eigenschappen van de rij van Fibonacci, dat a_{n+3}-3a_{n+2}+a_{n+1}+2a_n=0.
  • De karakteristieke vergelijking van deze lineaire recurrentie is x^3-3x^2+x+2=(x-2)(x^2-x-1). Volgens de theorie van de lineaire recurrente rijen is dan a_n=A.2^n+B.\alpha^n+C.\beta^n. Hierbij is \alpha=\dfrac{1+\sqrt{5}}{2} en \beta=\dfrac{1-\sqrt{5}}{2}. We weten, ook door gebruik te maken van de theorie van de lineaire recurrentie, dat F_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}.
  • In a_n=A.2^n+B.\alpha^n+C.\beta^n, bepalen we A,B en C door gebruik te maken van a_0=0,a_1=0 en a_2=1. We vinden A=1, B=-\dfrac{\alpha^2}{\alpha-\beta} en C=\dfrac{\beta^2}{\alpha-\beta}.
  • Bijgevolg is a_n=2^n-F_{n+2}.

Opgave 14

Geplaatst op door

Op de zijden van een rechthoekige driehoek ABC tekent men twee vierkanten: BGFC en AEDC. De rechten AG en BE snijden elkaar in I. Verder is H het snijpunt van AG met BC en J het snijpunt van BE met AC. Bewijs dat de oppervlakte van ABI gelijk is aan de oppervlakte van IHJC.

Antwoord

  • We maken eerst een tekening
  • We kunnen beter bewijzen dat de oppervlakte van de driehoeken ABH en BJC dezelfde zijn door bij de opgave de oppervlakte van BIH toe te voegen aan beide delen.
  • Dus moet |BH|.|AC|=|JC|.|BC| of \dfrac{|AC|}{|BC|}=\dfrac{|JC|}{|BH|}.
  • Nu zijn de driehoeken ACH en BGH gelijkvormig (HH= rechte hoek en overstaande hoeken), dus geldt \dfrac{|AC|}{|BC|}=\dfrac{|HC|}{|BH|}. Bijgevolg rest ons te bewijzen dat |JC|=|HC|.
  • Ook driehoeken BJC en BED zijn gelijkvormig ( HH= gemeenschappelijke hoek en rechte hoek), dus is \dfrac{|JC|}{|ED|}=\dfrac{|BC|}{|BD|} of |JC|.|BD|=|BC|.|ED|. Bijgevolg is |JC|.(|BC|+|AC|)=|BC|.|AC|.
  • Uit de gelijkvormigheid van de driehoeken AHC en AGF volgt op een analoge wijze dat |HC|.(|BC|+|AC|)=|BC|.|AC|.
  • Uit de twee laatste  formules volgt dan inderdaad dat |JC|=|HC|, net wat we wilden bewijzen.

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.

 

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.