Library / Ukrainian National Mathematical Olympiad, Third Round, First Tour /7 of 19

Ukrainian National Mathematical Olympiad, Third Round, First Tour

Combinatorics Difficulty 5.2 AIME, harder Prove it Ukraine

$2n$ distinct positive integers are given. What's the largest number of pairs that can always be formed from these numbers, so that each number belongs to at most one pair, and the sum of integers in each pair is a composite number?

Solution

Let $p_1, p_2, \dots, p_{2n-1}$ be distinct prime integers larger than $2$ . Then for a set $(1, p_1-1, p_2-1, \dots, p_{2n-1}-1)$ it's not possible to form $n$ such pairs, as no number can be paired with number $1$ .

From the other side, we can always form at least $n-1$ pairs from the numbers of the same parity. In each such pair the sum will be even and not less than $4$ , therefore composite.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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