We represent the card distribution as a sequence of $100$ symbols from the set $S=\{r,w,b\}$ (if the $i$'th symbol is $x\in S$, then $i$ is in the box with color whose first letter is $x$ ). A "run" is a maximal subsequence of consecutive symbols which are all the same. If $x\ne y\in S$ and at some point an $x$-run is followed by a $y$-run, then all $x$-runs are followed by $y$-runs (except if it ends the $100$-symbol string, of course), and the same holds if we replace "are followed by" with "are preceded by". Also notice that if $x,y,z$ is a permutation of $S$ and $xx$ appears in the string, then $yz$ cannot appear. There are now two possibilities: (1) No $xx$ ever appears in the string for $x\in S$ If the string begins with $x$, then it can't continue $xyx$, because then it would have only $x$ and $y$, meaning that one of the boxes is not used. This means that for some permutation $x,y,z$ of $S$ the string must be $xyzxyz\ldots$, and there are $6$ possibilities. (2) There is some $x\in S$ for which $xx$ appears in the string Assume $x,y,z$ is a permutation of $S$ s.t. in our string $x$-runs are always followed by $y$-runs and always preceded by $z$-runs. An $x$-run in which $xx$ appears cannot be followed by a $y$-run and then a $z$-run because then we could find $yz$, so it's followed by at most a $y$-run. In the same way, it's preceded by at most a $z$-run. By applying these same observations to the $z$ and $y$-runs which precede/follow $x$, we conclude that they must be made up of exactly one symbol, or, in other words, our string must look like this: $zxx\ldots xy$. Again, there are $6$ possibilities for such an arrangement, according to the permutation $x,y,z$ of $S$ that we choose. This means that in total, there are $12$ ways to arrange the cards, and they have been described above.

Inspired by some generating-function solutions, can the following observation be completed into a solution? : We are looking for non-zero polynomials $ f_{1,2,3}$ with coefficients either 0 or 1, such that: (i) $ f_{1}(x)+f_{2}(x)+f_{3}(x)=\sum_{i=1}^{100} x^i$, and (ii) The exponents in $ f_{1}f_{2}$, $ f_{1}f_{3}$, $ f_{2}f_{3}$ are distinct. I tried to found some nice mathematical reformulation of the 2nd condition and couldn't find any... [and maybe generating functions aren't supposed to solve everything...]

For any sets $X$ and $Y$, let $X+Y = \{ x + y : x \in X, y \in Y\}$. Lemma: For any sets of real numbers $X$ and $Y$, $|X+Y| \geq |X| + |Y| - 1$, with equality holding if and only if $|X| = 1$, $|Y| = 1$, or the elements of $X$ and $Y$ form arithmetic sequences with the same common difference. Proof: Let $X = \{x_1, x_2, \ldots, x_m\}$ and $Y = \{y_1, y_2, \ldots, y_n\}$. Since $\{x_1 + y_1, x_2 + y_1, \ldots, x_m + y_1, x_m + y_2, \ldots, x_m + y_n\} \subseteq X+Y$, and $x_1 + y_1 < x_2 + y_1 < \ldots < x_m + y_1 < x_m + y_2 < \ldots < x_m + y_n$, we have $|X+Y| \geq m+n-1$. That equality holds when the elements of $X$ and $Y$ form arithmetic sequences with the same common difference, when $|X| = 1$ or when $|Y| = 1$ is trivial. Suppose now that $|X+Y| = m+n-1$. If $m=1$ or $n=1$, the result is trivial, so we assume that $m, n \geq 2$. For $2 \leq k \leq m+n$, let $S_k = \{x_i + y_j : i + j = k \}$. Because each $S_k$ is non-empty and there are $m+n-1$ different $S_k$'s, each $S_k$ must have exactly one element. Hence, whenever $p+q = r+s$ with $1 \leq p, r \leq m$ and $1 \leq q, s \leq n$, $x_p + y_q = x_r + y_s$. For any $2 \leq p \leq n$, setting $r=p-1$, $s = 2$, and $q=1$ yields $x_p - x_{p-1} = y_2 - y_1$. Since the differences of consecutive terms of $\{x_i\}$ are constant, $\{x_i\}$ must be an arithmetic sequence. Similarly, $\{y_i\}$ must be an arithmetic sequence. Finally, setting $p=2$, we find that $x_2 = x_1 = y_2 - y_1$, so $\{x_i\}$ and $\{y_i\}$ indeed have the same common difference. This problem is equivalent to finding the number of triples of sets $(A,B,C)$ such that $A \cup B \cup C = \{1, 2, \ldots, 100\}$; $A$, $B$, and $C$ are pairwise disjoint; and $A+B$, $B+C$, and $C+A$ are pairwise disjoint. It is clear that $A+B, B+C, C+A \subseteq \{3, 4, \ldots, 199\}$, so $(A+B) \cup (B+C) \cup (C+A) \subseteq \{3, 4, \ldots, 199\}$. Since $A+B, B+C, C+A$ are pairwise disjoint, we have $|A+B| + |B+C| + |C+A| \leq 197$. But by the lemma, \[ |A+B| + |B+C| + |C+A| \geq (|A| + |B| - 1) + (|B| + |C| - 1) + (|C| + |A| - 1) = 2(|A| + |B| + |C|) - 3 = 197,\] so we must have $|A+B| = |A| + |B| - 1$, $|B+C| = |B| + |C| - 1$, and $|C+A| = |C| + |A| - 1$. If no more than one of $A$, $B$, and $C$ have cardinality 1, then by the lemma, each of $A$, $B$, and $C$ are terms of an arithmetic sequence with the same common difference. Hence, we have the following cases: Exactly two of $A$, $B$, and $C$ have 1 element. We will solve this when $A = \{a\}, B = \{b\}$, and $a < b$, and then multiply our answer by $3!$. If $a > 1$, then $0 < b-a+1 < b, 101$, so if $b-a-1 \neq a$, then $b-a-1 \in C$, whence $1+b = (b-a+1)+a \in (C+B) \cap (C+A)$, which is a contradiction, so either $b-a+1 = a$ or $a=1$. If the former case is true, we claim that $a=2$. If not, then $a > 2$, so $0<b-a+2<b,101$. Since $b-a+2 = a+1 \neq a$, $2+b = (b-a+2)+a \in (C+B) \cap (C+A)$, which is a contradiction. Hence, $a = 2$ and $b = 2a - 1 = 3$. But then $7 = 5+a = 4 + b \in (C+A) \cap (C+B)$, which is impossible, so $a = 1$. If $b < 100$, then $100 > 101 - b > 1$ and $101 - b \neq b$, so $101 - b \in C$, whence $1+100 = b+(101-b) \in (A + C) \cap (B+C)$, which is a contradiction, so $b=100$. If $a=1$ and $b=100$, then $A+B = \{101\}$, $B+C = \{102, 103, \ldots, 199\}$. and $C+A = \{3, 4, \ldots, 100\}$, which indeed satisfy the conditions of the problem, so we have a total of 6 triples in this case. The elements of $A$, $B$, and $C$ form arithmetic sequences with common difference at least 3, and at most one of $A,B,C$ has exactly one element: Let $d$ be the common difference of $A$, $B$, and $C$. Since the elements of $A \cup B \cup C$ contain at most 3 distinct residue classes mod $d$, $d \leq 3$, so $d=3$. Hence, the elements of $A$, $B$, and $C$ must form all of the residue classes mod 3. The only way for this to happen is for $A$, $B$, and $C$ to equal $\{1, 4, 7, \ldots, 100\}, \{2, 5, \ldots, 98\}. \{3, 6, 9, \ldots, 99\}$ in some order. That $A+B$, $B+C$, and $C+A$ are disjoint follows from the fact that the elements in $A+B$, $B+C$, and $C+A$ must be 0 mod 3, 1 mod 3, and 2 mod 3 in some order, so when $d=3$ we have $3! = 6$ triples $(A,B,C)$. The elements of $A$, $B$, and $C$ form arithmetic sequences with common difference 2, and at most one of $A,B,C$ has exactly one element: We claim that there are no solutions. If there is a solution, then the parities of the elements of at least one of $A,B,C$, say, $A,$ must be distinct from the parities of the other two; hence, it must contain all integers between 1 and 100 inclusive of that parity. Let $b$ be the smallest element of $B$, let $c$ be the smallest element of $C$, and suppose without loss of generality that $b > c$. Because $2 \leq b-c \leq 98$, we can find elements $a_1, a_2$ in $A$ such that $a_1 - a_2 = b - c$, so $a_1 + c = a_2 + b$, so $A+B$ and $A+C$ are not disjoint, which is a contradiction. The elements of $A$, $B$, and $C$ form arithmetic sequences with common difference 1, and at most one of $A,B,C$ has exactly one element: $A$, $B$, and $C$ must, in some order, be $U = \{1, 2, \ldots, p\}$, $V = \{p+1, p+2, \ldots, q\}$, and $W = \{q+1, q+2, \ldots, 100\}$, where $1 \leq p < q \leq 99$. If $p \geq 2$, then $2+q = 1+(q+1) \in (U+V) \cap (U+W)$, which is a contradiction, so we must have $p=1$. If $q \leq 98$, then $1+(q+2)=2+(q+1) \in (U+W) \cap (V+W)$, which is a contradiction, so $q=99$. But then $U$ and $W$ both have exactly one element, which is a contradiction. Combining these cases, we arrive at a final answer of $\boxed{12}$.

