Maths Olympiad Prep

Library / /68 of 520

Number theory Difficulty 6.4 National olympiad Find the answer

Determine if there is a set SS of 2011 positive integers so that for every pair m,nm,n of distinct elements of SS, mn=(m,n)|m-n|=(m,n). Here (m,n)(m,n) denotes the greatest common divisor of mm and nn.

Solution

To determine if there exists a set S S of 2011 positive integers such that for every pair m,n m, n of distinct elements of S S , mn=(m,n) |m - n| = (m, n) , we can proceed as follows:

1. Understanding the Condition:
The condition mn=(m,n) |m - n| = (m, n) implies that the absolute difference between any two distinct elements m m and n n in the set S S must be equal to their greatest common divisor (gcd).

2. Initial Setup:
Let's start with a positive integer a a . We need to find a sequence of integers a1,a2,,an a_1, a_2, \ldots, a_n such that for any i<j i < j , ajai a_j - a_i divides ai a_i .

3. Generating the Sequence:
Consider the sequence m,m+a1,m+a2,,m+an m, m + a_1, m + a_2, \ldots, m + a_n , where m=lcm(a1,a2,,an) m = \mathrm{lcm}(a_1, a_2, \ldots, a_n) . Here, lcm \mathrm{lcm} denotes the least common multiple.

4. Verifying the Condition:
For any i<j i < j :
(m+aj)(m+ai)=ajai (m + a_j) - (m + a_i) = a_j - a_i
Since ajai a_j - a_i divides ai a_i , and ai a_i divides m m , it follows that ajai a_j - a_i divides m+ai m + a_i .

5. Ensuring the GCD Condition:
We need to ensure that m+aj(m+ai)=(m+aj,m+ai) |m + a_j - (m + a_i)| = (m + a_j, m + a_i) . Given that ajai a_j - a_i divides ai a_i and ai a_i divides m m , we have:
(m+aj)(m+ai)=ajai (m + a_j) - (m + a_i) = a_j - a_i
and
(m+ai)m=ai (m + a_i) - m = a_i
Thus, the sequence satisfies the initial requirement.

6. Inductive Construction:
By induction, we can construct such sequences of arbitrary length. Starting with a base case, we can generate a sequence of length 2011 by choosing appropriate ai a_i values.

Conclusion:
The construction method described above shows that it is possible to generate a set S S of 2011 positive integers satisfying the given condition.

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.