uniolympiads Ελληνικά

IMC 2010, Day 2, Problem 3

Denote by SnS_n the group of permutations of the sequence (1,2,…,n)(1, 2, \dots, n). Suppose that GG is a subgroup of SnS_n, such that for every π∈G∖{e}\pi \in G \setminus \{e\} there exists a unique k∈{1,2,…,n}k \in \{1, 2, \dots, n\} for which π(k)=k\pi(k) = k. (Here ee is the unit element in the group SnS_n.) Show that this kk is the same for all π∈G∖{e}\pi \in G \setminus \{e\}.

Original from the official PDFDenote by S n the group of permutations of the sequence (1, 2, . . . , n). Suppose that G is a subgroup of S n , such that for every π ∈ G \ {e} there exists a unique k ∈ {1, 2, . . . , n} for which π(k) = k. (Here e is the unit element in the group S n .) Show that this k is the same for all π ∈ G \ {e}.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Let us consider the action of GG on the set X={1,…,n}X=\{1,\dots,n\}. Let

Gx={ g∈G ⁣: g(x)=x}andGx={ g(x) ⁣: g∈G}G_x=\{\,g\in G\colon\ g(x)=x\}\quad\text{and}\quad Gx=\{\,g(x)\colon\ g\in G\}
be the stabilizer and the orbit of x∈Xx\in X under this action, respectively. The condition of the problem states that
G=⋃x∈XGx(1)G=\bigcup_{x\in X}G_x \tag{1}
and
Gx∩Gy={e}for allx≠y.(2)G_x\cap G_y=\{e\}\quad\text{for all}\quad x\ne y. \tag{2}
We need to prove that Gx=GG_x=G for some x∈Xx\in X.

Let Gx1,…,GxkGx_1,\dots,Gx_k be the distinct orbits of the action of GG. Then one can write (1) as

G=⋃i=1k⋃y∈GxiGy.(3)G=\bigcup_{i=1}^k\bigcup_{y\in Gx_i}G_y. \tag{3}
It is well known that
∣Gx∣=∣G∣∣Gx∣.(4)|Gx|=\frac{|G|}{|G_x|}. \tag{4}
Also note that if y∈Gxy\in Gx then Gy=GxGy=Gx and thus ∣Gy∣=∣Gx∣|Gy|=|Gx|. Therefore,
∣Gx∣=∣G∣∣Gx∣=∣G∣∣Gy∣=∣Gy∣for ally∈Gx.(5)|G_x|=\frac{|G|}{|Gx|}=\frac{|G|}{|Gy|}=|G_y|\quad\text{for all}\quad y\in Gx. \tag{5}
Combining (3), (2), (4) and (5) we get
∣G∣−1=∣G∖{e}∣=∣⋃i=1k⋃y∈GxiGy∖{e}∣=∑i=1k∣G∣∣Gxi∣(∣Gxi∣−1),|G|-1=|G\setminus\{e\}|=\left|\bigcup_{i=1}^k\bigcup_{y\in Gx_i}G_y\setminus\{e\}\right|=\sum_{i=1}^k\frac{|G|}{|G_{x_i}|}(|G_{x_i}|-1),
hence
1−1∣G∣=∑i=1k(1−1∣Gxi∣).(6)1-\frac1{|G|}=\sum_{i=1}^k\left(1-\frac1{|G_{x_i}|}\right). \tag{6}
If for some i,j∈{1,…,k}i,j\in\{1,\dots,k\} ∣Gxi∣,∣Gxi∣≥2|G_{x_i}|,|G_{x_i}|\ge2 then
∑i=1k(1−1∣Gxi∣)≥(1−12)+(1−12)=1>1−1∣G∣\sum_{i=1}^k\left(1-\frac1{|G_{x_i}|}\right)\ge\left(1-\frac12\right)+\left(1-\frac12\right)=1>1-\frac1{|G|}
which contradicts with (6), thus we can assume that
∣Gx1∣=…=∣Gxk−1∣=1.|G_{x_1}|=\ldots=|G_{x_{k-1}}|=1.
Then from (6) we get ∣Gxk∣=∣G∣|G_{x_k}|=|G|, hence Gxk=GG_{x_k}=G.

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?