### 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.

**Answer**

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