Maths Olympiad Prep

Library / /17 of 21

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it South Korea

nn students with different names are forming a circle and standing toward the center of the circle. Initially nn name tags of the students are distributed to them at random. The students repeat the following process:
[process] Every student having one's own name tag gets out of the circle, and the remaining students pass their name tags to the right.
Find the number of initial distributions of name tags such that some students still remain after 4 processes.

Solution

Let AA be a finite set of positive integers and π\pi be a permutation (=bijection) on AA. A pair (x,π(x))A2(x, \pi(x)) \in A^2 is called a "up" if x<π(x)x < \pi(x) holds, and up(π)up(\pi) is defined by the number of up's in π\pi.

Given a permutation π\pi on A={x1<x2<<xm}A = \{x_1 < x_2 < \dots < x_m\}, define a permutation π\pi' by
π=x2x3x1π, \pi' = x_2x_3\cdots x_{1} \circ \pi,
where \circ means the functional composition. Then we can easily deduce the following lemma.

Lemma. Let π\pi be a permutation on A={x1<x2<<xm}A = \{x_1 < x_2 < \dots < x_m\} without fixed points. Then we have
up(π)=up(π)1. up(\pi') = up(\pi) - 1.

Let S0={s1,s2,,sn}S_0 = \{s_1, s_2, \dots, s_n\} be the set of nn students and T0={t1,t2,,tn}T_0 = \{t_1, t_2, \dots, t_n\} be the set of nn name tags. A distribution of name tags can be interpreted as a bijection τ0:T0S0\tau_0: T_0 \to S_0. By simplifying τ0(ti)=sj\tau_0(t_i) = s_j to τ0(i)=j\tau_0(i) = j, we can regard τ\tau as a permutation on nn. Let F1F_1 be the set of fixed points of τ0\tau_0. Define S1=S0{siiF1}S_1 = S_0 - \{s_i \mid i \in F_1\} and T1=T0{tiiF1}T_1 = T_0 - \{t_i \mid i \in F_1\}. Then τ1:T1S1\tau_1: T_1 \to S_1 represents the state after the exit of each student having one's own name tag. It is obvious that up(τ0)=up(τ1)up(\tau_0) = up(\tau_1). Also we can easily deduce the following:

Given a distribution π\pi, passing their name tags to the right derives a distribution π\pi'.
Therefore τ1\tau'_1 is the distribution after one process. By the lemma we have
up(τ1)=up(τ1)1=up(τ0)1. up(\tau'_1) = up(\tau_1) - 1 = up(\tau_0) - 1.

Thus, with a single process, the number of up's is decreased by 1. Thus if an initial distribution τ0\tau_0 has at most 3 up's then every student has one's own name tag during 3 processes, i.e., every student gets out of the circle until 4 processes. Therefore the answer of this problem is
n!{τ0Symnup(τ0)3}, n! - |\{\tau_0 \in \text{Sym}_n \mid \text{up}(\tau_0) \le 3\}|,
where Symn\text{Sym}_n is the set of permutations on {1,2,,n}\{1, 2, \dots, n\}.

Let B(n,k)B(n, k) be the set of {πSymnup(π)k}\{\pi \in \text{Sym}_n \mid \text{up}(\pi) \le k\} and b(n,k):=B(n,k)b(n, k) := |B(n, k)|. By considering the position of nn in πB(n,k)\pi \in B(n, k), we can easily deduce the following recurrence relation:
b(n,k)=(k+1)b(n1,k)+(nk1)b(n1,k1),n2 b(n, k) = (k + 1)b(n - 1, k) + (n - k - 1)b(n - 1, k - 1), \quad n \ge 2
with b(n,0)=1b(n, 0) = 1 and b(n,k)=0b(n, k) = 0 for knk \ge n. For k=1k = 1 we have
b(n,1)=2b(n1,1)+(n2).b(1,1)=1. b(n, 1) = 2b(n - 1, 1) + (n - 2). \quad b(1, 1) = 1.
The recurrence relation yields b(n,1)=2nnb(n, 1) = 2^n - n. For k=2k = 2 we have
b(n,2)=3b(n1,2)+(n3)(2n1n+1),b(1,2)=1. b(n, 2) = 3b(n - 1, 2) + (n - 3)(2^{n-1} - n + 1), \quad b(1, 2) = 1.
The recurrence relation yields b(n,2)=3nn2n+(n2)b(n, 2) = 3^n - n2^n + \binom{n}{2}. Finally, for k=3k = 3, we have
b(n,3)=4b(n1,3)+(n4)(3n1(n1)2n1+(n12)),b(1,3)=1. b(n, 3) = 4b(n - 1, 3) + (n - 4) \left( 3^{n-1} - (n-1)2^{n-1} + \binom{n-1}{2} \right), \quad b(1, 3) = 1.
The recurrence relation yields b(n,3)=4nn3n+(n2)2n(n3)b(n, 3) = 4^n - n3^n + \binom{n}{2}2^n - \binom{n}{3}. Therefore the answer of this problem is
n!b(n,3)=n!4n+n3n(n2)2n+(n3). n! - b(n, 3) = n! - 4^n + n3^n - \binom{n}{2}2^n + \binom{n}{3}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.