Az A. 734. feladat (2018. november)

A. 734. Tetszőleges, $\displaystyle 3$-mal nem osztható pozitív egész $\displaystyle m$-re tekintsük az $\displaystyle \{1,2,\ldots,m-1\}$ halmazon az $\displaystyle x\mapsto 3x\pmod{m}$ permutációt. Ez a permutáció néhány diszjunkt ciklusra bomlik; például $\displaystyle m=10$ esetén a ciklusok $\displaystyle (1\mapsto3\mapsto9 \mapsto 7\mapsto1)$, $\displaystyle (2\mapsto6\mapsto8\mapsto4\mapsto2)$ és $\displaystyle (5\mapsto5)$. Milyen $\displaystyle m$ számok esetén lesz a ciklusok száma páratlan?

(7 pont)

A beküldési határidő 2018. december 10-én LEJÁRT.

Megoldás. A megoldáshoz felhasználunk néhány ismert tényt permutációk paritásáról.

Legyen $\displaystyle \pi(x)=3x\pmod m$, a ciklusok száma $\displaystyle c$, a ciklusok hosszai $\displaystyle k_1,k_2,\ldots,k_c$; a feladatbeli példában $\displaystyle m=10$, $\displaystyle c=3$, $\displaystyle k_1=k_2=4$ és $\displaystyle k_3=1$. A ciklusokban az $\displaystyle 1,2,\ldots,m-1$ elemek mindegyike pontosan egyszer szerepel, tehát $\displaystyle k_1+\ldots+k_c=m-1$.

Jól ismert, hogy bármely $\displaystyle k$ hosszú $\displaystyle (x_1\mapsto x_2\mapsto\ldots\mapsto x_k\mapsto x_1)$ ciklus megkapható az $\displaystyle (x_1,x_2), (x_2,x_3) \ldots, (x_{k-1},x_k)$ cserék (transzpozíciók), tehát összesen $\displaystyle k-1$ transzpozíció egymás utánjaként, avagy szorzataként; a $\displaystyle \pi$ permutáció összesen $\displaystyle (k_1-1)+(k_2-1)+\ldots+(k_c-1)=m-c-1$ transzpozíció szorzata. A $\displaystyle \pi$ páros, illetve páratlan permutáció, ha az előállítása páros, illetve páratlan számú transzpozíció szorzataként lehetséges. A $\displaystyle c$ paritásának meghatározásához tehát elég $\displaystyle \pi$ paritását vizsgálni.

A $\displaystyle \pi$ paritásának meghatározásához az inverziószámának paritását fogjuk vizsgálni, azaz az olyan $\displaystyle (x,y)$ párok számát, amelyekre $\displaystyle 1\le x<y\le m-1$ és $\displaystyle \pi(x)>\pi(y)$. Legyen az inverzióban álló $\displaystyle (x,y)$ párok halmaza

$\displaystyle I = \big\{ (x,y): x<y, ~\text{és}~ \pi(x)>\pi(y) \big\};$

az $\displaystyle I$ elemszámának paritására van szükségünk.

Bontsuk fel $\displaystyle I$-t a következő halmazokra:

$\displaystyle A = \big\{ (x,y): ~ x<y, ~ \pi(x)>\pi(y) ~\text{és}~ x+y<m \big\},$

$\displaystyle B = \big\{ (x,y): ~ x<y, ~ \pi(x)>\pi(y) ~\text{és}~ x+y>m \big\},$

$\displaystyle C = \big\{ (x,m-x): ~ x<\tfrac{m}{2} ~\text{és}~ \pi(x)>\pi(m-x) \big\}.$

Látható, hogy minden $\displaystyle (x,y)$ inverzió az $\displaystyle A,B,C$ halmazok közül pontosan az egyikben szerepel, tehát $\displaystyle |I|=|A|+|B|+|C|$.

1. állítás: Az $\displaystyle (x,y)\mapsto (m-y,m-x)$ egy kölcsönösen egyértelmű megfeleltetés az $\displaystyle A$ és $\displaystyle B$ halmazok között, így $\displaystyle |A|=|B|$.

Bizonyítás: Vegyük észre, hogy bármely $\displaystyle 1\le x<m$ esetén $\displaystyle \pi(x)+\pi(m-x)\equiv3x+3(m-x)\equiv0\pmod{m}$. De mivel $\displaystyle 0<\pi(x)+\pi(m-x)<2m$, ez csak úgy lehet, ha $\displaystyle \pi(x)+\pi(m-x)=m$.

Ezek után bármely $\displaystyle (x,y)\in A$ esetén $\displaystyle m-y<m-x$ és $\displaystyle (m-y)+(m-x)>m$, valamint $\displaystyle \pi(m-y)=m-\pi(y)>m-\pi(x)=\pi(m-x)$, vagyis valóban $\displaystyle (m-y,m-x)\in B$. A megfordítás ugyanígy bizonyítható.

2. állítás: $\displaystyle C=\big\{(x,m-x): \tfrac{m}{6}<x<\tfrac{m}3 \big\}$, így $\displaystyle |C|=\big[\tfrac{m}3\big]-\big[\tfrac{m}6\big]$.

Bizonyítás: A $\displaystyle C$ halmaz olyan $\displaystyle (x,m-x)$ párokból áll, amelyekben $\displaystyle 0<x<\tfrac{m}{2}$.

Ha $\displaystyle 0<x<\tfrac{m}{6}$, akkor $\displaystyle \pi(x)=3x<m-3x=\pi(m-x)$, tehát $\displaystyle x$ és $\displaystyle m-x$ nem állnak inverzióban, tehát $\displaystyle (x,m-x)\notin C$.

Ha $\displaystyle \tfrac{m}{6}<x<\tfrac{m}{3}$, akkor $\displaystyle \pi(x)=3x>m-3x=\pi(m-x)$, tehát $\displaystyle x$ és $\displaystyle m-x$ inverzióban állnak, tehát $\displaystyle (x,m-x)\in C$.

Végül, ha $\displaystyle \tfrac{m}{3}<x<\tfrac{m}{2}$, akkor $\displaystyle \pi(x)=3x-m<2m-3x=\pi(m-x)$, tehát $\displaystyle x$ és $\displaystyle m-x$ nem állnak inverzióban, tehát $\displaystyle (x,m-x)\notin C$. Ezzel a 2. állítást is igazoltuk.

A $\displaystyle \pi$ paritását most már kétféleképpen is felírtuk: megegyezik $\displaystyle m-c-1$, illetve $\displaystyle |I|$ paritásával is. A kétféle felírást összehasonlítva $\displaystyle m-c-1\equiv |I|\equiv |C|=\big[\tfrac{m}3\big]-\big[\tfrac{m}6\big]\pmod{2}$, ezért a ciklusok számára azt kapjuk, hogy

$\displaystyle c \equiv m+\big[\tfrac{m}3\big]+\big[\tfrac{m}6\big]+1 \pmod{2}.$

Az $\displaystyle m$ modulo $\displaystyle 12$ maradéka szerint szétbontva

Statisztika:

8 dolgozat érkezett.
7 pontot kapott:	Molnár Bálint, Schrettner Jakab, Szabó 417 Dávid, Szabó Kristóf.
5 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2018. novemberi matematika feladatai