Non-Splittable Subsets

Let the desired $3$ -element subset be $S = {a, b, c}$ where $a < b < c$ . Thus for any $n \in N \setminus S, S \cup \{ n \}$ cannot be split into $2$ sets such that the sum of each set is the same. First, $S \cup \{ n \}$ cannot be split into $2$ sets of $2$ . Thus there does not exist $n \in N \setminus S$ for any of the following to be true: $a+b=c+n, b+c=a+n, c+a=b+n.$

Thus each of $a+b-c, b+c-a, c+a-b$ must be either out of the domain $[1, 2012]$ or be equal to one of $a, b, c$ . Since $1 \leq a < c+a-b < c \geq 2012$ , $c+a-b$ must be equal to $b$ . So $c+a-b=b \Rightarrow c+a=2b$ . Now we let $b=a+k, c=a+2k$ where $k$ is a positive integer. Then since $a+b-c < a$ and $b+c-a > c$ must be out of the domain $[1, 2012 ]$ , we must have $a+b-c<1, b+c-a>2012 \Rightarrow a+a+k-(a+2k)<1, a+k+a+2k-a>2012,$ which solves to $2012-3k < a \leq k$ .

Now we consider the other possible way of partitioning the $4$ -element set. If the $4$ -element set is partitioned into $1$ -element set and a $3$ -element set such that the sum of each is equal, the element in the $1$ -element set must be the biggest element among the $4$ because they are all positive integers. Thus we cannot have any $n \in N \setminus S$ such that any of the following is true: $a+b+c=n, a+b+n=c.$

So each of $a+b+c, c-a-b$ must be either out of the range $[1, 2012]$ or equal to one of $a, b, c$ . Thus $a+b+c>2012 \Rightarrow 3a+3k>2012 \Rightarrow a \geq 671-k$ and either $c-a-b=a \Rightarrow a+2k-a-(a+k)=a \Rightarrow a=\frac{k}{2}$ or $c-a-b=b \Rightarrow a+2k-a-(a+k)=a+k \Rightarrow a=0$ (reject) or $c-a-b<1 \Rightarrow a+2k-a-(a+k) \leq 0 \Rightarrow a \geq k \Rightarrow a=k$ because $a \leq k$ from earlier. As a result, $a=k$ or $a= \frac{k}{2}$ , under the restriction $2012-3k<a, a \geq 671-k$ , and $a+2k \leq 2012$ .

When $a=k$ , $2012-3k<a$ gives $k \geq 504$ , $a \geq 671-k$ gives $k \geq 336$ , and $a+2k \leq 2012$ gives $k \leq 670$ . So $504 \leq k \leq 670$ , and for each $k$ there is only one set $\{a, b, c \}$ , thus there are $670-504+1=167$ sets. [This gives us sets of the form $\{a, 2a, 3a\}$ . - Calvin]

When $a=\frac{k}{2}$ , $2012-3k<a$ gives $k \geq 575$ , $a \geq 671-k$ gives $k \geq 448$ , and $a+2k \leq 2012$ gives $k \leq 804$ . So $575 \leq k \leq 804$ . Since $k$ must be even, there are $\frac{804-576}{2} +1 = 115$ sets. [This gives us sets of the form $\{a, 3a, 5a\}$ . - Calvin]

Thus there are $167+115 = 282$ sets in total.

Let $S$ be a non-4-splittable set. Write $S = \{ a,b,c \}$ with $a < b < c$ . Note that $d = a+c-b$ satisfies $a < d < c$ , and $d$ would split $S$ if it were in $N \setminus S$ since $a+c = b+d$ , so the only possibility is that $d = b$ . So $a+c = 2b$ . Taking $x = b-a$ , we can write $S = \{ a, a+x, a+2x \}.$

Note that $a-x$ would split $S$ if it were in $N \setminus S$ , since $(a-x) + (a+2x) = a + (a+x).$ Since $a-x < a$ , the only possibility is that this integer is $\le 0$ , so $x \ge a$ .

But now note that $x-a$ would split $S$ if it were in $N \setminus S$ , since $(x-a) + a + (a+x) = a+2x$ . Since $0 \le x-a < a+x$ , there are only two possibilities left: $x-a = 0$ or $x-a = a$ . This leads to $S = \{ a, 2a, 3a \}$ and $S = \{ a, 3a, 5a \}$ respectively.

