Valse munten

Je hebt 10 stapels van 10 munten. Elke munt  van 9 van die stapels weegt 6 gram? Maar de munten van de 10de stapel wegen elk maar 5 gram. Hoe kan je met slechts 1 weging weten in welke stapel de munten van 5 gram zitten?

Antwoord

  • Neem van de eerste stapel 1 muntstuk, van de tweede stapel 2 muntstukken, van de derde stapel 3 munten, ….. en van de tiende stapel 10 munten.
  • Je hebt dan 1+2+3+…+10 = 55 munten genomen.
  • Als ze elk 6 gram zouden wegen , is het totale gewicht 6 x 55 = 330 gram.
  • Weeg nu de 55 munten. Het gewicht minder dan 330 gram geeft aan welke stapel de munten van 5 gram bevat. Want stel dat de 55 munten 327 gram wegen, dan zijn er drie munten bij van 5 gram. Drie munten heb je genomen van de  derde stapel. Dus stapel drie heeft de munten van 5 gram.

Les 5: Diophantische vergelijkingen en modulo rekenen

Als twee gehele getallen gelijk zijn, dan zijn hun resten bij deling door een zelfde natuurlijk getal, verschillend van nul, ook gelijk. Of via contrapositie: als er tenminste 1 natuurlijk getal n bestaat waarvoor a \neq b \mod n, dan zal ook a verschillend zijn van b.

Proberen we eens met

    \[2x^2-3y^2-9463=0\]

  • Herschrijf tot 2x^2-3y^2=9463.
  • We bepalen de resten van beide leden bij deling door 3: 2x^2-3y^2\equiv 9463 \mod 3.
  • Of 2x^2\equiv 1 \mod 3.
  • Het inverse element, modulo 3, van 2 is 2 zelf, dus kunnen we vorige  vergelijking herschrijven als

        \[x^2\equiv 2 \mod 3\]

  • Nu is 2 geen kwadraatrest modulo 3, want 0^2=0,1^2=1 en 2^2=1.
  • Bijgevolg heeft de gegeven vergelijking geen oplossingen.

Les 4: ontbinding en exhaustie

Bij Diophantische vergelijkingen van een hogere graad kan je via ontbinding in factoren dikwijls de oplossing vinden. Neem bijvoorbeeld:

    \[3x^2-4xy+5=0\]

  • We kunnen deze vergelijking herschrijven als

        \[x(3x-4y)=-5\]

  • Als x en y gehele getallen zijn, dan moeten x en 3x-4y delers zijn van -5.
  • We kunnen gemakkelijk alle mogelijkheden opschrijven: 

        \[\begin{array}{c|c|c} x&3x-4y&y \\ \hline \\1&-5&2\\-1&5&-2\\5&-1&4\\-5&1&-4\end{array}\]

  • We hebben dus als oplossingen (1,2),(-1,-2),(5,4),(-5,-4).

 

Les 3: Stelsels Diophantische vergelijkingen

We lossen één van de vergelijkingen op en vullend die dan in de andere in, waardoor er een verband ontstaat tussen de parameters. Neem bijvoorbeeld:

    \[\left\{\begin{matrix} 3x-6y+16z=1\\2x+5y-6z=2\end{matrix}\right\]

  • Uit les 2 weten we dat de oplossing van de eerste vergelijking gegeven wordt door  x=5+16t+2v, y=5+16t+v, z=1+3t.
  • Invullen in de tweede vergelijking geeft: 2(5+16t+2v)+5(5+16t+v)-6(1+3t)=2. Na uitwerking vinden we 94t+9v=-27.
  • Dit is een Diophantische vergelijking met slechts twee onbekenden. De oplossingen hangen af van 1 parameter w: t=54-9w en v=-567+94w.
  • Brengen we deze waarden in bij de oplossingen van de eerste vergelijking van het stelsel, dan vinden we :

        \[\left\{\begin{matrix}x=-265+44w\\y=302-50w\\z=163-27w\end{matrix}\right\]

Les 2: ax+by+cz=d

Omdat ggd(a,b,c) = ggd( ggd(a,b),c) kunnen we recursief werken. Neem als voorbeeld de vergelijking

    \[3x-6y+16z=1\]

  • Herschrijf deze vergelijking als 3(x-2y)+16z=1.
  • Stel x-2y=u, dan wordt de gegeven vergelijking 3u+16z=1.
  • Gebruikmakend van de techniek uit les 1 vinden we dat u=-5-16t en z=1+3t, met t een willekeurig geheel getal.
  • Met dezelfde methode kunnen we via x-2y=1, de oplossing van x-2y=u schrijven als x=-u+2v en y=-u+v met v een geheel getal.
  • Na eliminatie van u vinden we dus dat x=5+16t+2v, y=5+16t+v en z=13t. Dit zijn alle gehele oplossingen van de gegeven vergelijking. Deze hangen af van 2 parameters.