IMO 1999 SL A4

Origin: BLR | Category: Algebra

Problem

Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that for any two integers x, y taken from two different subsets, the number x2 −xy +y2 belongs to the third subset.

Solution

Define f(x, y) = x2 −xy + y2. Let us assume that three such sets A, B, and C do exist and that w.l.o.g. 1, b, and c (c > b) are respectively their smallest elements. Lemma 1. Numbers x, y, and x + y cannot belong to three different sets. Proof. The number f(x, x + y) = f(y, x + y) must belong to both the set containing y and the set containing x, a contradiction. Lemma 2. The subset C contains a multiple of b. Moreover, if kb is the smallest such multiple, then (k −1)b \inB and (k −1)b + 1, kb + 1 \inA. Proof. Let r be the residue of c modulo b. If r = 0, the first statement automatically holds. Let 0 < r < b. In that case r \inA, and c −r is then not in B according to Lemma 1. Hence c −r \inA and since b | c −r, it follows that b | f(c −r, b) \inC, thus proving the first statement. It follows immediately from Lemma 1 that (k −1)b \inB. Now by Lemma 1, (k −1)b + 1 = kb −(b −1) must be in A; similarly, kb + 1 = [(k −1)b + 1] + b \inA as well. Let us show by induction that (nk −1)b + 1, nkb + 1 \inA for all integers n. The inductive basis has been shown in Lemma 2. Assuming that [(n − 1)k −1]b + 1 \inA and (n −1)kb + 1 \inA, we get that (nk −1)b + 1 = ((n −1)kb + 1) + (k −1)b = [((n −1)k −1)b + 1] + kb belongs to A and

nkb + 1 = ((nk −1)b + 1) + b = ((n −1)kb + 1) + kb ⇒nkb + 1 \inA. This finishes the inductive step. In particular, f(kb, kb+1) = (kb+1)kb+1 \inA. However, since kb \inC, kb+1 \inA, it follows that f(kb, kb+1) \inB, which is a contradiction.