Competition problem — Combinatorics

Library / /87 of 129

Combinatorics Difficulty 5.6 AIME, harder Prove it Slovenia

A red box contains twelve balls numbered from $1$ to $12$ . Jan moves some of the balls into the green box. He then realizes that for any two balls from the green box the following is true: if these two balls are numbered $a$ and $b$ , then the ball numbered $|a-b|$ is in the red box. At most how many balls has Jan moved to the green box?

Solution

Jan can move $6$ balls. If he moves all odd-numbered balls, then the difference of the numbers on any two of them is an even number, which is clearly not written on any of the balls in the green box.

Now, assume that Jan moved at least $7$ balls to the green box and denote the numbers on these balls by $a_1 < a_2 < a_3 < a_4 < a_5 < a_6 < a_7$ . Then $a_7 - a_1$ , $a_6 - a_1$ , $a_5 - a_1$ , $a_4 - a_1$ , $a_3 - a_1$ , $a_2 - a_1$ are six different positive integers smaller than $12$ . The balls with these numbers on them should be in the red box, but this is not possible since the red box contains at most five balls.

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.