Tag archieven: pariteit

Opgave 39

Geplaatst op door

Bewijs dat geen enkel getal van de vorm

    \[3^m+3^n+1\]

met m en n strikt positieve gehele getallen, een volkomen kwadraat is.

Antwoord

  • Veronderstel dat er toch een natuurlijk getal k bestaat zodat

        \[3^3+3^n+2=k^2\]

  • Dan is 3^m+3^n=(k+1)(k-1). Omdat het linkerlid even is en omdat k-1 en k+1 dezelfde pariteit hebben, zijn k-1 en k+1 opeenvolgende even getallen.
  • Dit betekent ook dat ofwel k-1 ofwel k+1 een viervoud is. Het rechterlid (k-1)(k+1) is dus deelbaar door 8.
  • Bij deling door 8 zijn de resten van machten van 3 ofwel 1 ofwel 3. De som 3^m+3^n is dus modulo 8, gelijk aan 2,4 of 6 en dus zeker niet deelbaar door 8.
  • Bijgevolg kan 3^m+3^n+1 nooit een volkomen kwadraat zijn.

Pariteit van een permutatie

Geplaatst op door

Elke permutatie kan geschreven worden als het product ( samenstelling) van transposities. Een transpositie of omwisseling is een twee-cykel, zoals bijvoorbeeld (12).

Dit product kan op verschillende manieren tot stand komen, maar het is wel zo dat het aantal transposities dat je nodig hebt, steeds hetzelfde is. Als dat aantal even is , spreken we van een even permutatie. Als het aantal oneven is , spreken we van een oneven permutatie.  Dit noem je de pariteit van de permutatie

Een voorbeeldje van een oneven permutatie:

    \[(1234) =(14)(13)(12)\]

    \[(1234)=(12)(23)(34)\]

Let op de volgorde! Zoals bij de samenstelling , werken we van achter na voor. Nog een paar voorbeelden met afbeelding:

 

is een even permutatie, want de permutatie is te schrijven als (16)(15)(13)(28)(27)(24).

is een oneven permutatie, want de permutatie is te schrijven als (14)(32)(35)

 

Schuifpuzzel

Geplaatst op door

 

De schuifpuzzel is een puzzel, meestal op een bord van 4  op 4 met 15 verschillende stukken en 1 leeg veld; Het wordt dan ook   15-puzzel genoemd, maar bestaat ook in andere afmetingen. De bedoeling is om de stukken terug in de goede volgorde te krijgen door de stukken te schuiven.

De oorspronkelijke versie van dit spel werd in 1874 ontwikkeld door de New Yorkse postdirecteur Noyes Palmer Chapman. De vierkantjes zaten los en de speler kon ze in willekeurige volgorde neerleggen en dan proberen de puzzel door schuiven op te lossen. In de afbeelding hierboven uit Sam Loyds Cyclopedia waren in de beginpositie de getallen 14 en 15 van plaats gewisseld. 

Niet elke beginpositie is oplosbaar. Wiskundigen hebben onderzocht welke beginopstellingen kunnen worden opgelost. Neem bijvoorbeeld bovenstaande puzzel, beter afgebeeld als:

Is dit oplosbaar?

Twee speltoestanden worden als equivalent gedefinieerd als de ene door een aantal malen schuiven in de andere kan worden overgevoerd. Deze relatie is een equivalentierelatie.  Of  de puzzel oplosbaar is betekent dus of bovenstaande schikking equivalent is met de begintoestand. Men kan aantonen dat twee speltoestanden equivalent zijn als de pariteit van de permutatie van de 16 elementen die de ene in de andere overvoert gelijk aan die van de ‘afstand’  tussen de lege velden van de twee speltoestanden (dit betekent dat de twee lege velden zoals bij een schaakbord dezelfde of een verschillende kleur hebben). Wat geeft dit nu voor onze opgave?

  • de lege vakken staan in begin en eind situatie opdezelfde plaats: dus pariteit 0
  • De eindsituatie wordt bekomen uit de beginsituatie via 1 transpositie ( 1 omkering: 14 versus 15); Dus is de permutatie oneven en heeft pariteit 1.
  • De twee pariteiten zijn verschillend en dus is de puzzel onoplosbaar. Er werd dus ten onrechte een prijs van 1000$ uitgereikt voor de oplossing!

 

Uitdaging 3 en 4

Geplaatst op door

Voor welke waarden van k is x^3+y^3+z^3+kxyz deelbaar door x+y+z?

Antwoord

  • Als x^3+y^3+z^3+kxys deelbaar is door x+y+z, dan bestaat er een Q(x,y,z) zodat

        \[x^3+y^3+z^3+kxyz=(x+y+z)Q(x,y,z)\]

  • Vervang nu in beide leden x door 2, en y en z door -1, dan vind je 8-1-1+2k=0 of m.a.w. k=-3.

Een veelterm f(x)  met gehele coëfficiënten heeft oneven getalwaarden voor 0 en 1. Bewijs dat  f(x) geen gehele nulwaarden kan hebben.

Antwoord

  • Noteer de veelterm f(x)=a_nx^n+\cdots+a_1x+a_0.
  • Omdat f(0) oneven is moet a_0 een oneven getal zijn.
  • Omdat f(1) even is moet a_n+\cdots+a_1+a_0 ook oneven zijn.
  • Stel nu dat c een gehele nulwaarde is van f(x), dan is a_nc^n+\cdots+a_1c+a_0=0.
  • Als c even is dan is het linkerlid van deze ongelijkheid oneven en kan dus nooit nul zijn.
  • Als c oneven is, dan krijgen we modulo 2 dat a_n+\cdots+a_1+a_0 \equiv 0. Maar ook dat is onmogelijk want het linkerlid is oneven en kan dus nooit  nul zijn.
  • Dus heeft f(x) geen gehele nulwaarden.