Problem 1239

Among the numbers under consideration, we call $a$ and $b$ acquaintances if there exist numbers

$$a=c_{0}, c_{1}, c_{2}, \ldots, c_{n-1}, c_{n}=b$$

such that

$$\left|c_{0}-c_{1}\right|=3^{k_{1}},\left|c_{1}-c_{2}\right|=3^{k_{2}}, \ldots,\left|c_{n-1}-c_{n}\right|=3^{k_{n}}$$

where $k_{1}, k_{2}, \ldots, k_{n}$ are integers. The numbers $\left(c_{0}, c_{1}, c_{2}, \ldots, c_{n}\right)$ can also be equal. If $a$ and $b$ are acquaintances, we will call them friends or enemies depending on whether the above $n$ is even or odd. (Specifically, if $|a-b| = 3^{k}$, then $a$ and $b$ are enemies.) It is easily seen that the following rules hold:

(1) If $a$ and $b$ are acquaintances, and $b$ and $c$ are acquaintances, then $a$ and $c$ are also acquaintances.

(2) If $a$ and $b$ are friends, and $a$ and $c$ are friends, then $b$ and $c$ are also friends.

(3) If $a$ and $b$ are enemies, and $a$ and $c$ are enemies, then $b$ and $c$ are friends.

It is far from obvious that the following statement holds:

(4) If $a$ and $b$ are friends, they cannot be enemies.

Suppose, however, that $a$ and $b$ are friends and also enemies. This means that among the given numbers, we can select $c_{1}, c_{2}, \ldots, c_{2 m-1}$ and $d_{1}, d_{2}, \ldots, d_{2 t}$ such that

$$\begin{aligned} & \left|a-c_{1}\right|=3^{k_{1}},\left|c_{1}-c_{2}\right|=3^{k_{2}}, \ldots,\left|c_{2 m-1}-b\right|=3^{k_{2 m}} \\ & \quad\left|a-d_{1}\right|=3^{l_{1}},\left|d_{1}-d_{2}\right|=3^{l_{2}}, \ldots,\left|d_{2 t}-b\right|=3^{l_{2 t+1}} \end{aligned}$$

(with appropriate integers $k_{i}, l_{j}$). Then

$$\begin{aligned} & \left|a-c_{1}\right|=s_{1} \cdot 3^{k_{1}}, \ldots,\left|c_{2 m-1}-b\right|=s_{2 m} \cdot 3^{k_{2 m}} \\ & \left|d_{1}-a\right|=f_{1} \cdot 3^{l_{1}}, \ldots,\left|d_{2 t}-b\right|=f_{2 t+1} \cdot 3^{l_{2 t+1}} \end{aligned}$$

where each $s_{i}, f_{j}$ is either 1 or $(-1)$. Adding the above equalities, we get

$$0=\sum_{i=1}^{2 m} s_{i} \cdot 3^{k_{i}}+\sum_{j=1}^{2 t+1} f_{j} \cdot 3^{l_{j}}$$

Let $M$ be the maximum of the absolute values of $k_{i}, l_{j}$. Multiplying both sides of (5) by $3^{M}$, we obtain

$$0=\sum_{i=1}^{2 m} s_{i} \cdot 3^{k_{i}+M}+\sum_{j=1}^{2 t+1} f_{j} \cdot 3^{l_{j}+M}$$

Since here $k_{i}+M, l_{j}+M \geqq 0$, each term in the sums in (6) is an odd integer. The number of terms, $2 n+2 t+1$, is also odd, so the sum cannot be even (and therefore not 0); this is a contradiction, which proves (4).

To be able to divide our numbers into two groups as desired, we first classify them into classes as follows. Arbitrarily select a number $a_{1}$ from among them, and place $a_{1}$ and its acquaintances in the first class. If there are any numbers left, select one of them, $a_{2}$, and place $a_{2}$ and its acquaintances in the second class. Continuing this process, we can eventually classify all numbers into $r$ classes, where the classes consist of $a_{1}, a_{2}, \ldots, a_{r}$ and their acquaintances. Numbers in different classes never have a difference of the form $3^{k}$; if $a$ is in the $i$-th class and $b$ is in the $j$-th class, and $|a-b|=3^{k} (i \neq j, k$ integer), then $a$ and $b$ are acquaintances. However, $a_{i}$ and $a$, as well as $b$ and $a_{j}$, are also acquaintances, so by (1), $a_{i}$ and $a_{j}$ are acquaintances, which is impossible.

It is therefore sufficient to divide the numbers in the same class into two groups as desired. For the $p$-th class, place $a_{p}$ and the numbers friendly with $a_{p}$ in the first group, and the numbers hostile to $a_{p}$ in the second group. By (2), any two (different) numbers in the first group are friends, and by (3), the same is true for any two numbers in the second group. By (4), numbers in the same group cannot be enemies, so their difference is certainly not of the form $3^{k}$.

Remarks. 1. The statement of the problem is also true if $3^{k}$ is replaced by $a^{k}$ for any odd $a$. With some modifications to the given proof, it can also be shown that not only a finite number, but any number (e.g., all!) real numbers can be divided into two groups in the desired manner.

2. Consider the graph whose vertices are the real numbers in the problem, and two vertices are connected by an edge if the difference of the corresponding numbers is of the form $3^{k}$. According to the problem, this graph is bipartite. It is well known that a graph is bipartite if and only if every cycle in it has an even number of edges. In the course of the above proof, we essentially showed that this graph has no cycles with an odd number of edges (1. (4)), and then used this to prove the bipartiteness of the graph.