Maths Olympiad Prep

Library / /3 of 5

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:

A set SS of irrational real numbers has the property that among any subset of five numbers in SS, one can find two with irrational sum. How large can S|S| be?

Solution

Solution:

The answer is S8|S| \leq 8. An example is S={n±2n=1,2,3,4}S=\{n \pm \sqrt{2} \mid n=1,2,3,4\} (and any of its subsets).

In general, construct a graph with vertex set SS in which we join two numbers with rational sum. We claim this graph is bipartite; indeed if a1+a2,a2+a3,,an+a1a_{1}+a_{2}, a_{2}+a_{3}, \ldots, a_{n}+a_{1} are all rational for some odd nn, solving the resulting system of equations gives a1a_{1}, \ldots, ana_{n} all rational numbers.

Accordingly we may 2-color SS. If S9|S| \geq 9, then we may find a set of five numbers with rational sum, as desired.

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.