I think these solutions are a bit complicated for C1. Can anybody provide the official solutions ?

We'll prove by induction that there are $2\cdot 6=12$ ways regardless of the number of cards $n$. Note that this is true for $n=4$; group $1,4$ in the first and $2,3$ in the second, then permute. Notice that all solutions are either the mod $3$ one or the extreme case of $1$ alone, $n$ alone, and all the rest together. Now for $n+1$ cards, if we remove $1$ the remaining $n$ must be a valid arrangement, unless the only case where $n+1$ is alone. In this case note that by looking at the numbers $n+1,1$ we get $n,2$ in the same group, by looking at $n+1,2$ we get $n,3$ in the same group. Continue in this fashion, the numbers $2$ through $n$ must be in the same group, and hence $1$ must fill the last. It is easy to verify that this works, since the pairwise sums split into $\le n+1, n+2, \ge n+3$. Now assume the only solutions for $n$ cards are the mod 3 and the extreme case. Check that the extreme case fails when we try to add in $n+1$ and that we must continue the mod 3 fashion. So there is always $2\cdot 6$ by induction.

I got some motivation for my solution from the generating function idea: bambaman wrote: Inspired by some generating-function solutions, can the following observation be completed into a solution? : We are looking for non-zero polynomials $ f_{1,2,3}$ with coefficients either 0 or 1, such that: (i) $ f_{1}(x)+f_{2}(x)+f_{3}(x)=\sum_{i=1}^{100} x^i$, and (ii) The exponents in $ f_{1}f_{2}$, $ f_{1}f_{3}$, $ f_{2}f_{3}$ are distinct. I tried to found some nice mathematical reformulation of the 2nd condition and couldn't find any... [and maybe generating functions aren't supposed to solve everything...] Namely, the backwards induction step I mentioned came from this.

Denote $A,B,C$ as the boxes. We consider the general problem for $n$. For now, we temporarily ignore the distinction of the boxes, just say all boxes have the same colour. More stronger, we can prove that the only possible partitions are $A= \{ 1 \}, B= \{ 2,3, \cdots , n-1 \}, C= \{ n \}$ or $A= \left \{ x | x \le n, x \equiv 0 \pmod{3} \right \}, B= \left \{ x | x \le n, x \equiv 1 \pmod{3} \right \}$ and $C= \left \{ x | x \le n, x \equiv 2 \pmod{3} \right \}$. The permutations of this two solutions will give $2 \cdot 3!=12$, which is the answer of the question.

This solution has a similar approach with India TST 2003.

There are $2 \cdot 3! = 12$ ways, which amount to: Partitioning the cards modulo $3$, or Placing $1$ alone in a box, $100$ alone in a second box, and all remaining cards in the third box. These are easily checked to work so we prove they are the only ones. Let $A$, $B$, $C$ be the sets of cards in the three boxes. Then $A+B$, $B+C$, $C+A$ should be disjoint, and contained in $\{3, 4, \dots, 199\}$. On the other hand, we have the following famous fact. Claim: Let $X$ and $Y$ be finite nonempty sets of real numbers. We have $|X+Y| \ge |X|+|Y|-1$, with equality if and only if $X$ and $Y$ are arithmetic progressions with the same common difference, or one of $X$ and $Y$ is a singleton set. Putting these two together gives the estimates \[ 197 \ge |A+B| + |B+C| + |C+A| \ge 2\left( |A|+|B|+|C| \right)-3 = 197. \]So all the inequalities must be sharp. Consequently we conclude that: Claim: Either the sets $A$, $B$, $C$ are disjoint arithmetic progressions with the same common difference $d = \min_{x \neq y \text{ in same set}} |x-y|$, or two of the sets are two singleton. Moreover, $\{3, 4, \dots, 199\} = (A+B) \sqcup (B+C) \sqcup (C+A)$. From here it is not hard to deduce the layouts above are the only ones, but there are some details. First, we make the preliminary observation that $3=1+2$, $4=1+3$, $198=98+100$, $199=99+100$ and these numbers can't be decomposed in other ways; thus from the remark about the disjoint union: Claim: [Convenient corollary] The pairs $(1,2)$, $(1,3)$, $(98,100)$, $(99,100)$ are all in different sets. We now consider the four cases. If two of the boxes are singletons, it follows from the corollary that we should have $A = \{1\}$, $B = \{100\}$ and $C = \{2, \dots, 99\}$, up to permutation. Otherwise $A$, $B$, $C$ are disjoint arithmetic progressions with the same common difference $d$. As two of $\{1,2,3,4\}$ are in the same box (by pigeonhole), we must have $d \le 3$. If $d=3$, then no two elements of different residues modulo $3$ can be in the same box, so we must be in the first construction claimed earlier. If $d=2$, then the convenient corollary tells us we may assume WLOG that $1 \in A$ and $2 \in B$, hence $3 \in C$ (since $3 \notin A$ by convenient corollary, and $3 \notin B$ because common difference $2$). Thus we must have $A = \{1\}$, $B = \{2, 4, \dots, 100\}$ and $C = \{3, 5, \dots 99\}$ which does not work since $1+4 = 2+3$. Therefore there are no solutions in this case. If $d=1$, then by convenient corollary the numbers $1$ and $2$ are in different sets, as are $99$ and $100$. So we must have $A = \{1\}$, $B = \{2, \dots, 99\}$, $C = \{100\}$ which we have already seen is valid. Remark: A more direct solution is to replace $100$ by $n \ge 3$ and then proceed by induction on $n$. Indeed, any working configuration for $\{1, \dots, n\}$ immediately gives a working configuration for $n-1$.

We claim that the only ways this can be done are by either splitting the numbers $\pmod{3}$, or placing $1$ and $100$ each in their own singleton boxes, with everything else in the other box. This gives a final answer of $\boxed{12}$. Let $A$, $B$, $C$ be the sets of numbers of the three boxes. The problem condition is saying that $A,B,C$ partition $[100]$ and that $A+B$, $B+C$, and $C+A$ are all disjoint. However, \[A+B,B+C,C+A\subseteq [3,199],\]and furthermore, \[|A+B|+|B+C|+|C+A|\ge(|A|+|B|-1)+(|B|+|C|-1)+(|C|+|A|-1)=197.\]Thus, we have that $A+B$, $B+C$, and $C+A$ partition exactly $[3,199]$, so as a corollary, we must have \begin{align*} |A+B|&=|A|+|B|-1 \\ |B+C|&=|B|+|C|-1 \\ |C+A|&=|C|+|A|-1. \\ \end{align*}We now have a key lemma that all but destroys the difficulty of the problem. Lemma: Given sets of positive integers $A$ and $B$, we have $|A+B|=|A|+|B|-1$ if and only if either of the sets is a singleton, or $A$ and $B$ are arithmetic progressions of the same common difference. Proof: The result is well known, so we simply sketch a proof. The if direction is easy to check, so start by assuming that $|A+B|=|A|+|B|-1$, and we'll show that $\{A,B\}$ is of the desired form. Order $A=\{a_1<\ldots<a_m\}$ and $B=\{b_1<\ldots<b_n\}$. Suppose that $m,n\ge 2$. Note that any path which goes only to the left and down in the array \[\begin{bmatrix}a_1+b_1 & a_1+b_2 &\cdots &a_1+b_n\\a_2+b_1 & a_2+b_2 &\cdots &a_2+b_n \\ \vdots & \vdots & \ddots & \vdots \\ a_m+b_1 & a_m+b_2 &\cdots &a_m+b_n\end{bmatrix}\]from the top left to the bottom right forms a sequence of $m+n-1$ numbers in $A+B$, so by varying the paths, the upper right to lower left diagonals in this array are constant. Thus, $a_1+b_i=a_2+b_{i-1}$ for all $i$, so $B$ is an arithmetic sequence with difference $a_2-a_1$, and similarly for $A$, so the result follows. Thus, we have two cases. Either two of $A,B,C$ are singletons, or they are all arithmetic progressions of the same common difference. Say we have $A=\{a\}$ and $B=\{b\}$. If $a+b\ne 101$, then $(101-a)+a\in A+C$ and $(101-b)+b\in A+B$, which is a contradiction, so $a+b=101$. If $\{a,b\}\ne\{1,100\}$, then $(100-a)+a\in A+C$ and $(100-b)+b\in A+B$, so we must have $\{a,b\}=\{1,100\}$, which is one of the claimed solutions at the start. Now, we have $A$, $B$, and $C$ are all arithmetic progressions of common difference $d$. We need to cover at least $\min\{d,100\}$ residues $\pmod{d}$, so $d\le 3$. If $d=1$, then $A=[1,a]$, $B=[a+1,b]$, and $C=[b+1,100]$. If $a\ge 2$, then $1+(b+1)\in A+C$ and $2+b\in A+B$, so we have $a=1$. We now see that \begin{align*} A+B &= [3,b+1]\\ B+C &= [b+2,101]\\ C+A &= [b+3,100],\\ \end{align*}so $b=99$, which is the same claimed solution at the start. If $d=2$, then by the residue argument, one of $A,B,C$ is either all the odds, or all the evens. If $A$ is all the odds, then $B$ and $C$ are of the form $[2,2n]\cap E$ and $[2n+2,100]\cap E$ where $E$ is the set of even numbers. We get a contradiction as $2+99\in B+A$ and $1+100\in A+C$. Now, if $A$ is all the evens, then $B$ and $C$ are of the form $[1,2n-1]\cap O$ and $[2n+1,99]\cap O$ where $O$ is the set of odd numbers. We again get a contradiction as $1+100\in B+A$ and $99+2\in A+C$. So there is no solution with $d=2$. Finally if $d=3$, we see that $A,B,C$ are all distinct $\pmod{3}$, so we have the $\pmod{3}$ splitting solution claimed at the start.

