6.1 Combinatorial Arguments in Set Theory and Geometry 293order. These numbers, together with the differencesxi−x 1 ,i= 2 , 3 ,...,|X|, must all
be distinct elements ofM. Altogether, there are 2|X|−1 such numbers, implying that
2 |X|− 1 ≤40, or|X|≤20. Also, 3|X|≥|X|+|Y|+|Z|=40, so|X|≥14.
There are|X|·|Y|≥|X|×^12 ( 40 −|X|)pairs inX×Y. The sum of the numbers in
each pair is at least 2 and at most 80, a total of 79 possible values. Because 14≤|X|≤ 20
and the functionf(t)=^12 t( 40 −t)is concave on the interval[ 14 , 20 ], we have that
|X|( 40 −|X|)
2≥min{
14 · 26
2
,
20 · 20
2
}
= 182 > 2 · 79.
We can use the pigeonhole principle to find three distinct pairs(x 1 ,y 1 ),(x 2 ,y 2 ),(x 3 ,y 3 )∈
X×Ywithx 1 +y 1 =x 2 +y 2 =x 3 +y 3.
If any of thexi’s were equal, then the correspondingyi’s would be equal, which is
impossible because the pairs(xi,yi)are distinct. We may thus assume, without loss of
generality, thatx 1 <x 2 <x 3. For 1≤j<k≤3, the valuexk−xjis inMbut cannot be
inXbecause otherwisexj+(xk−xj)=xk. Similarly,yj−yk∈/Yfor 1≤j<k≤3.
Therefore, the three common differencesx 2 −x 1 =y 1 −y 2 ,x 3 −x 2 =y 2 −y 3 , and
x 3 −x 1 =y 1 −y 3 are inM(X∪Y)=Z. However, settinga=x 2 −x 1 ,b=x 3 −x 2 ,
andc=x 3 −x 1 , we havea+b=cwitha, b, c∈Z, a contradiction.
Therefore, it is impossible to partitionMinto three sets with the desired property.
Let us show that this can be done with four sets. The question is how to organize the 40
numbers.
We write the numbers in base 3 as...at...a 3 a 2 a 1 with only finitely many digits not
equal to 0. The setsA 1 ,A 2 ,A 3 ,...are constructed inductively as follows.A 1 consists of
all numbers for whicha 1 =1. Fork>1 the setAkconsists of all numbers withak= 0
that were not already placed in other sets, together with the numbers that haveak= 1
andai=0 fori<k. An alternative description is thatAkconsists of those numbers that
are congruent to some integer in the interval(^123 k−^1 , 3 k−^1 ]modulo 3k. For our problem,
A 1 ={ 1 , 11 , 21 , 101 , 111 , 121 , 201 , 211 , 221 , 1001 , 1011 , 1021 , 1101 , 1111 },
A 2 ={ 2 , 10 , 102 , 110 , 202 , 210 , 1002 , 1010 , 1102 , 1110 },
A 3 ={ 12 , 20 , 22 , 100 , 1012 , 1020 , 1022 , 1100 },
A 4 ={ 112 , 120 , 122 , 200 , 212 , 220 , 222 , 1000 }.Using the first description of these sets, we see that they exhaust all positive integers.
Using the second description we see that(Ak+Ak)∩Ak=∅,k≥1. HenceA 1 ,A 2 ,A 3 ,
A 4 provide the desired example, showing that the answer to the problem isn=4.
Remark.In general, for positive integersnandkand a partition of{ 1 , 2 ,...,k}inton
sets, a triple(a,b,c)such thata, b, andcare in the same set anda+b=cis called a
Schur triple. Schur’s theorem proves that for eachnthere exists a minimal numberS(n)