Track / Stage 5 / 143 of 400 #1223 of 2444

Problem 1223

AIME late

Number theory Difficulty 5.3 Prove it Ukrainian National Mathematical Olympiad · 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$ ?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.