Maths Olympiad Prep

Library / /92 of 94

Algebra Difficulty 7.4 National Olympiad, round 2 Prove it Hong Kong

Let S={1,2,,100}S = \{1, 2, \dots, 100\}. Determine the number of functions f:SSf : S \to S satisfying the following conditions.
(i) f(1)=1f(1) = 1;
(ii) ff is bijective (i.e. for every yy in SS, the equation f(x)=yf(x) = y has exactly one solution);
(iii) f(n)=f(g(n))f(h(n))f(n) = f(g(n))f(h(n)) for every nn in SS.
Here g(n)g(n) and h(n)h(n) denote the uniquely determined positive integers such that g(n)h(n)g(n) \le h(n), g(n)h(n)=ng(n)h(n) = n and h(n)g(n)h(n)-g(n) is as small as possible. (For instance, g(80)=8g(80) = 8, h(80)=10h(80) = 10 and g(81)=h(81)=9g(81) = h(81) = 9.)

Solution

There are 348364800 such functions.
We first claim that condition (iii) can be replaced by the completely multiplicative condition. This means
f(p1a1p2a2psas)=f(p1)a1f(p2)a2f(ps)as f(p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}) = f(p_1)^{a_1} f(p_2)^{a_2} \cdots f(p_s)^{a_s}
for any distinct primes p1,p2,,psp_1, p_2, \dots, p_s and positive integers a1,a2,,asa_1, a_2, \dots, a_s. We prove this by induction on a1+a2++asa_1 + a_2 + \cdots + a_s.
The base cases a1+a2++as=0,1a_1 + a_2 + \cdots + a_s = 0, 1 hold trivially. Assume the result holds whenever the sum of exponents is less than kk. Consider n=p1a1p2a2psasn = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s} where a1+a2++as=ka_1 + a_2 + \cdots + a_s = k. Note that nn is composite, and so g(n),h(n)>1g(n), h(n) > 1. Since g(n)h(n)=ng(n)h(n) = n, the sum of exponents in the prime factorizations of g(n)g(n) and h(n)h(n) are both smaller than kk. Thus, by the inductive hypothesis, f(g(n))f(g(n)) and f(h(n))f(h(n)) can be decomposed into a product of f(pj)f(p_j)'s. Clearly, this proves
f(n)=f(p1a1p2a2psas)=f(p1)a1f(p2)a2f(ps)as. f(n) = f(p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}) = f(p_1)^{a_1} f(p_2)^{a_2} \cdots f(p_s)^{a_s}.

By induction, we have shown that ff is completely multiplicative. Conversely, if ff is completely multiplicative, condition (iii) holds trivially.
Let P\mathcal{P} be the set of all primes from 1 to 100, and let C=S(P{1})\mathcal{C} = S - (\mathcal{P} \cup \{1\}) be the set of all composites. For any nCn \in \mathcal{C}, since g(n),h(n)>1g(n), h(n) > 1, we must have f(g(n)),f(h(n))>1f(g(n)), f(h(n)) > 1. Therefore, f(n)=f(g(n))f(h(n))Cf(n) = f(g(n))f(h(n)) \in \mathcal{C}. This implies f(C)=Cf(\mathcal{C}) = \mathcal{C}. As f(1)=1f(1) = 1, by the bijective condition, we must have f(P)=Pf(\mathcal{P}) = \mathcal{P}. Thus, it remains to assign distinct prime values to f(p)f(p) for pPp \in \mathcal{P}. Afterwards we can easily compute f(n)f(n) by the completely multiplicative condition, while the bijective condition is always satisfied.
Now, the only constraint is that f(n)Sf(n) \in S for any nSn \in S. For example, since
100f(64)=f(2)6 100 \ge f(64) = f(2)^6
and f(2)1f(2) \ne 1, we must have f(2)=2f(2) = 2. Similarly, by considering f(81)f(81), we can prove that f(3)=3f(3) = 3. Next, since
100f(75)=f(3)f(5)2, 100 \ge f(75) = f(3)f(5)^2,
we have f(5)5f(5) \le 5, and hence f(5)=5f(5) = 5. Similarly, by considering f(98),f(99)f(98), f(99) and f(91)f(91), we can prove that f(p)=pf(p) = p for p=7,11,13p = 7, 11, 13.
Next, by considering f(85)f(85) and f(95)f(95), we can only prove that f(17),f(19)20f(17), f(19) \le 20. Therefore, we have {f(17),f(19)}={17,19}\{f(17), f(19)\} = \{17, 19\}. There is no further constraint on f(17)f(17) and f(19)f(19) since we can verify that f(n)Sf(n) \in S for any nn being multiples of 17 or 19, as long as f(17),f(19)20f(17), f(19) \le 20.
Similarly, by considering f(92)f(92), we find that f(23)=23f(23) = 23.
By considering f(87)f(87) and f(93)f(93), we find that {f(29),f(31)}={29,31}\{f(29), f(31)\} = \{29, 31\}.
By considering f(74),f(82),f(86)f(74), f(82), f(86) and f(94)f(94), we find that 37,41,43,4737, 41, 43, 47 can be mapped to any permutation of themselves.
Lastly, the images of 53,59,61,67,71,73,79,83,89,9753, 59, 61, 67, 71, 73, 79, 83, 89, 97 can be any permutation of themselves.
In view of the above arguments, we can choose the images within each group in an arbitrary way. Each choice corresponds to a unique function satisfying all requirements. Therefore, the number of such functions is

2! ×\times 2! ×\times 4! ×\times 10! = 348364800.

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.