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 pa for p prime and a = 1 or 2 p4q, p3q2 for distinct primes p, q p2qr for distinct primes p, q, r B pa for p prime and a = 3, 4, 5 or 6 pq, p2q, p2q2, p3q for distinct primes p, q pqr for distinct primes p, q, rNote that 27 = 128 > 95, 253 = 96 > 95, so we do not need to consider pa for a > 6 or paq for a > 4. Also 2333 = 216, so we do not need to consider p3q3. Finally 22325 = 180, 233.5 = 120, so we do not need to consider any paqbrc except pqr and p2qr. It is easy to check that A and B satisfy the condition. [Note that it does not extend to 96 because 253 = 2(243) = 24(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.
© John Scholes
jscholes@kalva.demon.co.uk
30 Dec 2002
Last corrected/updated 30 Dec 02