Competition problem — Number theory

Library / /52 of 220

Number theory Difficulty 5.3 AIME, harder Prove it Ukraine

What is the size of the largest set of numbers we can choose among $1$ , $2$ , ..., $2n$ in such a way that any two of them have a common divisor greater than $1$ ?

Solution

If we choose all even numbers, they follow required condition and there are exactly $n$ of them.

Now let's consider next pairs of integers: $(1, 2)$ , $(3, 4)$ , ..., $(2n-1, 2n)$ . In each pair, numbers are relatively prime and we cannot choose both of them to our set. Therefore, it is impossible to choose more than $n$ integers.

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.