20. 2005 children, numbered 1 to 2005 , participate in a game. 2005 cards, numbered 2 to 2006, are prepared. Each child is to be distributed one card. It is required that the number on the card given to each child must be a multiple of the number of the child. In how many different ways can the cards be distributed?
(2 marks)
一個遊戲有 2005 名小孩參加, 他們被編成 1 至 2005 號。此外, 遊戲中有 2005 張咭片, 分別編成 2 至 2006 號。現要把咭片派給小孩, 每人一張, 並且要求每人所得的咭片的編號都是相應的小孩的編號的倍數。問有多少種不同的方法派咭片?
20. 13
20. Let $f(n)$ be the number of the card received by child $n$. Consider the sequence
$$
1, f(1), f(f(1)), f(f(f(1))), \ldots
$$

Note that the term 2006 must eventually occur and the sequence can no longer be continued as $f(2006)$ is undefined. Furthermore, if we let $S$ be the set of integers from 1 to 2006 which have not occurred in the above sequence, then we see that $f(S)=S$. It easily follows that every child in $S$ must receive the card with the same number as his own.

It therefore remains to count the number of such sequences, starting from 1 and ending in 2006, and each term (except for the first one) is a multiple of the previous term. Note that $2006=2 \times 17 \times 59$, and every positive factor of 2006 is of the form $2^{a} 17^{b} 59^{c}$ and can be denoted by the three-tuple $(a, b, c)$ where each of $a, b, c$ is 0 or 1 . The problem is thus reduced to counting the number of sequences from $(0,0,0)$ to $(1,1,1)$ for which each coordinate must be greater than or equal to the corresponding coordinate in the previous term.

If we increase the three coordinates one by one, we get $3!=6$ such sequences. If we first increase one of the coordinates and then increase the other two at once, we get $C_{1}^{3}=3$ such sequences. If we first increase two of the coordinates at once and then increase the remaining one, we get $C_{2}^{3}=3$ such sequences. Finally, we get 1 such sequence if we jump from $(0,0,0)$ to $(1,1,1)$ directly. It follows that the answer is $6+3+3+1=13$.