Competition problem — Combinatorics

Library / /8 of 21

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.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.