Denote the boxes by $A$, $B$ and $C$. The problem statement means that there doesn't exist distinct $a,b,c,d$ such that $a,c\in A$, $b\in B$, $d\in C$, and $a+b=c+d$. So we use the shorthand $(aA,bB; cA,dC)$ for contradiction cases. First, we discuss about the positions of 1, 2, 3. If they are not in distinct boxes, there are three cases: $1,2\in A$, $3\in B$; $1,3\in A$, $2\in B$; or $1\in A$, $2,3\in B$. Case 1. $1,2\in A$, $3\in B$. Then 4 can't be in $C$ because of the pair $(1A,4C;2A,3B)$. Thus 4 must be in either $A$ or $B$. If $k\notin C$, $k\ge 4$, we prove that $k+1\notin C$. Assume otherwise. If $k\in A$, then $(2A,(k+1)C; kA,3B)$ yields contradiction. If $k\in B$, then $(1A,(k+1)C; 2A,kB)$ yields contradiction. Thus, by induction, $C=\varnothing$, contradiction. Case 2. $1,3\in A$, $2\in B$. Then 4 can't be in $C$ because of the pair $(1A,4C;3A,2B)$. Thus 4 must be in either $A$ or $B$. If $k\notin C$, $k\ge 4$, we prove that $k+1\notin C$. Assume otherwise. If $k\in A$, then $(1A,(k+1)C; kA,2B)$ yields contradiction. If $k\in B$, then $(2B,(k+1)C; 3A,kB)$ yields contradiction. Thus, by induction, $C=\varnothing$, contradiction. Case 3. $1\in A$, $2,3\in B$. Suppose $k$ is the smallest number in $C$, $k\ge 4$. If $k-1\in A$, then $(1A,kC; (k-1)A,2B)$ yields contradiction, so $k-1\in B$. For $1\le i \le k-3$, We prove that if $k-i\in B$, then $i+3\in B$. This is true because if $i+3\in A$, then $((i+3)A, (k-i)B; 3B, kC)$ gives contradiction. We also prove that if $i+3\in B$, then $k-i-1\in B$. This is true because if $k-i-1\in A$, then $((k-i-1)A, (i+3)B; 2B, kC)$ gives contradiction. Thus, by induction, all $i\in B$ for $2\le i\le k-1$. Now if $k+1\le 100$, then it can't be in any of these sets. Indeed, if $(k+1)\in A$ then $((k+1)A,2B; 3B,kC)$; if $(k+1)\in B$ then $(1A,(k+1)B; 2B,kC)$; if $(k+1)\in C$ then $(1A, (k+1)C; 2B, kC)$. Thus, this leads to contradiction except the case when $1\in A$, $2,3,\dots,99\in B$, and $100\in C$. We can check that this case is a solution. Thus, now we assume that 1, 2, 3 are in boxes $A,B,C$ respectively. We claim that this ensures that $4\in A$, and then by induction we can finish. If $4\in B$, $(1A,4B;2B,3C)$ leads to contradiction. If $4\in C$, then by checking the cases we have $5\in A$, and $6$ can't belong in any of these sets. Hence, there are two classes of solutions: cards are divided according to their residue modulo 3, or $1\in A$, $100\in C$, and the rest are in $B$. This gives us $2\times 6=12$ ways.

Let $R, B, W$ be the three sets, and we want to partition 1 through $n$ such that $R+B, R+W, W+B$ are disjoint. I claim that $(1), (n), (2, ..., n-1)$ and the mod 3 partition are the only one that work. To prove this, we will use induction. The base case is trivial. For the inductive step, suppose the claim holds for $n-1$. Then, we do cases for $n$: 1) 1 through $n-1$ are in the mod 3 partition. Suppose $n$ is not in its mod 3 group; then, by doing cases on what $n\pmod{3}$ is and which group it's in, we'll find a contradiction by finding a common element of two of the sumsets (for instance, if $n\equiv 0\pmod{3}$ and $n$ is in the $1\pmod{3}$ group, then $n-1+3=n+2$, contradiction, and the other cases are similar). 2) 1 through $n-1$ is in $R=(1), W=(n-1), B=(2, ..., n-2)$. If $n\in R$, then $n+2=n-1+3$, contradiction. If $n\in W$, then $1+n=n-1+2$, contradiction. If $n\in B$, then $1+n=n-1+2$, contradiction. Thus this case can't happened. 3) 1 through $n-1$ is not in a valid partition. Then, $n$ is by itself, so let $n\in R$. Let $1\in W$, and suppose $2\in W$. Then, note $n-1$ in $W$ or else $n+1=2+n-1$, contradiction. Now, note if $k\in W$, then $n+k\in R+W$, so $k+1$ is not in $B$, meaning $k+1\in W$. But this would mean nothing is in $B$, contradiction; hence, $2\in B$. This means that $n-1\in B$ or else $1+n=2+n-1$, contradiction; and now note that if $k\in B$, then $n+k\in R+B$, so $k+1\in B$. Therefore, $R=(n), W=(1), B=(2, ..., n-1)$. Hence, we have proven the claim, so the answer is 12.

We solve the problem for all $n \ge 3$. We claim that the answer for $n = 3$ is $6$, with $S_1 = \{1\}, S_2 = \{2\}, S_3 = \{3\}$, and permutations being the construction, and for $n > 3$, the answer is $12$, with $S_1, S_2, S_3$ being the three residue classses modulo $3$, and $S_1 = \{1\}, S_2 = \{2, ..., n-1\}, S_3 = \{n\}$, and permutations, being the constructions. These clearly work. Observation: Note that if none of the three sets is $\{n\}$, we can remove $n$ from its set to reduce to a construction for $n-1$. Lemma: If $S_3 = \{n\}$, and $n-1$ belongs to $S_2$, then $S_1 = \{1\}, S_2 = \{2, ..., n-1\}$. Proof: Suppose $k > 1$ is the largest element in $S_1$. Then $(k-1) + n = k + (n-1)$ gives a contradiction. By the above observation and lemma, it is easy to manually check that our main claim holds till $n = 6$. We prove our main claim inductively. Base case is $n = 6$. Supposing our claim holds till $n = k, k \ge 6$, we prove it for $n = k+1$. If $S_1 = \{1\}, S_2 = \{2, ..., k-1\}, S_3 = \{k\}$, then adding $k+1$ to: $S_1$ gives $(k+1) + 2 = k + 3$, $S_2$ gives $(k+1) + 1 = k + 2$, $S_3$ gives $(k+1) + 1 = k + 2$. So this can't be extended to a construction for $k+1$. If $S_1$, $S_2$, $S_3$ are the three distinct residue classes modulo $3$, and $k+1$ belongs to, WLOG, $S_1$, but we added it, WLOG, to $S_2$, the $(k+1) + a = (k-2) + (a+3)$, where $a$ is the smallest member of $S_3$, gives a contradiction.

