5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (ii) is the definition of partition, seems redundant. $\endgroup$ – Thomas Andrews Nov 10 '15 at 3:27
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 10 '15 at 3:30
  • $\begingroup$ ^^ i) and ii) are giving the definition of partition and the actual problem is stated below. $\endgroup$ – Elliot G Nov 10 '15 at 3:31
  • $\begingroup$ Ok thanks everyone. I just want it to be clear, but yeah it does seem unneccesary. $\endgroup$ – primitiveroot Nov 10 '15 at 3:33
  • $\begingroup$ (i) Isn't the definition of partition, @ElliotG $\endgroup$ – Thomas Andrews Nov 10 '15 at 4:03
2
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.