Let be a set of rational numbers satisfying the following two conditions:
(a) The set contains at least two elements,
(b) For any in , if then there exists in such that either or .
Prove that contains infinitely many elements.
Solution
The condition (b) tells that if are in , then at least one of the four numbers
,
is in .
Assume that is finite and let be the smallest element of . By condition (a), the set is nonempty. Consider a map
which satisfies, for , the condition
Notice that is defined for all by condition (b) since is not in .
Now, fix an element and define by induction and for all . Clearly, the sequence () is well defined and positive and we have, for each , either
Therefore, for each positive integers , there exist non-negative integers with such that
Because is finite, there exist two positive integers such that . Hence the corresponding two non-negative integers with satisfy
which is impossible.
This proves that contains infinitely many elements.
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.