IMO 1988 SL 20

Origin: MON

Problem

Find the least natural number n such that if the set {1, 2, . . ., n} is arbitrarily divided into two nonintersecting subsets, then one of the subsets contains three distinct numbers such that the product of two of them equals the third.

Solution

Suppose that An = {1, 2, . . ., n} is partitioned into Bn and Cn, and that neither Bn nor Cn contains 3 distinct numbers one of which is equal to the product of the other two. If n \geq96, then the divisors of 96 must be split up. Let w.l.o.g. 2 \inBn. There are four cases. (i) 3 \inBn, 4 \inBn. Then 6, 8, 12 \inCn ⇒48, 96 \inBn. A contradiction for 96 = 2 \cdot 48. (ii) 3 \inBn, 4 \inCn. Then 6 \inCn, 24 \inBn, 8, 12, 48 \inCn. A contradiction for 48 = 6 \cdot 8. (iii) 3 \inCn, 4 \inBn. Then 8 \inCn, 24 \inBn, 6, 48 \inCn. A contradiction for 48 = 6 \cdot 8. (iv) 3 \inCn, 4 \inCn. Then 12 \inBn, 6, 24 \inCn. A contradiction for 24 = 4 \cdot 6. If n = 95, there is a very large number of ways of partitioning An. For example, Bn = {1, p, p2, p3q2, p4q, p2qr | p, q, r = distinct primes}, Cn = {p3, p4, p5, p6, pq, p2q, p3q, p2q2, pqr | p, q, r = distinct primes}. Then B95 = {1, 2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 48, 49, 53, 59, 60, 61, 67, 71, 72, 73, 79, 80, 83, 84, 89, 90}.