Nested Permutations

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Nested Permutations

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

#1 h Apr 24, 2025, 2:09 PM • 1 Y

Y by Sedro

Let $S = \{1, 2, 3, 4, 5\}$ and let $\sigma_1 : S \to S$ and $\sigma_2 : S \to S$ be permutations of $S$ . Suppose there exists a permutation $\tau : S \to S$ such that $\sigma_1(\tau(s)) = \tau(\sigma_2(s))$ for all $s$ in $S$ .

If $N$ is the number of possible pairs of permutations $(\sigma_1, \sigma_2)$ , find the remainder when $N$ is divided by 1000.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

#2 h Apr 24, 2025, 2:11 PM

Y by

This is inspired by high level mathematics, but can be solved without the need for it and cannot be trivialized by using it. I'd put this around 10 on AIME.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

Sedro

#3 h Apr 24, 2025, 3:37 PM

Y by

Sketch?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

#4 h Apr 24, 2025, 4:02 PM • 1 Y

Y by Sedro

Correct, $\tau$ exists $\iff$ $\sigma_1$ and $\sigma_2$ have matching cycle lengths.

The problem came from conjugates in group theory.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

871 posts

#5 h Apr 24, 2025, 4:36 PM • 1 Y

Y by Sedro

Here's a sketch of the proof:

( $\Rightarrow$ ): Let $\sigma_2$ have a cycle $a_1 \to a_2 \to \cdots \to a_{\ell} \to a_1$ . Then, taking $s = a_i$ , we have $\sigma_1(\tau(a_i)) = \tau(a_{i+1})$ (where we set $a_{\ell + 1} = a_1$ ).

So $\sigma_1$ has $\tau(a_1) \to \tau(a_2) \to \cdots \to \tau(a_{\ell}) \to \tau(a_1)$ . We can't yet say this is a cycle, since there could be repeats, but there cannot be repeats. $\tau$ as a permutation has to map distinct inputs to distinct outputs, so $a_1, a_2, \cdots, a_{\ell}$ being distinct means $\tau(a_1), \tau(a_2), \cdots, \tau(a_{\ell})$ are distinct. So we have a cycle of the same length.

So cycles of length $\ell$ in $\sigma_2$ become cycles of length $\ell$ in $\sigma_1$ under $\tau$ .

Also, as a permutation, we can't have something like 2 separate 2-cycles mapping to the same 2-cycle; they have to map to separate 2-cycles. This shows one direction.

( $\Leftarrow$ ): From the work in the other direction, it becomes obvious how we want to construct $\tau$ . If we match cycles of the same length in $\sigma_2$ and $\sigma_1$ , suppose $\sigma_2$ has $a_1, \cdots, a_{\ell}$ and $\sigma_1$ has $b_1, \cdots, b_{\ell}$ . Set $\tau(a_i) = b_i$ and repeat for all other cycles. It's easy to show this works.

This post has been edited 1 time. Last edited by P_Groudon, Apr 24, 2025, 4:38 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a