Maths Olympiad Prep

Library / /436 of 520

Number theory Difficulty 7.4 National olympiad, round 2 Find the answer

Let nn be a "Good Number" if sum of all divisors of nn is less than 2n2n for nZ.n\in \mathbb{Z}.
Does there exist an infinite set MM that satisfies the following?

For all a,bM,a,b\in M, a+ba+b is good number. (a=ba=b is allowed.)

Solution

1. Define the function and set up the problem:
Let σ(n)\sigma(n) be the sum of the divisors of nn and define f(n)=σ(n)nf(n) = \dfrac{\sigma(n)}{n}. We are interested in finding a set MM such that for all a,bMa, b \in M, f(a+b)<2f(a+b) < 2.

2. Construct the sequence of sets:
Start with M1={1}M_1 = \{1\}. We will construct a sequence of sets M1,M2,M_1, M_2, \ldots such that Mk+1=Mk{ak+1}M_{k+1} = M_k \cup \{a_{k+1}\} for some positive integer ak+1a_{k+1} with a1=1a_1 = 1. The union of all these sets will produce an infinite set MM.

3. Choose the elements of the sequence:
Let p1<p2<p_1 < p_2 < \ldots be the primes in increasing order. Suppose at some step we have the set Mk={a1,a2,,ak}M_k = \{a_1, a_2, \ldots, a_k\}. We will choose ak+1=p1p2pm+1a_{k+1} = p_1 p_2 \ldots p_m + 1 for sufficiently large mm to be determined later. We need ai+ak+1a_i + a_{k+1} to be a good number for each ik+1i \le k+1.

4. Lemma:
For all nn, f(n)<pn(pp1)f(n) < \prod_{p|n} \left( \dfrac{p}{p-1} \right).
- Proof:
Note that f(n)=pn(1+p1++pvp(n))<pn(pp1)f(n) = \prod_{p|n} \left( 1 + p^{-1} + \ldots + p^{-v_p(n)} \right) < \prod_{p|n} \left( \dfrac{p}{p-1} \right) by the infinite geometric series formula applied to each term of the product.

5. **Show that 2ak+12a_{k+1} is a good number:**
For large mm, our choice of ak+1a_{k+1} satisfies that 2ak+12a_{k+1} is a good number. All primes dividing ak+1a_{k+1} must have size at least pm+1p_{m+1}, hence:
f(2ak+1)=1.5f(ak+1)<1.5pak+1(pp1)1.5pak+1(pm+1pm+11) f(2a_{k+1}) = 1.5 f(a_{k+1}) < 1.5 \prod_{p|a_{k+1}} \left( \dfrac{p}{p-1} \right) \le 1.5 \prod_{p|a_{k+1}} \left( \dfrac{p_{m+1}}{p_{m+1}-1} \right)
Since ak+1=p1p2pm+1pm+1ma_{k+1} = p_1 p_2 \ldots p_m + 1 \le p_{m+1}^m, this term is at most:
1.5(1+1pm+11)m 1.5 \cdot \left( 1 + \dfrac{1}{p_{m+1}-1} \right)^m
For large enough mm, the ratio bm=mpm+11b_m = \dfrac{m}{p_{m+1}-1} grows arbitrarily small (as roughly (logm)1(\log m)^{-1}), hence:
1.5(1+1pm+11)m1.5ebm<2 1.5 \cdot \left( 1 + \dfrac{1}{p_{m+1}-1} \right)^m \approx 1.5 \cdot e^{b_m} < 2

6. **Show that ai+ak+1a_i + a_{k+1} is a good number:**
For sufficiently large mm, each ai+ak+1a_i + a_{k+1} must be a good number. Assume pm>akp_m > a_k. Then:
ai+ak+1=(ai+1)+p1p2pm a_i + a_{k+1} = (a_i + 1) + p_1 p_2 \ldots p_m
By the inductive hypothesis, ai+1=ai+a1a_i + 1 = a_i + a_1 is good, hence f(ai+1)=ci<2f(a_i + 1) = c_i < 2. Since pmak+1ai+1p_m \ge a_k + 1 \ge a_i + 1, if pai+1p \nmid a_i + 1 and pai+ak+1p | a_i + a_{k+1}, we know pp1p2pm    ppm+1p \nmid p_1 p_2 \ldots p_m \implies p \ge p_{m+1}. It follows that:
f(ai+ak+1)<pai+ak+1,pai+1(pp1)pai+ak+1,ppm+1(pp1)cipai+ak+1,ppm+1(pm+1pm+11) f(a_i + a_{k+1}) < \prod_{p|a_i + a_{k+1}, p|a_i + 1} \left( \dfrac{p}{p-1} \right) \prod_{p|a_i + a_{k+1}, p \ge p_{m+1}} \left( \dfrac{p}{p-1} \right) \le c_i \prod_{p|a_i + a_{k+1}, p \ge p_{m+1}} \left( \dfrac{p_{m+1}}{p_{m+1}-1} \right)
For each ai+ak+1a_i + a_{k+1} to be good, we need:
(pm+1pm+11)logpm+1(ai+ak+1)2ci \left( \dfrac{p_{m+1}}{p_{m+1}-1} \right)^{\log_{p_{m+1}} (a_i + a_{k+1})} \le \dfrac{2}{c_i}
where each cic_i is less than 22. Since ai+ak+1<2(p1p2pm+1)<4p2p3pmpm+1ma_i + a_{k+1} < 2(p_1 p_2 \ldots p_m + 1) < 4 p_2 p_3 \ldots p_m \le p_{m+1}^m, the LHS of the previous inequality is at most:
(pm+1pm+11)m \left( \dfrac{p_{m+1}}{p_{m+1} - 1} \right)^m
As with the previous argument, for large mm this term approaches ebme^{b_m}, which grows arbitrarily close to one as bm0b_m \to 0. Hence for suitable mm we have:
LHSmin(2c1,,2ck) \text{LHS} \le \min \left( \dfrac{2}{c_1}, \ldots, \dfrac{2}{c_k} \right)
Therefore, each ai+ak+1a_i + a_{k+1} is good, as desired.

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