Let $n$ be a positive integer, and let $x_1, x_2, \dots, x_n$ be distinct positive integers with $x_1 = 1$. Construct an $n \times 3$ table where the entries of the $k$-th row are $x_k, 2x_k, 3x_k$ for $k = 1, 2, \dots, n$. Now follow a procedure where, in each step, two identical entries are removed from the table. This continues until there are no more identical entries in the table. Prove that at least three entries remain at the end of the procedure. Prove that there are infinitely many possible choices for $n$ and $x_1, x_2, \dots, x_n$ such that only three entries remain.
Problem
Source: South African Mathematics Olympiad 2018, Problem 6
Tags: combinatorics
27.07.2018 15:54
It is clear that $1$ remains at the end of the procedure. Let the largest power of two that occurs in the table be $2^k$. (There is at least one power of two, since $x_1 = 1$, and so $2$ appears in the first row of the table.) We note that we must have that $2^k = 2x_m$ for some $m$. This is because we can not have $2^k = 3x_m$, and if $2^k = x_m$, then $2x_m$ is a larger power of two that appears in the table. We see that this implies that $2^k$ appears exactly once in the table, and so remains at the end of the procedure. (There is a unique value for $x_m$ such that $2^k = 2x_m$.) Similarly, the largest power of $3$ in the table remains at the end of the procedure. Consider the sequence $x_1, x_2, \dots, x_9$ given by $x_1 = 1, x_2 = 2, x_3 = 3, x_4 = 4, x_5 = 8, x_6 = 9, x_7 = 12, x_8 = 18, x_9 = 27$. By drawing the table and crossing off duplicate entries, we see that only the entries $1$, $16$, and $81$ remain. Now suppose that for some $n$ and some choice $x_1, x_2, x_3, \dots, x_n$, we have that only $1$, $2^a$ and $3^b$ remain at the end of the procedure. Consider the sequence $y_1, y_2, \dots, y_{3n}$ defined as follows: $y_i = x_i$ if $i \leq n$, $y_i = 2^a x_{i - n}$ if $n < i \leq 2n$ and $y_i = 3^b x_{i - 2n}$ if $2n < i \leq 3n$. When applying the procedure to $y_1, y_2, \dots, y_n$, the numbers $1, 2^a, 3^b$ remain. When applying the procedure to $y_{n + 1}, y_{n + 2}, \dots, y_{2n}$, the numbers $2^a, 2^{2a}, 2^a \cdot 3^b$ remain. When applying the procedure to $y_{2n + 1}, y_{2n + 2}, \dots, y_{3n}$, the numbers $3^b, 2^a \cdot 3^b, 3^{2b}$ remain. Thus when applying the procedure to $y_1, y_2, \dots, y_{3n}$, the numbers $1, 2^{2a}, 3^{2b}$ remain. Edit: for part b), we could just use $n = x_1 = 1$ as the base case