Crimson boi can u water it [13] 几把水题

题目背景

南大几把选拔中最水的题(T3), 适合出在初中竞赛里. 另外这期写解答方便以后想考南大几把的学生?, 篇幅太长除了题面不写中文了. 不过题面也是pmt提供的, 不一定完全准确.

题面

记排列P的置换环数量为c(P),排列P,Q的复合记为P\oplus Q，已知长度为n的排列f_1,f_2,...,f_k。

求证：\sum\limits_{i=1}^k c(f_i)\le n(k-1)+c(\mathop{\oplus}\limits_{i=1}^k f_i)

先想再看提示哦

提示

狠狠归纳.

愿你无需看标答

标答

本期竟然又有标答, 还发出来了!!1111

Let's use the standard notation of the composition of permutations P and Q, P\circ Q. Maybe nju used that weird symbol to make \mathop{\oplus}\limits_{i=1}^k look better. It's easy to observe that P\circ(Q\circ R)=(P\circ Q)\circ R, so we only need to prove that for a pair of n-permutations, namely P and Q,

c(P)+c(Q)\le n+c(P\circ Q)

We prove this by induction on n. Suppose this holds for k, in the k+1 case:

If there's no i such that P(i)\ne i and Q(i)\ne i, which means for any i either P(i)=i or Q(i)=i. Sort all i into three categories:

A=\lbrace i:P(i)=Q(i)=i\rbrace

B=\lbrace i:Q(i)=i\ne P(i)\rbrace

C=\lbrace i:P(i)=i\ne Q(i)\rbrace

then A, B, and C contains all i from 1 to k+1. As P and Q actually don't interfere with each other, we calculate c(P), c(Q), and c(P\circ Q) directly:

c(P)=|A|+|C|+c(P\restriction B)

c(Q)=|A|+|B|+c(Q\restriction C)

c(P\circ Q)=|A|+c(P\restriction B)+c(Q\restriction C)

Thus c(P)+c(Q)=|A|+k+1+c(P\restriction B)+c(Q\restriction C)= k+1+c(P\circ Q).

Otherwise \exists i(P(i)\ne i\land Q(i)\ne i), WLOG assume 1 is such an i.

Define P', a permutation of 2 to k+1, as below:

P'(a)=\left\lbrace\begin{array}{ll}
P(1)&a=P^{-1}(1)\\
P(a)&\text{otherwise}
\end{array}\right.

Q' is defined similarly. As P(1)\ne 1 and Q(1)\ne 1, c(P')=c(P) and c(Q')=c(Q).

If Q(1)=P^{-1}(1), which is equivalent to P\circ Q(1)=1 and Q^{-1}(P^{-1}(1))=1, then

P'\circ Q'(a)=P\circ Q(a)

as the only 'exception', Q^{-1}(1), now coincidentally takes the same value, P(1), when permutated by P'\circ Q' and P\circ Q. In this case, by induction hypothesis,

\begin{array}{rcl}
c(P)+c(Q)&=&c(P')+c(Q')\\
&\le& k+c(P'\circ Q')\\
&=&k+c((P\circ Q)\restriction\lbrace 2,...,k+1\rbrace)\\
&=&k+c(P\circ Q)-1
\end{array}

Otherwise Q(1)\ne P^{-1}(1), which means 1 doesn't form a self-loop under P\circ Q.

In this case,

P'\circ Q'(a)=\left\lbrace\begin{array}{ll}
P\circ Q(1)&a=Q^{-1}(1)\\
P(1)&a=Q^{-1}(P^{-1}(1))\\
P\circ Q(a)&\text{otherwise}
\end{array}\right.

Then we define (P\circ Q)' as below:

(P\circ Q)'(a)=\left\lbrace\begin{array}{ll}
P\circ Q(1)&a=Q^{-1}(P^{-1}(1))\\
P\circ Q(a)&\text{otherwise}
\end{array}\right.

Similarly, c(P\circ Q)=c((P\circ Q)').

Notice that actually P'\circ Q' is just the composition of (P\circ Q)' and the exchange of Q^{-1}(1) and Q^{-1}(P^{-1}(1)), which means the difference between c(P'\circ Q') and c((P\circ Q)') won't be too large.

In fact, if Q^{-1}(1) and Q^{-1}(P^{-1}(1)) are in the same cycle under (P\circ Q)', namely

Q^{-1}(1)\mapsto P(1)\mapsto ...\mapsto Q^{-1}(P^{-1}(1))\mapsto P(Q(1))\mapsto ...\mapsto Q(1)

Then under P'\circ Q' this will be splited into two cycles:

Q^{-1}(1)\mapsto P(Q(1))\mapsto...\mapsto Q^{-1}(1)

Q^{-1}(P^{-1}(1))\mapsto P(1)\mapsto ...\mapsto Q^{-1}(P^{-1}(1))

Thus here

c(P)+c(Q)\le k+c(P'\circ Q')=k+1+c(P\circ Q)

If Q^{-1}(1) and Q^{-1}(P^{-1}(1)) are in two different cycles under (P\circ Q)', namely

Q^{-1}(1)\mapsto P(1)\mapsto ...\mapsto Q^{-1}(1)

Q^{-1}(P^{-1}(1))\mapsto P(Q(1))\mapsto...\mapsto Q^{-1}(P^{-1}(1))

Then under P'\circ Q' these two cycles will be merged into one:

Q^{-1}(1)\mapsto P(Q(1))\mapsto ...\mapsto Q^{-1}(P^{-1}(1))\mapsto P(1)\mapsto ...\mapsto Q^{-1}(1)

In this case

c(P)+c(Q)\le k+c(P'\circ Q')=k-1+c(P\circ Q)

It's easy to verify the above holds when there are self-loops (like when Q^{-1}(1)=P(1)).

Finally, by induction, c(P)+c(Q)\le n+c(P\circ Q) for any pair of n-permutations, which proves what the question proposed.