Maths Olympiad Prep

Library / /221 of 348

Number theory Difficulty 5.0 AIME Find the answer

Let nn be the answer to this problem. Find the minimum number of colors needed to color the divisors of (n24)(n-24)! such that no two distinct divisors s,ts, t of the same color satisfy sts \mid t.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We first answer the following question. Find the minimum number of colors needed to color the divisors of mm such that no two distinct divisors s,ts, t of the same color satisfy sts \mid t. Prime factorize m=p1e1pkekm=p_{1}^{e_{1}} \ldots p_{k}^{e_{k}}. Note that the elements 1,p1,p12,,p1e1,p1e1p2,p1e1p22,,p1e1p2e2p1e1p2e2p3,p1e1p2e2p32,,p1e1p2e2p3e3p1e1pk1ek1pk,p1e1pk1ek1pk2,,p1e1pk1ek1pkek\begin{aligned} & 1, p_{1}, p_{1}^{2}, \ldots, p_{1}^{e_{1}}, \\ & p_{1}^{e_{1}} p_{2}, \quad p_{1}^{e_{1}} p_{2}^{2}, \quad \ldots, \quad p_{1}^{e_{1}} p_{2}^{e_{2}} \\ & p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}, \quad p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{2}, \quad \ldots, \quad p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{e_{3}} \\ & \vdots \\ & p_{1}^{e_{1}} \ldots p_{k-1}^{e_{k-1}} p_{k}, \quad p_{1}^{e_{1}} \ldots p_{k-1}^{e_{k-1}} p_{k}^{2}, \quad \ldots, \quad p_{1}^{e_{1}} \ldots p_{k-1}^{e_{k-1}} p_{k}^{e_{k}} \end{aligned} must be pairwise different colors. Hence, we need at least 1+e1++ek1+e_{1}+\cdots+e_{k} colors. This is also sufficient: number the colors 1,2,,1+e1++ek1,2, \ldots, 1+e_{1}+\cdots+e_{k}, and color the divisor ss with color 1+p prime νp(s)1+\sum_{p \text { prime }} \nu_{p}(s). Thus, the answer to the above question is c(m):=1+e1++ekc(m):=1+e_{1}+\cdots+e_{k}. Now, we return to the original problem. We wish to find the integer nn for which c((n24)!)=nc((n-24)!)=n, or c((n24)!)(n24)=24c((n-24)!)-(n-24)=24. Let f(k)=c(k!)kf(k)=c(k!)-k, so that we want to solve f(n24)=24f(n-24)=24. Note that f(1)=0f(1)=0, while for k>1k>1 we have f(k)f(k1)=c(k!)c((k1)!)1=Ω(k)1f(k)-f(k-1)=c(k!)-c((k-1)!)-1=\Omega(k)-1, where Ω(k)\Omega(k) is the number of prime factors of kk with multiplicity. k12345678910111213141516Ω(k)112121322131224f(k)000112245668891013k1718192021222324252627Ω(k)13132214223Ω(k)1315151718191922232426\begin{array}{c|cccccccccccccccc} k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline \Omega(k) & & 1 & 1 & 2 & 1 & 2 & 1 & 3 & 2 & 2 & 1 & 3 & 1 & 2 & 2 & 4 \\ f(k) & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 4 & 5 & 6 & 6 & 8 & 8 & 9 & 10 & 13 \\ & k & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & \\ & \Omega(k) & 1 & 3 & 1 & 3 & 2 & 2 & 1 & 4 & 2 & 2 & 3 & \\ & & \Omega(k) & 13 & 15 & 15 & 17 & 18 & 19 & 19 & 22 & 23 & 24 & 26 & \end{array} Therefore n24=26n-24=26 and n=50n=50.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.