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