Got solution by intuition, then proved it by mathematical induction. Problem is very long because of cases. Claim: There are $12$ ways, and the trick is that we are sorting cards by their remainder when divided by $3$ or to put $1$ and $n$ in different boxes and all the others in last box. Place cards by their remainder when divided by 3 into boxes. For remainders $1, 2, 0$ place them in boxes $B_1$, $B_2$, $B_3$. For $n = 3$ and $n = 4$ this us easy to see. Now let's suppose it works for $n \geq 4$ and we want to prove that it also works for $n + 1$. Then we divide this into two cases. $1$) $n + 1$ is alone in the box $2$) there are other cards with $n + 1$ in the box. In the second case if we remove $n + 1$ then trick still works since there are no empty boxes. By induction hypothesis we get that there are two possible strategies for the cards from $1$ to $n$. If $1$ and $n$ are alone then if we place $n + 1$ with $1$ then we can choose pairs $(n, 3)$ and $(n + 1, 2)$ so this doesn't work. If $n + 1$ and $n$ are in the same box then we can choose pairs $(n + 1, 1)$, $(n, 2)$ and again it doesn't work. If $n + 1$ is with the other cards, we can choose $(n + 1, 1)$ and $(n, 2)$ and again trick doesn't work. So other strategy must work (place cards by their remainder when divided by $3$). Let's prove it. If $n + 1$ and $n$ are in the same box then by choosing pairs $(n + 1, n - 2)$, $(n, n - 1)$ trick doesn't work. Similarly if $n + 1$ is with $n - 1$ then by choosing pairs $(n + 1, n - 2)$, $(n - 1, n)$ then trick doesn't work. From this $n + 1$ and $n - 2$ are in same box so other strategy works, so there are $3!$ possible ways of sorting cards in three distinct boxes. In the first case we should prove that first strategy works. Let's consider elements $(n + 1, k)$ and $(n, k + 1)$ with condition $n > k \geq 1$. First pair has different boxes because $n + 1$ is alone. Now we see that $n$ and $k + 1$ must be in same box because they can't share it with $n + 1$. Last box must contain $1$ because it mustn't be empty. From this we obtain that $1$ and $n + 1$ are alone and the rest of cards are jn the last box, let's show that this work because this will complete induction. If $1$ and $n$ are alone using pair $(1, \psi)$ where $2n - 1 > \psi >2$ we get the sums from $3$ to $n$. With the cards $1$ and $n$ we only get sum $n + 1$. With the cards from $2$ and $n - 1$ and the card $n$ we get sums from $n + 2$ to $2n - 1$. Thus the first strategy works. For the second strategy, it doesn't works because it depends on two boxes where the numbers were chosen. Then if we repeat the sum, we repeat the boxes too. Hence we arw done with this case which has also $3!$ ways of placing. Thus final answer is $3! + 3! = 12$. Comment: We just watched case $n = 100$

Let $X,Y,Z$ be the sets of cards in the 3 boxes, respectively. The condition implies $X+Y$, $Y+Z$, $Z+X$ are disjoint, since $x+y$ for $x\in X$ and $y\in Y$ must be in exactly one of the 3 aforementioned sumsets. Let $x=|X|$, $y=|Y|$, $z=|Z|$. It is well-known that $|A+B|\ge |A|+|B|-1$ for any sets $A,B$, with equality when (1) $A$ or $B$ is a singleton; the other can then be any set, or (2) the elements of $A$ and $B$ both form arithmetic sequences with the same common difference. So \[ |X+Y| \ge x+y-1, \ |Y+Z|\ge y+z-1, \ |Z+X| \ge z+x-1. \]Summing gives \[ |X+Y|+|Y+Z|+|Z+X| \ge 2x+2y+2z-3 = 197. \]Since $X+Y\subseteq \{3,4,\ldots,199\}$ and similarly for the other two, and since the 3 sumsets are disjoint, \[ |X+Y|+|Y+Z|+|Z+X| \le 197. \]Therefore, equality is achieved in all 3 bounds we applied. So $X+Y,Y+Z,Z+X$ partition $[3,199]$. Case 1: None of $X,Y,Z$ is a singleton. Then $X=\{a,a+d,\ldots,a+(x-1)d\}$, $Y=\{b,b+d,\ldots,b+(y-1)d\}$, $Z=\{c,c+d,\ldots,c+(z-1)d\}$ for some $a,b,c$ and common difference $d$. Note that $(x-1)d \le a+(x-1)d \le 100$, so $x\le 100/d+1$, and similarly for $y,z$. Summing gives $x+y+z \le 300/d+3$, i.e. $97 \le 300/d$, so $d\le 3$. Subcase 1.1: $d=1$. So $X=[1,m]$, $Y=[m+1,n]$, $Z=[n+1,100]$ for some $m,n$. If $m\ge 2$, then we can never get 3 as a sum, since the minimum is $m+2$; so $m=1$. Similarly, unless $n=99$ we cannot get 199 as a sum, since the maximum is $100+n$. Therefore, $X=\{1\}$, $Y=[2,99]$, $Z=\{100\}$, or any permutation. There are $3!$ ways to order. Subcase 1.2: $d=2$. By Pigeonhole, one of $X,Y,Z$ is all the odds or all the evens. Suppose $X$ is all the odds. Then $Y,Z$ split the evens down the middle at some point. Now $X+Y$ contains $99+2$ and $X+Z$ contains $1+100$, contradiction. We can get a similar contradiction if $X$ is all the evens. Subcase 1.3: $d=3$. Then $X,Y,Z$ are all distinct mod 3, they each take one mod 3 class. There are $3!$ ways here to order. Case 2: Exactly one of $X,Y,Z$ is a singleton. Then the other two must be arithmetic sequences with the same common difference, and the singleton is technically to. Now refer to Case 1. Case 3: Exactly two of $X,Y,Z$ are singletons. Suppose $x=y=1$. Suppose $X=\{m\}, Y=\{n\}$ for some distinct $m,n$; WLOG $m<n$. Then $Z=[1,100]\setminus \{m,n\}$. Then $X+Y=\{m+n\}$, $X+Z=[m+1,m+100]\setminus \{2m,m+n\}$, and $Y+Z=[n+1,n+100]\setminus \{m+n,2n\}$. But since 199 must be one of these, we must have $n=99$ or $m=99$, but since $m<n$, $n=99$. Similarly 3 must be in one, so $m=1$. Now we get the same as Subcase 1.1. In total, there are $3!+3!=\boxed{12}$ ways; the mod 3 partition or 1,100 as singletons and the rest together.

We claim that there are $12$ ways to do this no matter how many cards there are. We induct on $n$, where there are $n$ cards. Let the boxes be labeled $B_1,B_2,B_3$. Then, place each card $i$ in boxes $B_{i\pmod{3}}$. It is easy to see that there are 12 cases for $n=4$: just permute $\{\{1,4\},\{2\},\{3\}\}$ or $\{\{4\}, \{1\}, \{2,3\}\}$. Now, assume that it works for $n\geq 4$. We want to show that it works for $n+1$. If we remove the card labeled $1$, then the remaining $n$ cards must work. However, this doesn't work if $n+1$ is alone, so we must consider this case separately. In the case that $n+1$ is alone, then by looking that $n+1, 1$ we have that $n,2$ must be in the same group. Similarly, by looking at $n+1,2$ we get that $n,3$ must be in the same group. Then, every number from $2$ to $n$ have to be in the same group, so $1$ is the sole member of the last group. It is easy to see that this works. Thus, by induction the number of ways to do this is always $3!\cdot2=12$.

Let $a_n$ denote the answer to the problem when $100$ is replaced by some $n.$ The answer is $a_n=\boxed{12}$ for all $n\ge 4,$ which is achieved by permutations of $S_0,S_1,S_2,$ where $S_i$ is the set of cards congruent to $i\pmod{3}.$ $\{1\},\{2,3,\dots,99\},\{100\}.$ To show this, we will induct on $n.$ $\textbf{Base Case: }$ Just list out the possibilities to find that only permutations of $\{1,4\},\{2\},\{3\}$ and $\{1,4\},\{2\},\{3\}.$ $\textbf{Inductive Step: }$ Assume the claim is true for all $4\le n\le k,$ and consider a valid arrangement with $k+1$ cards. If $k+1$ is not the only card in its box, then we can remove $k+1$ to obtain a valid $k$-card arrangement. Now we can easily check that the original arrangement must have been the first described in the claim. If $k+1$ is the only card in the (WLOG) red box, then all numbers in the interval $[k+2,2k+1]$ are possible sums of a card in the red box and a card in sum other box. Suppose WLOG that card $k$ is in the blue box; then, for any $i$ in the white box, we have $k+i\not\in[k+2,2k+1].$ But this implies the only card in the white box is $1,$ so the original arrangement must have been $\{1\},\{2,3,\dots,k\},\{k+1\}.$

What a boring magic trick We claim the answer is $12$. Mainly, the cards partitioned into the boxes mod 3 or one box with $1$, one box with $100$, and all other cards in the final box. Let us prove that the only valid partitions are the ones described using induction. Basis: Take $3$ cards. Trivially, the only valid partitions are the ones described. Inductive Step: Take $n$ cards who's only valid arrangements are the ones described and imagine adding the card $n+1$ to one of the three boxes. Clearly, if the $n$ cards are not in a valid arrangement, adding one card will not change that. Now, notice there is exactly one box to put the $n+1$ card in to keep the arrangement valid. Completing the induction. QED Note: I omitted casework for the sake of brevity.

