Problem:
Let be an integer and let . Find the smallest value of such that for every partition of into two subsets, at least one of the subsets contains integers , and (not necessarily distinct) such that .
Note: a partition of is a pair of sets such that .
Solution:
First prove that . Let and assume that and form a partition of such that neither of the subsets contains a solution to the given equation. Without loss of generality assume that . Then necessarily .
If , then because , one of the subsets must contain a solution to the given equation, which contradicts the assumption.
On the other hand, if then and thus . This implies that . Then the set contains a solution to the given equation, which again contradicts the assumption. Thus no such partition exists. If , then can be partitioned by taking , and , and neither of the sets contains a solution to the equation.
The problems on this page are the property of the MAA's American Mathematics Competitions