Tag archieven: pariteit

nootje 65

Geplaatst op door

Zoek het kleinste natuurlijk getal groter of gelijk aan 10 waarvoor n+6 priem is en 9n+7 een volkomen kwadraat is.

Antwoord

  • 9n+7=9(n+6)-47 .
  • n+6 is een priemgetal groter dan 2 en is dus oneven; bijgevolg is 9(n+6)-47 een even getal als verschil van twee oneven getallen.
  • Omdat 9n+7 een volkomen kwadraat moet zijn, moet 9n+7=(2m)^2.
  • Hieruit volgt dat n=\frac{4m^2-7}{9}.
  • Onderzoeken we nu voor welke waarden van m de uitdrukking 4m^2-7 deelbaar is door 9 en waarvoor dan een goede n kan worden gevonden.
  • Als m=2 dan is n=1 wat onmogelijk is, omdat n minstens 10 moet zijn. 
  • Als m=7 dan is n=21, maar dan is n+6=27 en dat is geen priemgetal.
  • Als  m=11 dan is n=53 en n+6=59 en dat is wel priem.
  • n=53 is  het kleinst mogelijke getal dat voldoet aan de gevraagde voorwaarden.

 

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!