The answer is $12$, which comes from: 1. Partitioning the cards $\pmod{3}$ (6 ways), 2. Placing $1$ in one box, $100$ in another box, and the rest in the last box. These clearly work. Let the boxes be represented by $R,W,B$. Observe that the magician's trick works if and only if $R+W,W+B,B+R$ are disjoint. For now ignore the "nonempty" condition, and replace $100$ with $n \geq 3$. Then the solutions are partitioning the cards $\pmod{3}$ or putting $1$ in one box, $n$ in another box, and the rest in the last box, as well as any arrangement in which at least one box is empty. Call such arrangements "magical". These clearly work, so I will now show that nothing else works by induction on $n$. The base case $n=3$ is obvious. Assume that the statement is true for some $n-1 \geq 3$; I will show that it holds for $n$ as well. First look at the $n$ case. Define $R'$ to be $R \setminus \{n\}$, and define $W',B'$ cyclically. Since $R+W,W+B,B+R$ must be disjoint, $R'+W',W'+B',B'+R'$ must be disjoint as well, hence by inductive hypothesis $R',W',B'$ must form a magical arrangement for $n-1$. Now consider the following cases on which magical arrangement this is: Case 1: The magical arrangement is the mod 3 partition. I'm too lazy to write three general cases, so here's an example for $n=5$ which generalizes: for $n-1$ (which is just $4$) one mod 3 (order doesn't matter) partition is $R'=\{2\},W'=\{3\},B'=\{1,4\}$. I will show that $5$ must go into $R$. Indeed if $5$ goes into $B$ then $5+2=4+3$ and hence the sets are not disjoint, and if $5$ goes into $W$ then $5+1=4+2$ and hence the sets are not disjoint. This generates the mod 3 partition for $n$, and only that. Case 2: The magical arrangement is the "put $1$ and $n-1$ in separate box, everything else in the remaining box". WLOG, let $R'=\{1\},W'=\{n-1\}$, and put everything else in $B'$. If $n$ goes into $R$ then $n+(n-3)=(n-1)+(n-2)$, hence $R+B$ and $R+W$ are not disjoint for $n>4$. If $n$ goes into $W$ then $n+1=(n-1)+2$, hence $W+R$ and $W+B$ are not disjoint for $n>3$. Finally if $n$ goes into $B$ then $1+n=2+(n-1)$, hence $B+R$ and $B+W$ are not disjoint for $n>3$. Therefore this case generates no working magical arrangements for $n$ cards, unless $n=4$. But if $n=4$, then $n-1=3$ and this case is the same as case 1. Hence this generates no additional solutions. Case 3: The magical arrangement has one empty set. WLOG let $R'$ be empty. Then if $n$ is added to $B$ or $W$, there is still an empty set, which works. Thus suppose $n$ is added to $R$, so then $R=\{n\}$. I claim that for all $2 \leq k \leq n-2$, $k$ and $n-1$ must be in the same set. Indeed, assume FTSOC that $k$ and $n-1$ are in different sets: WLOG let $k \in B$ and $n-1 \in W$. Then since $k-1$ is in $B$ or $W$ and $n+(k-1)=(n-1)+k$, either $R+B$ and $B+W$ are not disjoint or $R+B$ and $B+W$ are not disjoint: contradiction. Hence $k$ and $n-1$ must be together for all such $k$. If $1$ is also in the same set as $n-1$, then one of the sets is empty, which works. Otherwise, the arrangement is the "put $1$ and $n$ in separate boxes, everything else in the remaining box" arrangement, which is magical. This generates no additional solutions. Case 4: The magical arrangement has two empty sets. Then after adding $n$ to any set, there is still at least one empty set, which works (no additional solutions are generated). Combining these cases implies that no arrangements which aren't magical work. Then, removing the magical arrangements which contain empty sets implies the desired result. $\blacksquare$

