Library / /21 of 91

, 2007

Combinatorics Difficulty 5.4 AIME, harder Prove it India

Let $X$ be the set of all bijective functions from the set $S = \{1, 2, 3, ..., n\}$ to itself. For each $f \in X$ , define
$T_f(j) = \begin{cases} 1, & \text{if } f^{(12)}(j) = j, \\ 0, & \text{otherwise.} \end{cases}$

Determine
$\sum_{f \in X} \sum_{j=1}^{n} T_f(j).$
(Here $f^{(k)}(x) = f(f^{(k-1)}(x))$ for $k \ge 2$ .)

Solution

Suppose $n \ge 12$ . The elements of $X$ are permutations of $\{1, 2, 3, ..., n\}$ . If $j$ belongs to a $k$ -cycle of $f$ , where $k$ is a divisor of $12$ , then $f^{(k)}(j) = j$ . The number of divisors of $12$ is $6$ . Let $m(j,k)$ be the number of elements $f$ of $T$ in which $j$ belongs to a $k$ -cycle of $f$ , $1 \le j \le n$ . Then
$m(j,k) = (n-1)(n-2)\cdots(n-k+1)(n-k)! = (n-1)!$
The required sum is, therefore, $n(n-1)! \times 8 = 6(n!)$ If $n < 12$ , the answer is $t(n)(n!)$ , where $t(n)$ is the number of positive divisors of $12$ which are less than or equal to $n$ . Thus, they are $1, 2(2!), 3(3!), 4(4!), 4(5!), 5(6!), 5(7!), 5(8!), 5(9!), 5(10!), 5(11!)$ .

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.