29th IMO 1988 shortlist Problem 20 Find the smallest n such that if {1, 2, ... , n} is divided into two disjoint subsets then we can always find three distinct numbers a, b, c in the same subset with ab = c.
96. Solution We show first that however we partition {1, 2, 3, ... , 96}, one part always contains three distinct numbers a, b, c with ab = c. Suppose that we have a partition A, B with neither A nor B containing such a, b, c. We will obtain a contradiction. Without loss of generality 2 belongs to A. Case 1 3 and 4 belong to A. Then 2.3 = 6, 2.4 = 8, and 3.4 = 12 belong to B. Hence 6.8 = 48, and 6.12 = 96 belong to A. Contradiction (2.48 = 96). Case 2 3 belongs to A, 4 belongs to B. Then 2.3 = 6 belongs to B, 4.6 = 24 belongs to A. So 12 = 24/2 belongs to B. So 4.12 = 48 belongs to A. Contradiction (2.24 = 48). Case 3 4 belongs to A, 3 belongs to B. Then 2.4 = 8 belongs to B, 3.8 = 24 belongs to A. So 24/2 = 12 and 24/4 = 6 belong to B. Hence 3.6 = 18 and 3.12 = 36 belong to A. Contradiction (2.18 = 36). Case 4 3, 4 belong to B. Then 3.4 = 12 belongs to A. So 12/2 = 6 belongs to B. Hence 4.6 = 24 belongs to A. Contradiction (2.12 = 24). Next we show that there is a partition of (1, 2, 3, ... , 95} such that neither part contains such a, b, c. Take A p a for p prime and a = 1 or 2 p 4 q, p 3 q 2 for distinct primes p, q p 2 qr for distinct primes p, q, r B p a for p prime and a = 3, 4, 5 or 6 pq, p 2 q, p 2 q 2 , p 3 q for distinct primes p, q pqr for distinct primes p, q, r Note that 2 7 = 128 > 95, 2 5 3 = 96 > 95, so we do not need to consider p a for a > 6 or p a q for a > 4. Also 2 3 3 3 = 216, so we do not need to consider p 3 q 3 . Finally 2 2 3 2 5 = 180, 2 3 3.5 = 120, so we do not need to consider any p a q b r c except pqr and p 2 qr. It is easy to check that A and B satisfy the condition. [Note that it does not extend to 96 because 2 5 3 = 2(2 4 3) = 2 4 (2.3).] Finally for n < 95, A ⊆ {1, 2, ... , n} and B ⊆ {1, 2, ... , n} provide a partition of {1, 2, ... , n} with neither art containing such a, b, c. 29th IMO shortlist 1988 © John Scholes jscholes@kalva.demon.co.uk 30 Dec 2002 Last corrected/updated 30 Dec 02