Maths Olympiad Prep

Library / /126 of 133

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Saudi Arabia

Let XX be a set of rational numbers satisfying the following two conditions:
(a) The set XX contains at least two elements,
(b) For any x,yx, y in XX, if xyx \neq y then there exists zz in XX such that either xzyz=2\left|\frac{x-z}{y-z}\right|=2 or yzxz=2\left|\frac{y-z}{x-z}\right|=2.
Prove that XX contains infinitely many elements.

Solution

The condition (b) tells that if xyx \neq y are in XX, then at least one of the four numbers
z1=x(yx),z2=x+13(yx),z3=x+23(yx),z4=x+2(yx)z_1 = x - (y - x), \quad z_2 = x + \frac{1}{3}(y - x), \quad z_3 = x + \frac{2}{3}(y - x), \quad z_4 = x + 2(y - x),
Figure 1
is in XX.

Assume that XX is finite and let x0x_0 be the smallest element of XX. By condition (a), the set X\{x0}X \backslash \{x_0\} is nonempty. Consider a map
f:X\{x0}X\{x0} f: X \backslash \{x_0\} \rightarrow X \backslash \{x_0\}
which satisfies, for yX\{x0}y \in X \backslash \{x_0\}, the condition
f(y){x0+13(yx0),x0+23(yx0),x0+2(yx0)}X. f(y) \in \{x_0 + \frac{1}{3}(y - x_0), x_0 + \frac{2}{3}(y - x_0), x_0 + 2(y - x_0)\} \cap X .
Notice that f(y)f(y) is defined for all yX\{x0}y \in X \backslash \{x_0\} by condition (b) since x0(yx0)<x0x_0 - (y - x_0) < x_0 is not in XX.

Now, fix an element y0X\{x0}y_0 \in X \backslash \{x_0\} and define by induction a0=y0x0a_0 = y_0 - x_0 and an+1=f(x0+an)x0a_{n+1} = f(x_0 + a_n) - x_0 for all nN0n \in \mathbb{N}_0. Clearly, the sequence (ana_n) is well defined and positive and we have, for each nN0n \in \mathbb{N}_0, either
an+1=13an,oran+1=23an,oran+1=2an. a_{n+1} = \frac{1}{3} a_n, \quad \text{or} \quad a_{n+1} = \frac{2}{3} a_n, \quad \text{or} \quad a_{n+1} = 2 a_n .
Therefore, for each positive integers m,nm, n, there exist non-negative integers p,qp, q with p+q>0p + q > 0 such that
am+n=2p3qam. a_{m+n} = \frac{2^p}{3^q} a_m .
Because X\{x0}X \backslash \{x_0\} is finite, there exist two positive integers m0,n0m_0, n_0 such that am0+n0=am0a_{m_0 + n_0} = a_{m_0}. Hence the corresponding two non-negative integers p0,q0p_0, q_0 with p0+q0>0p_0 + q_0 > 0 satisfy
1=2p03q0, 1 = \frac{2^{p_0}}{3^{q_0}},
which is impossible.

This proves that XX 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.