Tag archieven: pariteit

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.

Pariteit

Geplaatst op door

Het feit dat een gegeven even of oneven is kan belangrijk zijn om de oplossing van het probleem te vinden. Het even of oneven zijn van een getal noemen we de pariteit  van het getal. Deze heuristiek wordt dikwijls gebruikt in combinatie met kleuringen of het invariantie principe.

Neem 2017 punten op een cirkel en verbind ze tot ze een 2017-hoek vormen. Elke zijde van deze 2017-hoek krijgt een ‘lading’: +1 of -1. Bewijs dat er altijd een hoekpunt moet zijn, zodat het product van de ladingen van de zijden die samenkomen in dat punt, gelijk is aan +1.

  • Neem een willekeurige zijde en geef die lading +1. Dit kan, want als alle ladingen -1 zouden zijn is het gestelde zeker al bewezen. Het rechtse eindpunt van de zijde noemen we H_1.
  • Ga rechtsom en neem de volgende zijde. Is de lading +1 dan is H_1 een hoekpunt dat aan de voorwaarde voldoet. Dus veronderstel dat de lading -1 is.
  • Je gaat zo steeds verder. Ofwel vindt je twee maal na elkaar eenzelfde lading, en dan is de stelling bewezen. Ofwel alterneren de ladingen +1 en -1 elkaar. Omdat 2017 oneven is zal de laatste zijde lading +1 hebben en is de stelling ook dan bewezen.
  • Je kan het probleem ook oplossen door P_i te definiëren als het product van de ladingen die in hoekpunt H_i samenkomen. Het product van alle P_i’s moet +1 zijn, omdat alle zijden twee keer geteld worden in dit product. Omdat we een oneven aantal hoekpunten hebben kunnen niet alle P_i’s gelijk zijn aan -1. Er is dus minstens één hoekpunt, zodat het product van de ladingen van de zijden die samenkomen in dat punt, gelijk is aan +1.