It's easy to check in the first case that $S$ is not splittable if and only if $3a \le 2012$ (to make it a subset of $N$ ) and $4a \ge 2013$ (so that it doesn't split $S$ ), and in the second case $S$ is not splittable if and only if $5a \le 2012$ and $7a \ge 2013$ .

In the first case the admissible values of $a$ are between $504$ and $670$ inclusive, and in the second case the admissible values are between $288$ and $402$ inclusive. This gives $167 + 115 = \fbox{282}$ sets in all.

Main idea : Brute force all numbers that a 4-splittable set candidate might "take" in order to form a set that can be split into equal sums. For example, with a set $\{a,b,c\}$ and $a<b<c$ , the number $a+c-b$ might make the set to be a 4-splittable.

Complete proof :

Let's call a set of three integers from $N$ be a 4-splittable set candidate, or candidate for short. For a candidate set $S$ , let's call a number $n$ (not necessarily in $N \backslash S$ ) a witness if $S \oplus \{n\}$ is a 4-element multiset that can be partitioned into two sets with equal sums. A multiset is simply a set where the elements might repeat (like $\{1,1,2\}$ ; as a set is it indistinguishable with $\{1,2\}$ ). For a candidate set $S$ and a witness $n$ , call a partition of $S \oplus \{n\}$ into two subsets with equal sum as a split .

A set $S$ is not 4-splittable if and only if its witnesses are not in $N \backslash S$ . Call a witness that is in $N \backslash S$ as a proof , and a fake otherwise.

Suppose that our candidate set is $S = \{a,b,c\}$ where $a < b < c$ ; we assume that it is not 4-splittable. Note that $a+c-b$ is a witness as $\{a,c\}, \{b,a+c-b\}$ is a split. Also, since $a < b < c$ , we have $a+c-b > a+b-b = a$ and $a+c-b < b+c-b = c$ , so $a < a+c-b < c$ . Every number between $a$ and $c$ must belong to $N$ , and we have shown that $a+c-b \neq a,c$ , so $a+c-b$ is a proof unless $b=a+c-b$ in which $a+c-b \in S$ . Since we want to make all witnesses fakes, we need to have $b = a+c-b$ . Then we can let $b-a = k$ , so $c-b = k$ and $S = \{b-k, b, b+k\}$ .

Next, $2k-b$ is a witness as $\{b+k\}, \{b, b-k, 2k-b\}$ is a split. Also, since $b, b-k > 0$ and $b+k = b + (b-k) + (2k-b)$ , we must have $2k-b < b+k$ . So this witness is a proof except in three cases:

• Case 1: $2k-b = b$

Then $b = k$ and $S = \{0, k, 2k\}$ , impossible.

• Case 2: $2k-b = b-k$

Then $b = \frac{3}{2}k$ . Letting $k = 2m$ , we have $b = 3m$ and so $S = \{m, 3m, 5m\}$ .

• Case 3: $2k-b \le 0$

Then $b-2k \ge 0$ . Note that $b-2k$ is also a witness as $\{b+k, b-2k\}, \{b, b-k\}$ is a split, and since $k > 0$ , we have $b-2k < b-k$ . Thus $b-2k$ is a proof except when $b-2k \le 0$ . Combined with our assumption of this case, we need $b-2k = 0$ , so $b = 2k$ and so $S = \{k, 2k, 3k\}$ .

Next, note that $b+2k$ is a witness as $\{b+2k, b-k\}, \{b+k, b\}$ is a split. This is equal to $7m$ in case 2 or $4k$ in case 3. Since $b+2k > b+k$ , this is a proof unless $b+2k > 2012$ . Thus we need $7m > 2012 \implies m \ge 288$ in case 2 and $4k > 2012 \implies k \ge 504$ in case 3.

Now, we also need $b+k \le 2012$ . This means $5m \le 2012 \implies m \le 402$ in case 2 and $3k \le 2012 \implies k \le 670$ in case 3. So from case 2 we have $288 \le m \le 402$ , for a total of $402-288+1 = 115$ sets, and from case 3 we have $504 \le k \le 670$ , for a total of $670-504+1=167$ sets. It just remains to prove that they are indeed not 4-splittable.

