Homepage
April 2014
Betrakta ordet APRIL. Ett trebyte är när tre bokstäver i ordet roteras, t.ex. PIRAL, där A,P och I bytte plats. Kan man genom trebyten få PARIL från APRIL? (Problemet föreslogs av E. Vigren.)
Lösning
Vi skriver om problemet m.h.a. siffror istället för bokstäver.
Vi vill alltså använda trebyten för att från 12345 komma till 21345.
Betrakta nu alla möjliga omordningar (permutationer) av 12345.
(Visa att de är 120 stycken!)
Vi delar dem i två grupper:
En permutation är udda om den har ett udda antal "felvända" par:
i 21453 är paren 21, 43 och 53 "felvända", så permutationen är udda.
Annars är den jämn.
Nu kollar vi vad ett trebyte gör. Det består av två platsbyten. Ett
antal trebyten motsvarar alltså ett jämnt antal platsbyten. Vi skall
nu se att ett platsbyte alltid förvandlar en udda permutation till en
jämnt, och omvänt:
Antag att talen x och y byter plats. Då påverkas följande talpar:
1. Om talparet xy var felvänt, så blir det rättvänt nu. Och omvänt.
2. Om z är ett tal på en position mellan x:s och y:s positioner, så är
exakt ett av paren xz och yz felvänt. Efter platsbytet mellan x och y
blir det andra paret felvänt. I vilket fall som helst, så ändras inte
antalet sådana felvända par.
3. Övriga talpar påverkas inte av platsbytet.
Vi har nu sett att vid ett platsbyte minskar eller ökar antalet
felvända par med ett, det går alltså från udda till jämnt eller
tvärtom.
Detta betyder också att ett eller flera trebyten (som ju
består av två platsbyten) antingen går mellan endast udda eller endast
jämna permutationer. Men att gå från 12345 till 21345 är att gå från
en jämn till en udda permutation. Det kan alltså inte åstadkommas med
endast trebyten.
Sidansvarig: jana.bjorn@liu.se
Senast uppdaterad: 2019-12-03