# Partition of $S = \{1,2,\dots, 3n\}$ in to three subsets $A, B, C$ such that $|A| = |B| = |C| = n$

Let $n$ be a positive integer and consider the set $S = \{1,2,\dots ,3n\}$. Show that, for every partition of $S$ into 3 subsets $A, B, C$ such that:

i) $|A| = |B| = |C| = n$ (here $|X|$ denotes the number of elements of set $X$)

ii) $A \cap B = B \cap C = C \cap A = \varnothing$ and $A \cup B \cup C = S$

there exist 3 elements $a \in A, b \in B, c \in C$ such that one of $a, b, c$ equals sum of the two other elements.

• (ii) is the definition of partition, seems redundant. – Thomas Andrews Nov 10 '15 at 3:27
• There are only 3n element so to divide them into 3 sets of n each means the sets must be distinct so ii) didn't need to be stated. – fleablood Nov 10 '15 at 3:30
• ^^ i) and ii) are giving the definition of partition and the actual problem is stated below. – Elliot G Nov 10 '15 at 3:31
• Ok thanks everyone. I just want it to be clear, but yeah it does seem unneccesary. – primitiveroot Nov 10 '15 at 3:33
• (i) Isn't the definition of partition, @ElliotG – Thomas Andrews Nov 10 '15 at 4:03

Suppose otherwise.

Write $A = \{a_1, \dotsc, a_n\}$, $B = \{b_1, \dotsc, b_n\}$, and $C = \{c_1, \dotsc, c_n\}$, each indexed increasingly, such that $a_1 < b_1 < c_1$. Thus $a_1 = 1$. Set $k = b_1 - 1$, so that $\{1, \dotsc, k\} \subseteq A$.

Now, for any $b \in B$, if any of $b+1, \dotsc, b+k$ are in $C$, then we have a forbidden triple. Similarly for any $c \in C$, the succeeding $k$ elements cannot be in $B$. So between any elements of $B$ and of $C$ there must be at least $k$ elements of $A$.

Consider any $c \in C$ whose predecessor is not in $C$, i.e. so that $c - 1 \notin C$. Then before $c$ we have at least $k$ elements of $A$; in particular $c - k \in A$. If $(c - k) + b_1 = c + 1$ is in $C$, then we have a forbidden triple. Similarly, $(c - (k-1)) + b-1 = c + 2, \dotsc, (c-1)+b_1 = c+k$ cannot be in $C$. So we can have at most one element of $C$ occur successively, whose $k$ predecessors and $k$ successors are all in $A$.

Thus, the most compactly that the elements of $C$ can occur is in a pattern like this: $$\underbrace{A\dotsm A}_k C \underbrace{A\dotsm A}_k C \dotsm\underbrace{A\dotsm A}_k C,$$ where the last entry is $3n$ itself. If any elements of $B$ were interspersed, even more elements of $A$ would have to appear.

For each element of $C$ we have at least $k$ elements of $A$, contradicting that $|C| = |A|$, unless $k = 1$. Even then, the only way to have just $n$ elements of $A$ appear is with the pattern $$AC AC \dotsm AC$$ where $c_n = 3n$, which contradicts that $1 \in A$.

• How can you assure that $3n \in C$? – primitiveroot Nov 12 '15 at 11:48
• Otherwise another element of $A$ is required afterwards, which would mean at least $n+1$ elements are in $A$. – Nick Matteo Nov 12 '15 at 12:46