Competition problem — Combinatorics

Library / /3 of 16

Combinatorics Difficulty 5.4 AIME, harder Prove it JBMO

Problem:

The natural numbers from $1$ to $50$ are written down on the blackboard. At least how many of them should be deleted, in order that the sum of any two of the remaining numbers is not a prime?

Solution

Solution:

Notice that if the odd, respectively even, numbers are all deleted, then the sum of any two remaining numbers is even and exceeds $2$ , so it is certainly not a prime. We prove that $25$ is the minimal number of deleted numbers. To this end, we group the positive integers from $1$ to $50$ in $25$ pairs, such that the sum of the numbers within each pair is a prime:
$\begin{aligned} & (1,2), (3,4), (5,6), (7,10), (8,9), (11,12), (13,16), (14,15), (17,20) \\ & (18,19), (21,22), (23,24), (25,28), (26,27), (29,30), (31,36), (32,35) \\ & (33,34), (37,42), (38,41), (39,40), (43,46), (44,45), (47,50), (48,49) \end{aligned}$
Since at least one number from each pair has to be deleted, the minimal number is $25$ .

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.