We claim that if there are n cards from 1 to n, then there only 12 ways to put the cards into the boxes. They are the permutations of $[(1),(n),(2,\ldots n-1)]$ and $[(\equiv 1 \pmod{3}),(\equiv 2 \pmod{3}),(\equiv 3 \pmod{3}]$. In the base case $n=4$, the only pair of cards that can mess us up are 1+4=2+3. Additionally, the 4 cards must be distributed with 2 in one box and 1 in the others. Thus, we must either have (1,4) together or (2,3) together. These yield [2,(1,4),3] and [(1),(2,3),4]. For the inductive step, take some configuration of cards $1,\ldots ,n+1$ placed into the 3 boxes. By the inductive hypothesis if you remove the 'n+1' you are left with one of \begin{itemize} \item $[(1),(n),(2,\ldots n)]$ \item $[(\equiv 1 \pmod{3}),(\equiv 2 \pmod{3}),(\equiv 3 \pmod{3}]$ \item one empty box \end{itemize} Case 1: $[(1),(n),(2,\ldots n)]$ Placing an n+1 into the left or middle box yields $2+(n+1) = 3+n$. Placing in the right yields $(n+1)+1=n+2$. So this case is a dead end. Case 2: $[(\equiv 1 \pmod{3}),(\equiv 2 \pmod{3}),(\equiv 3 \pmod{3}]$ Let r = (n+1) mod 3. Note that n and n-1 are both not in box r. If n+1 is placed in box $x\neq r$, (n+1)+(n-2) = n+(n-1). Thus, n+1 must be placed in box r, creating a set $[(\equiv 1 \pmod{3}),(\equiv 2 \pmod{3}),(\equiv 3 \pmod{3}]$. Case 3: one empty box. This is the case where $n+1$ is alone in a box. Let $|A+B|$ be the set of $[\alpha +\beta | \alpha \in A, \alpha \in B]$. Then, WLOG C is the set with n+1. Then, $|A+B|+|B+C|+|A+C| = |A+B| + x + (n-x) \geq |A|+|B|-1+n = 2n-1$, which has an equality case when A and B are both arithmetic sequences or if one of A,B is a single element(Example 1.1 in EqualityDCW). We must be at the equality case because the only possible sums are from (1+2) to (n+(n-1)), with 2n-1 total values. Case 3a: A and B are both arithmetic sequences. They must be the odds and the evens, which clearly fails (n+1)+(n-2)=(n)+(n-1). Case 3b: WLOG A is a single element. Let A consist of $r$. If $r>1$, then (n+1)+1=r+(n+2-r). Thus, r=1 and we are left with $[(1),(n),(2,\ldots n-1)]$. Thus, we must have one of the permutations of $[(1),(n),(2,\ldots n-1)]$ or $[(\equiv 1 \pmod{3}),(\equiv 2 \pmod{3}),(\equiv 3 \pmod{3}]$, so there are 12 possible ways to place the cards.

We call an arrangement valid if it consists of the cards placed into the three boxes such that no box is empty. We claim that the answer is $2\cdot 3!=12$, and the only valid arrangements that the trick works on are the $\mathrm{mod}~3$ partition and $\{1\}\cup \{2,3,\dots,99\}\cup \{100\}$. We prove this for $n$ cards by induction. The base case $n=3$ is trivial, since we must have $\{1\}\cup \{2\}\cup \{3\}$. Suppose the claim is true for $n-1$. Then either the cards $1,2,\dots,n-1$ are sorted into the boxes in one of the ways mentioned above, or they are not in a valid arrangement, since the trick must still work for any pair of cards in $1,2,\dots,n-1$. Case 1: The cards $1,2,\dots,n-1$ are arranged with $2,3,\dots,n-2$ in one box and each of $1$ and $n-1$ in their own boxes. Then we cannot place the $n$-th card anywhere, since if $n$ is in the box with $1$, we have $n+(n-3)=(n-1)+(n-2)$ as a counterexample, if $n$ is in the box with $n-1$, then $n+1=(n-1)+2$ is a counterexample, and if $n$ is in the box with the cards $2,3,\dots,n-2$, then $n+1=(n-1)+2$ is again a counterexample. Therefore this case does not yield an arrangement that the magic trick works on. Case 2: The cards $1,2,\dots,n-1$ are arranged according to residue classes $\mathrm{mod}~3$. Then suppose for the sake of contradiction that $n$ is not also in the box for its residue class $\mathrm{mod}~3$. If $n\equiv 1\pmod{3}$, then $n+1\equiv (n-1)+2$ is a counterexample, since $n$ and $1$ are not in the same box, and $1$ is not in the same box as $n-1$ or $2$. Similarly, if $n\equiv 2\pmod{3}$, then $n+2=3+(n-1)$ is a counterexample, and if $n\equiv 0\pmod{3}$, then $n+3=4+(n-1)$ is a counterexample. We have reached a contradiction, thus $n$ must be in the box corresponding to its residue class $\mathrm{mod}~3$, resulting in a $\mathrm{mod}~3$ partition. Case 3: The cards $1,2,\dots,n-1$ are not in a valid arrangement. Then one box contains only the $n$-th card (else the whole arrangement wouldn't be valid either). Take any card numbered $c$ that is not in the same box as the card numbered $n-1$, which must exist, or else there would be an empty box. Then $c$ is not in the same box as $n$, either, so $c+(n-1)=n+(c-1)$ is a counterexample if a card numbered $c-1$ exists. The only way $c-1$ doesn't exist is if $c=1$, therefore the only card that is not in the same box as $n-1$ or $n$ must be $1$. This results in the $\{1\}\cup \{2,3,\dots,99\}\cup \{100\}$ partition. Hence the only two arrangements that work are the $\mathrm{mod}~3$ partition and the $\{1\}\cup \{2,3,\dots,99\}\cup \{100\}$ partition. Since the colors of the boxes do not affect the magic trick, there are $3!$ ways to implement each arrangement, so there are $2\cdot 3!=12$ ways total.

The answer is $6 \cdot 2 = 12$ ways. Disregarding the permutations of the boxes, there are two solutions: sorting the cards according to mod 3, or placing $1$ in one box, $100$ in another box, and the remaining numbers in another. It is easy to check that these work. To prove that no other placements work, we use induction. Notice that if, upon removal of the card $n+1$, we are left with $n$ cards whose placement does not satisfy either of those previously mentioned conditions, we are done by the inductive hypothesis. Next, if $n+1$ is placed in a different box than it is mod 3, suppose the audience member picked that number $n+1$ and a number $k \leq 3$ from another box. Then, there exists two numbers in two distinct boxes that do not contain the box with $n+1$ in it which have numbers that sum to this number, so the magician is unable to determine for sure. If $n+1$ is placed in the box with $1$, then the pairs $\{n+1, 2\}$ and $\{n, 3\}$ conflict. If it is placed in a box with $n$, then the pairs $\{n+1, 1\}$ and $\{n, 2\}$ conflict. This completes the induction.

First, we can have the trick work by either sorting the cards $\mod(3)$ or placing card $1$ in a box, card $100$ in a box, and the others in the third box. Next, we need to prove these are the only ways to place the cards. If we took card $x$ which is not in it's deck $\mod(3)$ with card $y$ from another box, we can get another card $x-3$ (which is in a different box) with card $y+3$. Therefore, if we have any cards in a different modulo deck, the magician has a chance of messing up. It is obvious if we have two decks of one card and a third deck of all other cards, we will fail if they are not $1$ and $100$. Therefore, we have $12$ total arragements of cards

hi everybody, could you tell me if either my solution works or has any mistake? Some Notation let $A$, $B$ and $C$ be the disjointed subsets of $L=\left\{ 1,2,...,100\right\}$. Then $A=\left\{ \alpha_1,...,\alpha_s\right\}$, $B=\left\{ \beta_1,...,\beta_t\right\}$, $C=\left\{ \gamma_1,...,\gamma_u\right\}$, s.t. s+t+u=100. What does the problem ask? Rephrasing the problem, we want to find the triple $\left( A, B, C\right)$ of subsets of $L$ s.t. the sum of one each elements of the two subsets doesn't appear in the sum of other two. More specifically, if a+b is the sum between an element of $A$ and one of $B$, then doesn't exist a c in $C$ such that exists a+b-c in either $A$ or $B$. SOLUTION we can easily notice 2 "sets" of triples: the first formed by the 6 recombinations of the subsets constructed as $A=\left\{ 1\right\}$, $B=\left\{ 100\right\}$ and $C=\left\{2,...,99\right\}$; the second formed by the 6 reordinations of the subsets built as the classes of modulo in 3, $A=\left\{ a\mid a \equiv 0 mod 3\right\}$, $B=\left\{ b\mid b \equiv 1 mod 3\right\}$ and $C=\left\{ c\mid c \equiv 2 mod 3\right\}$. In fact they work since, in the first case, defined $X+Y=\left\{x+y\mid x\in X, y\in Y\right\}$, A+B contains just 101, $max\left\{A+C\right\}\leq 100$ and $min\left\{B+C\right\}\geq102$ thant there is no intersection between the subsets. In the second case A+B, A+C and B+C produce 3 differents classes of numbers, which avoid the intersections. Let's prove that there is no other solution: We will form the subsets of $L$ by adding one number a time starting from 1 and respecting the condition. NOTE: if we divide in the 3 subsets 1,2,3 we will get the second case that we found earlier proof: initially we will have: $A=\left\{ 1\right\}$, $B=\left\{ 2\right\}$ and $C=\left\{ 3\right\}$. 4 could eventually be added just in A, in fact if 4 belongs to B or C, than 4+1(or A+(B/C) would be equal to 3+2(B+C), which goes against our condition. inductively, 5 and everyother number will end up to be in the subset containing the same class of modulo. Now suppose to have $A=\left\{1\right\}$ and $B=\left\{2\right\}$. Then suppose that you have put all the numbers from 3 to x into the subsets A and B. Suppose now you want to put x+1 in the subset C, this will be the first number. This will led to a contraddiction of our condition: once we added x+1, let's now try to add x+2. Since as (x+1)+2 forms x+3 as (x+2)+1 does, x+2 needs to be in the same subset of 1, for not considering that sum. Than x+2 is in A. Now let's consider x+4. This is gettable by (x+2)+2, which is a sum using elements in A and B, and (x+1)+3, which contains an element of C. This means that C contains also 3, but by definition x+1 is the first number added to C, than it's a contraddiction. *NOTE that as said before, if we divide 1,2,3 in 3 different subsets we will refall in the first case*. Let's finally consider 1 and 2 in the same subset $A=\left\{1,2\right\}$. We need to divide in 2 case: case 1 3 doesn't belong to A: then none of the bigger than 3 number can belong to the third subset. In fact, suppos we add x+1 to the third set. (x+1)+2=(x)+3 which contains all the 3 subsets, contraddiction. But we need that all the set have at least 1 element. case 2 3 belongs to A: it's the same case of before, but translated of 1. Than inductively none of the numbers can added to a different set from A. Impossible. CONLUCSION Given what we have done, there is no other combination from the one we found capable to satisfy the requirements of the problem, then the answer is 6+6=12 * I forgot to treat the case in which 1 and 2 are in differents sets and 3 belongs to the same set of 2. We easily refall in the first case we analyzed, let's see how: $A=\left\{1\right\}, B=\left\{2,3,...x-1\right\}$ and $C\left\{x\right\}. If we want to add x+1, we will fall in a problem: (x)+2=(x+1)+1 which contains all the 3 sets, then let's add x+1 to A (x)+3=(x+1)+2, which contains again all the 3 subsets, then x+1, with x bigger than 3, isn't addable, this implies that if exist x, it needs to be the last number, either in our case 100, which is exactly our first case.

The answer is 12. WLOG 1 is in r (3 ways). Case 1: 2 is not in red (w, 2 ways) Let k<100 be the smallest number in b. (b&w) k+2=(k+1)+1 (...&r), meaning that k+1+1 must not be a possible sum, since otherwise the magician is confused. So k+1 is in r, and since (r&w) (k+1)+2=k+3 (b&...), this means that 3 must be in b for same reason. Now, by induction, if n-1, n-2, and n-3 are in separate boxes (base case 1,2,3), we have k-1+k-2=k-3+k, so k must be in the same box as k-3. This gives $\boxed{6}$ ways. Now, if k=100, we claim that everything else is in w. (b&r) 100+1=2+99 (w&...), so 99 is in w. Also note that (b&w) 100+2=99+3 (w&...), so either 3 is in b, contradicting k, so 3 is in w. Now, for the inductive step, assume for some i that i-1 is in w (this is true for i=3). We have (w&b) (i-1)+100=i+99 (...&w). Since i<100, i is not in b (or else contradict k), so i is in w. This holds for all i=2 to 99, so we're done! The set is (r,w,b)=(1,{2,3,...,99},100) and permutations (another $\boxed{6}$ ways). Case 2: 2 is in r Let p and q be the smallest number in w and b, respectively, and WLOG p<q. Then, since (r&b) 2+q=p+(q-p+2) (w&...), q-p+2 is in w. However, since (r&b) 1+q=(q-p+2)+(x-1) (w&...), this means that x-1 is in w, which contradicts the definition of x. In conclusion, there are a total of $\boxed{12}$ ways the magician can do this, as claimed. $\blacksquare$ Remark: There were probably other ways to use induction, this problem seems very inductive reasoning since it can be thought of as recursion. I think induction on 1,2,3,4 would work, since there's nothing special on the number 100 and 100=1=4 mod 3.

1. Claim (Construction) We claim that $100$ is a "placeholder integer" - in other words, for any integer $n\ge{}5$, there are always exactly $12$ ways to arrange the boxes such that the mathematician may perform the trick. 2. First 6 arrangements - mod 3 split (Construction) In these arrangements, we simply assign one box to contain all cards 0 mod 3, another box to contain all cards 1 mod 3, and the final box to contain all cards 2 mod 3. Clearly, there are $3!$, or 6 ways to assign the boxes. To perform the trick, if the sum announced is $k$ mod 3, then the magician should choose the box assigned to $-k$ mod 3. In other words, if the sum announced is divisible by 3, then the magician should choose the box that is 0 mod 3. If the sum announced is 1 mod 3, then the magician should choose the box that is 2 mod 3, and vice versa when the sum announced is 2 mod 3. 3. Other 6 arrangements - 1, $n$, everything else (Construction) We can find more arrangements, where one box contains only 1, another box contains only $n$, and the third box contains everything else. Since $n\ge{}5$, notice that in this case, there are also $3!$ or 6 ways to assign the boxes. To perform the trick, let the sum announced be $s$. If $s$ is $n+1$, the magician knows that the "everything else" box was not drawn from. If the sum $s$ is such that $3\le{}s\le{}n$, then the magician knows that the box containing only $n$ was not drawn from. Finally, if $s\ge{}n+2$, the magician knows that the box containing only 1 was not drawn from. We will now use induction to prove that these are the only possible arrangements. 4. $n=5$ case (Induction) Simply brute forcing $n=5$, WLOG we let 1 be in the red box. Notice that 5 cannot be in the same box as 1 (prove this using brute force by considering what numbers would go in the other two boxes), so again WLOG let 5 be in the blue box, which implies that 2 cannot be with 1 (again prove through brute force). Notice that if 2 goes in the white box, then so must 3 and 4, and if 2 goes in the blue box, then 3 goes in the white box and 4 must go in the red box. Accounting for the WLOGs, we find that there are exactly 12 total ways, both of which fit into the two cases described above. 5. $n$ is alone (Induction) In this case, we let $n$ be alone in its own box. WLOG, let $n$ be in the red box. Obviously, $n$ will combine with the other numbers in the white in blue boxes to make the sums $n+1$, $n+2$, $\dots$, $2n-1$, meaning that there cannot be a number $w$ in the white box and a number $b$ in the blue box such that $n+1\le{}w+b\le{}2n-1$. WLOG, if we let $n-1$ be in the blue box, then notice by this constraint, the numbers $2$ through $n-2$ must also be in the blue box. Since there must be at least one number in the white box, the white box must contain only 1. Therefore, if $n$ is alone in its own box, the arrangement must be the case described in (3), for a total of 6 arrangements. 6. $n$ is not alone (Induction) Notice that this would mean that the original $n-1$ numbers, already in their spots, obey the fact that the magician can perform the trick. We can then take this in cases and see where $n$ could be placed. 6a. The $n-1$ numbers are split mod 3 Taking casework, we see that if $n$ is in any other box than the box in which $n$ is congruent to mod 3, then there will be repeats. Therefore, all possible arrangements for $n$ are in the case described in (2), for a total of 6 arrangements. 6b. The $n-1$ numbers are in 1, $n-1$, everything else Taking casework again, we find that if we place $n$ in the $n-1$ or the everything else boxes, then $n+1$ will be a repeated sum, a contradiction. Similarly, if we place $n$ in the 1 only box, then $n+2$ will be a repeated sum, another contradiction. We conclude that there are no possible arrangements for $n$ in this case. 7. Conclusion Combining the number of arrangements in each of the two cases, we find that there are 12 arrangements total. Letting $n=100$, as said in the problem, we conclude that the magician has 12 ways to place his cards in the boxes, finishing the problem.

We claim that the only possible placings are when we split the cards $\pmod 3$ or when $1$ and $100$ are the only card in their boxes. The former works by looking at the $\pmod 3$ of the card sum, and the latter works because the sum can be split into cases of $\le 100$, $101$, and $\ge 102$. We prove this inductively, replacing $100$ with $n$. Base case $n=3$: it is trivial because all boxes contain one card. Inductive step: Suppose we have a valid placing for $n$ cards. Consider removing the $n$th card. If such a removal violates the condition that every box contains at least one card, card $n$ must have been in a box of its own. Furthermore, if the box containing card $1$ has any other cards, then suppose $n-1$ and $i$ are in different boxes, then it is possible to get the sum $n-1+i$ in two different ways by choosing the two cards $n-1,i$ and $n, i-1$. Otherwise, the post-removal arrangement of cards must be one of the valid arrangements of $n-1$ cards (either split mod 3 or having cards $1$ and $n-1$ on their own). Suppose the former, then if card $n$ was not placed in the $n \pmod 3$ box we will get duplicate sums, so $n$ must be placed according to mod $3$. Suppose the latter, then we see that if card $n$ was not originally placed with card 1, then it is possible to form the sum $n+1$ in two different ways ($1, n$ and $2, n-1$), contradiction. But if $n$ was originally placed with card 1, then $n+2$ can be formed in two ways ($2, n$ and $3, n-1$. Note that we can assume $n \ne 4$ here because otherwise this would be equivalent to splitting the cards based on mod $3$, which we already know works). Hence, the valid arrangements are as claimed. This results in $2\cdot 3! = \boxed{12}$ valid placings of cards in the boxes.

The answer is $\boxed{12}$. This amounts to partitioning the cards modulo $3$ or placing $1$ and $100$ in their own boxes. These are easily checked to work so we will prove they are the only ones. We proceed by induction on $n$. The base case $n=3$ is vacuous as one card goes in each box. As for the inductive step, we will take a partition of $\{1,2,\dots, n\}$ and show that it reduces to a working partition of $\{1,2,\dots,n-1\}$ by either removing $1$ or $n$. If $1$ and $n$ are in their own box, this is already a desired case listed out by the induction. If $n$ is not in a box by itself, then by induction hypothesis the cards $1$ through $n-1$ are either arranged mod $3$, or as $\{1\} \cup \{2,3,\dots,n-2\} \cup \{n-1\}$. In the former mod $3$ situation, since $n + (n-3) = (n-1) + (n-2)$, so $n$ must be in the same box as $n-3$. In the latter case and for $n > 4$, since $n + 1 = 2 + (n-1)$, $n$ must be in the same box as $1$. But now $n + 2 = (n-1) + 3$ for $n > 4$, contradiction. An analoguous argument can be applied if $1$ is not in a box by itself. We have exhausted all cases and thus, we are done.

The answer is $12$, achievable by $A = \{1, 4, \ldots, 100\}$, $B = \{2, 5, \ldots, 98\}$, $C = \{3, 6, \ldots, 99\}$, $A = \{1\}, B = \{2,3,\ldots, 99\}, C = \{100\}$, and permutations. We now prove that nothing else works. 'WLOG that $1\in A$. Claim: $2\not \in A$ Proof: Suppose we had $2\in A$. Let $a$ be the smallest positive integer not in $a$. WLOG $a \in B$. Now let $a + k$ be the smallest positive integer in $C$. For any positive integer $m \le a - 1$, we have $(a + k) + m = a + (k + m)$. Since $a + k$ and $m$ are in different sets ($A$ and $C$) and $a\in B$, $k + m$ cannot be in set $A$, and since it is less than $a + k$, it must be in $B$. Now, notice that $(a + k) + 1 = (k + 2) + (a - 1)$. We have $a + k \in C, 1 \in A, k + 2 \in B, a - 1 \in A$ since $2 \le a - 1$, contradiction, $\square$ WLOG that $2\in B$. Case 1: $3\in B$. Let $b$ be the smallest positive integer in $C$. Clearly $b > 3$. For each positive integer $i < b - 1$, we have $i + b = (i + 1) + (b - 1)$ meaning that $i+1$ and $b - 1$ are in the same set. Hence $2, 3, \ldots, b-1$ are all in $B$. Claim: $b = 100$. Proof: Suppose not. Notice that $(b+1) + 1 = b + 2$ but $1, 2, b$ are in different sets, so $b+1 \in A$. Now, $(b+1) + 2 = b + 3$, but $2\in B, b+1\in A, b\in C, 3\in B$, contradiction. $\square$ Hence $1\in A, 2, 3,\ldots, 99\in B, $ and $100\in C$, corresponding to our second solution described above. Case 2: $3\in A$. Then let $k$ be the smallest positive integer in $C$. We have $k + 1 = (k-1) + 2$, so $k-1\in B$. Then $k + 2 = (k-1) + 3$, which is absurd since $2\in B, k\in C$ and $3\in A, k-1\in B$. Case 3: $3\in C$. Claim: For each positive integer $3 < x \le 100$, we have $x$ is on the same set as the unique integer $r_x \in \{1, 2, 3\}$ such that $3\mid x - r_x $. Proof: Suppose not. Let $i> 3$ be the smallest positive integer such that $i$ and $r_i$ are in different sets. Notice that $i-1, i-2, i-3$ are in pairwise different sets, but $i + (i-3) = (i-1) + (i-2)$, so if $i$ and $i-3$ were in different sets, then we would have a contradiction. Hence $i$ and $i - 3$ are in the same sets, which is also the set $r_{i-3} = r_i$ is in, absurd. $\square$ Hence all $a\equiv 1\pmod 3$ are in $A$, all $b\equiv 2\pmod 3$ are in $B$, and all $c\equiv 0\pmod 3$ are in $C$, giving the first solution described above.

hey guys, i just wanted to put something on my own on this- would using youngs' tableaaux and theory of partitions gonna help in this?

We claim that the only ways to perform the trick is by: Putting 1 in one box (say red), 100 in one box (say green), and rest in the third one (yellow). If sum is <101, then green, if sum = 101, then yellow and if sum > 101 then red. Partitioning everything mod 3. If sum 0 mod 3, then box with 0 mod 3, if sum 1 mod 3, then box with 2 mod 3, if sum 2 mod 3, then box with 1 mod 3. We now show that these are the only possible arrangements. Suppose the cards in red box is $a_1<a_2<\cdots<a_r$, cards in green box is $b_1<b_2<\cdots<b_g$ and cards in yellow box are $c_1<c_2<\cdots<c_y$. Note, $r+g+y=100$. Let $A=\{a_1,a_2,\ldots,a_r\}$, $B=\{b_1,b_2,\ldots,b_g\}$ and $C=\{c_1,c_2,\ldots,c_y\}$. Let $1\leq x\leq a_i+b_j$. such that $x\neq a_i+b_j-x$. Then, if $x\in C$, then $a_i+b_j-x\in C$ is forced, or else if the audience yells $a_i+b_j$ to the magician, the magician will remain indecisive. Similarly, if $x\notin C$, then $a_i+b_j-x\notin C$ is also forced. It follows that $(x,a_i+b_j-x)$ both occur either in $A\cup B$ or in $C$. It follows that $|A+B|+|B+C|+|C+A|\leq197$ But from the fact that $|A+B|\geq|A|+|B|-1$ we get equality. So, $A,B,C$ has at least two singleton set or all of them are arithmetic progressions with same common difference. Suppose it is like $A=\{a\},B=\{b\},C=\{1,2,\ldots,100\}-\{a\}-\{b\}$. Then, if $a+c$ is announced with $c\in C$, then $a+c-b\in C$ as $c\neq a,b$. So, we may give faulty answer unless $a=1$ or $a=100$, which is when $a+c-b$ does not lie in the set $\{1,2,\ldots,100\}$ for any $c$, or else we can just have $c>b-a$ Suppose all three are arithmetic progressions with same common difference $d$. If $d>3$, we will not be able to cover all residue classes. So, $d\leq3$. If $d=1$, then the boxes are just $A=\{1,2,\ldots,x\},B=\{x+1,x+2,\ldots,y\},C=\{y+1,y+2,\ldots,100\}$. If $x>1$ and $y<99$ then $y+2=(y+1)+1$, which is not allowed. If $d=2$, it does not work because $1+4=2+3$.

WLOG 1 is in the red box. Now we have to look at two cases - whether 2 is in the same box as 1 or not. Case 1: 1 and 2 are in the red box. Now lets assume A is the smallest number in the white box, and B is the smallest number in the blue box, also WLOG $A < B$. We have that 2 + B = A + (B - A + 2) $\Rightarrow$ B - A + 2 must be in the white box. Now 1 + B = (B - A + 2) + (A - 1) $\Rightarrow$ A - 1 must be in the white box, but we claimed that A is the smallest number in the white box, but $A - 1 < A$ - contradiction, so this means there are no constructions in this case. Case 2: 1 is in the red box, WLOG 2 is in white box. Let C be the smallest number in the blue box. Let $C \not = 100$. Now if C + 1 is in the blue box, then (C + 1) + 1 = C + 2 - impossible. If C + 1 is in the white box again we have (C + 1) + 1 = C + 2 - impossible $\Rightarrow$ C + 1 must be in the red box. Now since (C + 1) + 2 = C + 3, similarly we get that 3 should be in the blue box. Now we will show by induction that $x \in red$ if $x \equiv 1 \pmod 3$, $x \in white$ if $x \equiv 2 \pmod 3$ and $x \in blue$ if $3 \mid x$. We had already shown the base. Now the inductive step is: from (x - 1) + (x - 2) = x + (x - 3) we get that x and x - 3 should be in the same box, since x - 1 and x - 2 are in different boxes $\Rightarrow$ in this case we get a construction depending on mod 3. Now if C = 100, then obviously C is the only number in the blue box. We will now show by induction that every other number is in the white box. We had already showed the base. Now the inductive step is: Since 100 + 1 = 2 + 99, this means that 99 is in the white box, so by (x - 1) + 100 = x + 99, this means that x is not in the red box. But x can't be in the blue box either, because 100 is there alone $\Rightarrow$ x is in the white box $\Rightarrow$ in this case we have the construction: 1 in one box, 100 in another and all the other numbers in the third box $\Rightarrow$ from all cases we get 2 working constructions. Since the colors of the boxes matter we have $2 \cdot 3! = 12$ possible ways to put the cards, such that the trick works $\Rightarrow$ the answer is 12.

The answer is $12$. We can either split the cards $\bmod \ 3$, or place $1$ and $100$ in their own boxes. Both methods clearly work. We now prove those are the only ways. Let $n$ be the number of cards. We induct on $n$. The base case of $4$ cards can easily be verified. Now assume the claim holds for $n$ cards. We consider two cases for the $n+1$th card: - If the $n+1$th card is in its own box, then cards $2, 3, \dots, n$ must be in the same box, since $(n+1) + 1 = n+2, (n+1) + 2 = n+3,$ etc. The three boxes are nonempty, so $1$ and $n+1$ are in their own boxes, and $2, 3, \dots, n$ are in the third box. - If $n+1$ is not in its own box, then the other $n$ cards must satisfy the conditions. Note that \begin{align*} (n+1) + 1 &= n + 2 \\ (n+1) + 2 &= n + 3 \\ (n+1) + 3 &= n + 4. \\ \end{align*}If $n$ and $1$ are in their own boxes, then $n+1$ must be in the same box as both $1$ and $2$, contradiction, so the cards must be split $\bmod \ 3$. Then using the above relations we obtain that $n+1$ must be in the box with the other cards that have the same remainder $\bmod \ 3$. Therefore, those are the only ways we can place the cards. They have $6$ permutations each, thus the answer is $12$.

I claim the answer is $12$, $6$ ways for sorting by mod $3$ and another $6$ for one box having $1$, another having $100$, and another having the rest. Note that if we can find two numbers in a box differing by $a$, and then we find two numbers in each of the other boxes differing by $a$, the trick cannot work. By Pigeonhole, there exists some box, WLOG let it be red such that two cards in the box have numbers differing by less than $4$. We do casework on the minimum difference. If there are two red cards differing by $1$, we are not allowed to have any consecutive cards labeled blue and white in some order. Listing the cards in order, that means we can write the cards in order as blocks of red, blocks of blue, and blocks of white, where no block of blue is adjacent to a block of white. Now if any block of blue has length greater than $1$, there are two blue cards with consecutive labels, thus no red and white cards can be consecutive, however this is clearly impossible since it would be imply white cards cannot be adjacent to either red or blue. Thus blue and white blocks must be singular. If we have a blue card and a white card, the cards immediately before each of them must both be red, similarly for the cards after them, UNLESS those cards don't exist. If those cards do exist, we see we fail so we require that one of the cards is at the beginning and the other is at the end. If there are two red cards differing by $2$, consider the card in between, WLOG let it be blue, so there are no pairs of white and blue cards with gap 2. Clearly, the cards two away from the blue card must be blue (at least one of these cards must exist), but this implies that there exists no pairs of red and white cards with gap 2. This implies that white cards only have white cards two away from them. This is only possible if the white cards fill up all the numbers $1$ to $100$ alternating, but this is impossible since we know at least three cards that are not white. If there are two red cards differing by $3$, consider the two cards in between, clearly by minimum gap these cards are of different colors. Consider the card directly after, it can't be any of the two cards before so it is forced. Likewise we can just force everything from here using identical logic and it's forced to be mod $3$ pattern.

Let the numbers in the red box, white box, and blue box be $A=(a_1, a_2, \dots, a_k), B=(b_1, b_2, \dots, b_l), C=(c_1, c_2, \dots, c_m).$ Since there is a maximum of $197$ distinct sums (from $1+2$ to $99+100$) and $|A+B| \ge A+B-1$ (similarly for others), we get (first ineq follows from sums do not overlap or else trick does not work) $$197 \ge |A+B|+|B+C|+|C+A| \ge 2(A+B+C)-3=197.$$Thus, $|A+B|=A+B-1$ (similarly for others), which implies $A, B, C$ are arithmetic sequences with the same common difference, $d$ (to see why, look at example $1.1$ from handout). By Pigeonhole Principal, one of these sets contains $34$ elements, so $d \in \{1,2,3\}.$ Lets do casework: -If $d=1:$ WLOG let $A = (1,2,\dots, k), B=(k+1, k+2, \dots, k+l), C=(k+l+1, k+l+2, \dots, 100).$ If $|A| \ge 2,$ we see that ($k \in A, k+1 \in B, k-1 \in A, k+l+1 \in C$) $$(k)+(k+l)=(k-1)+(k+l+1),$$so the trick fails. Thus $|A|=|C|=1$. Accounting for permutations, we get a total of $6$ possibilities. -If $d=2:$ In this case, all the terms in any given box must have the same parity. Furthermore, two boxes have same parity and remaining box have other parity. Suppose two boxes have odd parity. WLOG let $A=(1,3,\dots,2k-1), B=(2k+1,2k+3,\dots,99), C=(2,4,\dots,100).$ We see that $$(2k-1)+(4) = (2k+1)+(2),$$which fails the trick. Trick also fails if two boxes have even parity, so we get $0$ possibilities. -If $d=3:$ All the terms in any given box must have the same remainder modulo $3.$ WLOG let $A=(1,4,7,\dots,100), B=(2,5,8,\dots,98), C=(3,6,9,\dots,99).$ Any term in $A+B$ has value $0 \pmod{3},$ any term in $B+C$ has value $2 \pmod{3},$ and any term in $C+A$ has value $1 \pmod{3}.$ These are all distinct, so the trick indeed works. Accounting for permutations, we get a total of $6$ possibilities. In total, we have $\boxed{12}$ ways.