Maths Olympiad Prep

Library / /228 of 397

Algebra Difficulty 6.0 National Olympiad Prove it Taiwan

Let Z\mathbb{Z} and Q\mathbb{Q} be the sets formed by integers and rational numbers, respectively. For subsets X,YX, Y of Q\mathbb{Q}, define X+YX + Y as:
X+Y:={x+yxX,yY}. X + Y := \{x + y \mid x \in X, y \in Y\}.
(a) Can Z\mathbb{Z} be partitioned into three nonempty subsets A,B,CA, B, C such that A+B,B+C,C+AA+B, B+C, C+A are pairwise disjoint?
(b) Can Q\mathbb{Q} be partitioned into three nonempty subsets A,B,CA, B, C such that A+B,B+C,C+AA+B, B+C, C+A are pairwise disjoint?

Solution

(a) Yes. Here is an example:
A={3kkZ},B={3k+1kZ},C={3k+2kZ}. A = \{3k \mid k \in \mathbb{Z}\}, \quad B = \{3k + 1 \mid k \in \mathbb{Z}\}, \quad C = \{3k + 2 \mid k \in \mathbb{Z}\}.

(b) No. Suppose Q\mathbb{Q} can be partitioned into three nonempty subsets A,B,CA, B, C such that A+B,B+C,C+AA+B, B+C, C+A are pairwise disjoint. Note that for all aA,bB,cCa \in A, b \in B, c \in C we have
a+bcC,b+caA,c+abB.(1) a + b - c \in C, \quad b + c - a \in A, \quad c + a - b \in B. \qquad (1)
Indeed a+bcAa + b - c \notin A since (A+B)(A+C)=(A+B) \cap (A+C) = \emptyset, and likewise a+bcBa + b - c \notin B, hence a+bcCa + b - c \in C. That is, A+BC+CA+B \subset C+C. Similarly, we have B+CA+AB+C \subset A+A, C+AB+BC+A \subset B+B.
The reverse inclusion also holds. Let a,aA,bB,cCa, a' \in A, b \in B, c \in C. By (1) we get a+cbBa' + c - b \in B, and since aA,cCa \in A, c \in C, applying (1) again gives
a+ab=a+(a+cb)cC. a + a' - b = a + (a' + c - b) - c \in C.

A+B=C+CA + B = C + C, B+C=A+AB + C = A + A, C+A=B+BC + A = B + B.
Furthermore, without loss of generality assume 0A0 \in A. Then B={0}+BA+BB = \{0\} + B \subset A + B and C={0}+CA+CC = \{0\} + C \subset A + C. Since B+CB + C is disjoint from A+BA + B and A+CA + C respectively, B+CB + C is disjoint from BB and CC respectively. Hence B+CB + C is contained in Z(BC)=A\mathbb{Z}\setminus(B \cup C) = A. Since B+C=A+AB + C = A + A, we obtain A+AAA + A \subset A. On the other hand, A={0}+AA+AA = \{0\} + A \subset A + A, so we obtain A=A+A=B+CA = A + A = B + C.
Therefore A+B+C=A+A+A=AA+B+C = A+A+A = A, and B+B=C+A,C+C=A+BB+B = C+A, C+C = A+B
from which we can derive B+B+B=A+B+C=A,C+C+C=A+B+C=AB+B+B = A+B+C = A, C+C+C = A+B+C = A.
In particular, if for any rQ=ABCr \in \mathbb{Q} = A \cup B \cup C then 3rA3r \in A.
But this conclusion is impossible. Take any bBb \in B (BB being a nonempty subset) and let r=b3Qr = \frac{b}{3} \in \mathbb{Q}, then
b=3rAb = 3r \in A yields a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.