Maths Olympiad Prep

Library / /736 of 860

Number theory Difficulty 5.5 AIME, harder Find the answer

Let SS be a set of positive integers satisfying the following two conditions: - For each positive integer nn, at least one of n,2n,,100nn, 2 n, \ldots, 100 n is in SS. - If a1,a2,b1,b2a_{1}, a_{2}, b_{1}, b_{2} are positive integers such that gcd(a1a2,b1b2)=1\operatorname{gcd}\left(a_{1} a_{2}, b_{1} b_{2}\right)=1 and a1b1,a2b2Sa_{1} b_{1}, a_{2} b_{2} \in S, then a2b1,a1b2Sa_{2} b_{1}, a_{1} b_{2} \in S Suppose that SS has natural density rr. Compute the minimum possible value of 105r\left\lfloor 10^{5} r\right\rfloor. Note: SS has natural density rr if 1nS{1,,n}\frac{1}{n}|S \cap\{1, \ldots, n\}| approaches rr as nn approaches \infty.

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

Solution

The optimal value of rr is 1252\frac{1}{252}. This is attained by letting SS be the set of integers nn for which ν2(n)4mod5\nu_{2}(n) \equiv 4 \bmod 5 and ν3(n)1mod2\nu_{3}(n) \equiv 1 \bmod 2. Let SS be a set of positive integers satisfying the two conditions. For each prime pp, let Ap={νp(n)A_{p}=\left\{\nu_{p}(n)\right. : nS}n \in S\}. We claim that in fact SS is precisely the set of positive integers nn for which νp(n)Ap\nu_{p}(n) \in A_{p} for each prime pp. Let pp be prime and suppose that a1pe1,a2pe2Sa_{1} p^{e_{1}}, a_{2} p^{e_{2}} \in S, with pa1,a2p \nmid a_{1}, a_{2}. Then, setting b1=pe1b_{1}=p^{e_{1}} and b2=pe2b_{2}=p^{e_{2}} in the second condition gives that a1pe2Sa_{1} p^{e_{2}} \in S as well. So, if we have an integer nn for which νp(n)Ap\nu_{p}(n) \in A_{p} for each prime pp, we can start with any element nn^{\prime} of SS and apply this step for each prime divisor of nn and nn^{\prime} to obtain nSn \in S. Now we deal with the first condition. Let nn be any positive integer. We will compute the least positive integer mm such that mnSm n \in S. By the above result, we can work with each prime separately. For a given prime pp, let epe_{p} be the least element of ApA_{p} with epνp(n)e_{p} \geq \nu_{p}(n). Then we must have νp(m)epνp(n)\nu_{p}(m) \geq e_{p}-\nu_{p}(n), and equality for all primes pp is sufficient. So, if the elements of ApA_{p} are cp,1<cp,2<cp,3<cp,4<c_{p, 1}<c_{p, 2}<c_{p, 3}<c_{p, 4}<\ldots, then cp=max(cp,1,cp,2cp,11,cp,3cp,21,cp,4cp,31,)c_{p}=\max \left(c_{p, 1}, c_{p, 2}-c_{p, 1}-1, c_{p, 3}-c_{p, 2}-1, c_{p, 4}-c_{p, 3}-1, \ldots\right) is the worst case value for νp(m)\nu_{p}(m). We conclude two things from this. First, we must have ppcp100\prod_{p} p^{c_{p}} \leq 100 by condition 1, and in fact this is sufficient. Second, since we only care about cpc_{p} and would like to minimize rr, the optimal choice for ApA_{p} is an arithmetic progression with first term cpc_{p} and common difference cp+1c_{p}+1. So we assume that each ApA_{p} is of this form. Let t=ppcpt=\prod_{p} p^{c_{p}}. We now compute rr. Note that SS is the set of integers nn such that for each prime pp, napk(cp+1)1modpk(cp+1)n \equiv a p^{k\left(c_{p}+1\right)-1} \bmod p^{k\left(c_{p}+1\right)} for some positive integers a,ka, k with a<pa<p. This means that each prime pp contributes a factor of p1pcp+1+p1p2cp+2+p1p3cp+3+=p1pcp+11=11+p++pcp\frac{p-1}{p^{c_{p}+1}}+\frac{p-1}{p^{2 c_{p}+2}}+\frac{p-1}{p^{3 c_{p}+3}}+\cdots=\frac{p-1}{p^{c_{p}+1}-1}=\frac{1}{1+p+\cdots+p^{c_{p}}} to the density of SS. Multiplying over all primes pp gives r=1σ(t)r=\frac{1}{\sigma(t)}, where σ(t)\sigma(t) is the sum of divisors of tt. So, it suffices to maximize σ(t)\sigma(t) for t100t \leq 100. By inspection, t=96t=96 is optimal, giving r=1252r=\frac{1}{252}.

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.