Problem

Source: South African Mathematics Olympiad 2018, Problem 6

Tags: combinatorics



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.