Suppose we have a set $S = \{a,b,c\}$ with $0 < a < b < c$ , a witness $n$ , and a split into $A, B$ where $n \in A$ . Then there are only eight possible witnesses. Each of $a,b,c$ goes into some of $A,B$ , so each element has $2$ choices; combined overall we have $2^3 = 8$ possibilities. Also, after we have assigned $a,b,c$ into the subsets, the value of $n$ is unique: it's simply the sum of elements in $B$ , minus the sum of elements in $A$ not including $n$ . Also, we can see that each term either contributes positively or negatively into the value of $n$ , so the value of $n$ can be expressed as $(-1)^pa + (-1)^qb + (-1)^rc$ where $p,q,r$ are integers.

However, some witnesses are trivially excluded as potential proofs. The witnesses $-a-b-c, a-b-c, -a+b-c$ are excluded as they must be less than zero. For example, for $a-b-c$ , since $a<c$ we have $a-c < 0$ , and adding with $-b < 0$ we have $a-b-c < 0$ . The other two cases are similar.

On the other end of the spectrum, if $a+b+c$ is a proof then $-a+b+c$ is also a proof. We prove this by contraposition: if $-a+b+c$ is fake then $a+b+c$ is fake. Since $-a+b+c > -a+a+c = c$ , the only way $-a+b+c$ can be a fake is if $-a+b+c > 2012$ , but if so then $a+b+c > -a+b+c > 2012$ is also a fake. So this makes our search to only four witnesses: $a+b-c, -a-b+c, a-b+c, -a+b+c$ .

For case 2, namely $S = \{a,b,c\} = \{m, 3m, 5m\}$ where $288 \le m \le 402$ , the four witnesses we need to check are $a+b-c = -m < 0$ , $-a-b+c = m \in S$ , $a-b+c = 3m \in S$ , or $-a+b+c = 7m \ge 7 \cdot 288 > 2012$ .

For case 3, namely $S = \{a,b,c\} = \{k, 2k, 3k\}$ where $504 \le k \le 670$ , the four witnesses we need to check are $a+b-c = 0$ , $-a-b+c = 0$ , $a-b+c = 2k \in S$ , or $-a+b+c = 4k \ge 4 \cdot 504 > 2012$ .

So we have shown that all these $115+167$ sets are indeed not 4-splittable, and so the number of non-4-splittable sets is $115+167 = \boxed{282}$ .

Motivation : Well, this one is pretty straightforward, just bash all possible witnesses. To be honest, I didn't think of checking them when I did the problem; those last 5 paragraphs were written on the spot when I realized that there are only 8 possible witnesses for any candidate set.

Generalization : Of course, changing $2012$ to some other value is pretty trivial. It will simply change the bounds $288, 402, 504, 670$ . What's more interesting is changing $3$ , as in the number of elements of $S$ . However, for lower values, it becomes rather trivial (for $1$ element all subsets are not "2-splittable" as the only two witnesses are the element itself or its negation which is obviously negative; for $2$ elements the interesting witnesses are simply the sum and the difference, and a simple casework like above will easily lead to $\{k, 2k\}$ where $2k \le 2012 < 3k$ ). And for higher values, it becomes a boring casework of checking the witnesses. An interesting result is that the sets $\{k, 2k, \ldots, nk\}$ where $(n+1)k > 2012$ and $\{m, 3m, \ldots, (2n-1)m\}$ where $(2n+1)m > 2012$ are always solutions, although there might be more; I'm already feeling lazy to check whether there are more. Or perhaps I miss something that can simplify it...

Suppose S={a,b,c} such that $1 \leq a<b<c \leq 2012$ . Therefore, S is not 4-splittable if all of the following conditions are satisfied:

$a+b-c<1$ (1)

$c+a-b=b$ (2)

$c+b-a>2012$ (3)

$c-a-b=a$ or $c-a-b=b$ or $c-a-b<1$ (4)

From (2), we have $c=2b-a$ , subtitute to (1),(4), we have

$b-2a>-1$ (1')

$b-2a=a$ or $b-2a=b$ or $b-2a<1$ (4')

$b-2a=b$ leads to $a=0$ , so we only have to consider 2 cases:

Case 1: $b-2a=a$ , so $b=3a$ and from (2), $c=5a$

Subtitute these equations to (3) and $c \leq 2012$ , we have $288 \leq a \leq 402$

Therefore, there are $402-288+1=115$ results in this case.

Case 2: $b-2a<1$ . From (1'), we have $b-2a=0$ , so $b=2a$ and $c=3a$ .

Subtitute these equations to (3) and $c \leq 2012$ , we have $504 \leq a \leq 670$

Therefore, there are $670-504+1=167$ results in this case.

The answer is $115+167=282$ .