MathDB

6

Part of 2018 South Africa National Olympiad

Problems(1)

SAMO Problem 6: Three entries remain after removing duplicates

Source: South African Mathematics Olympiad 2018, Problem 6

7/27/2018
Let nn be a positive integer, and let x1,x2,…,xnx_1, x_2, \dots, x_n be distinct positive integers with x1=1x_1 = 1. Construct an n×3n \times 3 table where the entries of the kk-th row are xk,2xk,3xkx_k, 2x_k, 3x_k for k=1,2,…,nk = 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 nn and x1,x2,…,xnx_1, x_2, \dots, x_n such that only three entries remain.
combinatorics