A magician has one hundred cards numbered 1 to 100

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Valentin Vornicu

7301 posts

Valentin Vornicu

#1 h Oct 24, 2005, 10:21 AM • 6 Y

Y by SSaad, junioragd, Adventure10, ImSh95, Mango247, and 1 other user

A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card. A member of the audience draws two cards from two different boxes and announces the sum of numbers on those cards. Given this information, the magician locates the box from which no card has been drawn.

How many ways are there to put the cards in the three boxes so that the trick works?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

grobber

7849 posts

grobber

#2 h Oct 24, 2005, 7:42 PM • 6 Y

Y by ValidName, Adventure10, ImSh95, Mango247, Sagnik123Biswas, and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bambaman

345 posts

bambaman

#3 h Mar 19, 2009, 10:15 PM • 2 Y

Y by ImSh95, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zhero

2043 posts

Zhero

#4 h Mar 25, 2011, 12:05 AM • 8 Y

Y by Nelu2003, Guardiola, mueller.25, Taopopai, ImSh95, Adventure10, Mango247, and 1 other user

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

utkarshgupta

2280 posts

utkarshgupta

#5 h Jul 30, 2014, 2:23 PM • 11 Y

Y by Wizard_32, Lukaluce, mueller.25, michaelwenquan, ImSh95, Adventure10, Mango247, Titibuuu, fearsum_fyz, megarnie, and 1 other user

I think these solutions are a bit complicated for C1.

Can anybody provide the official solutions ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

infiniteturtle

1131 posts

infiniteturtle

#6 h Sep 3, 2014, 9:49 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DrMath

2130 posts

DrMath

#7 h Jun 28, 2015, 5:19 PM • 2 Y

Y by ImSh95, Adventure10

Induct

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.

This post has been edited 1 time. Last edited by DrMath, Jun 28, 2015, 5:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shinichiman

3212 posts

shinichiman

#8 h Mar 30, 2016, 6:59 AM • 2 Y

Y by ImSh95, Adventure10

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.

Induction solution.

This solution has a similar approach with India TST 2003.

This post has been edited 1 time. Last edited by shinichiman, Mar 30, 2016, 7:02 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#9 h Feb 20, 2018, 6:29 PM • 10 Y

Y by Nelu2003, Wizard_32, ValidName, v4913, michaelwenquan, ImSh95, CahitArf, Adventure10, Mango247, Sagnik123Biswas

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$ , are disjoint arithmetic progressions with the same common difference $d$ . As two of 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$ .

This post has been edited 4 times. Last edited by v_Enhance, Apr 14, 2019, 2:16 PM
Reason: fix mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#10 h Aug 28, 2019, 7:48 AM • 3 Y

Y by ImSh95, Adventure10, Titibuuu

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Idio-logy

206 posts

Idio-logy

#11 h Oct 23, 2019, 12:50 AM • 2 Y

Y by ImSh95, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Stormersyle

2786 posts

Stormersyle

#13 h Feb 14, 2020, 3:59 AM • 2 Y

Y by ImSh95, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sa2001

281 posts

sa2001

#14 h Mar 20, 2020, 3:34 PM • 2 Y

Y by ImSh95, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AleksaS

41 posts

AleksaS

#15 h Aug 14, 2020, 6:17 PM • 1 Y

Y by ImSh95

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$

This post has been edited 1 time. Last edited by AleksaS, Aug 14, 2020, 6:21 PM
Reason: Comment

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#16 h Sep 18, 2020, 6:33 AM • 1 Y

Y by ImSh95

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 is a singleton. Then $X=\{a,a+d,\ldots,a+(x-1)d\}$ , $Y=\{b,b+d,\ldots,b+(y-1)d\}$ , for some 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.

This post has been edited 1 time. Last edited by pad, Sep 18, 2020, 6:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Godlex04

1 post

Godlex04

#38 h Feb 23, 2023, 10:50 PM • 1 Y

Y by ImSh95

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#40 h Jun 4, 2023, 9:23 PM • 1 Y

Y by ImSh95

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.

This post has been edited 1 time. Last edited by huashiliao2020, Jun 4, 2023, 9:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

281 posts

peppapig_

#41 h Jun 29, 2023, 4:49 PM • 1 Y

Y by ImSh95

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.

This post has been edited 1 time. Last edited by peppapig_, Jun 29, 2023, 4:51 PM
Reason: Formatting

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Curious_Droid

35 posts

Curious_Droid

#42 h Sep 17, 2023, 8:56 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2533 posts

joshualiu315

#43 h Nov 25, 2023, 6:06 AM

Y by

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.

This post has been edited 1 time. Last edited by joshualiu315, Nov 25, 2023, 6:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5603 posts

megarnie

#44 h Feb 11, 2024, 9:15 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathhotspot

70 posts

mathhotspot

#45 h Feb 12, 2024, 1:24 AM

Y by

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Pyramix

419 posts

Pyramix

#46 h Feb 13, 2024, 7:39 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Markas

105 posts

Markas

#47 h May 26, 2024, 5:30 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lnzhonglp

120 posts

lnzhonglp

#48 h Jun 6, 2024, 8:12 AM

Y by

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

This post has been edited 2 times. Last edited by lnzhonglp, Jun 6, 2024, 8:15 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1261 posts

ezpotd

#49 h Aug 24, 2024, 1:39 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bebebe

992 posts

bebebe

#50 h Aug 25, 2024, 12:53 AM

Y by

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.

This post has been edited 1 time. Last edited by bebebe, Aug 25, 2024, 12:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

1007 posts

bjump

#51 h Mar 13, 2025, 3:46 PM

Y by

I claim their are $12$ ways in order to put the cards into three boxes so that the trick works.

Given two distinct positive integers between $1$ and $100$ inclusive, their possible sum ranges from all positive integers $1+2=3$ to $99+100 =199$ inclusive. Therefore their are $199-2=197$ distinct possible sums. Now suppose that the magician places $r$ cards in the red box, $w$ cards in the white box, and $b$ cards in the blue box. Note that by OTIS Equality Walkthrough 1.1 their are at least $r+w-1$ distinct possible sums when taking two cards one from red and one from white, similarly their are $w+b-1$ sums taking from white and blue, and $r+b-1$ when taking from red and blue. Equality occurs if and only if the cards in each box form an arithmetic progression with the same common difference. We observe that $(r+w-1)+(w+b-1) + (b+r-1) \ge 200-3 = 197$ . Since all of these sums must be distinct we must have all sums $3$ through $197$ occur in exactly one possible way, and the terms of each number in each box must form an arithmetic progression

Now suppose without loss of generality that $1$ is placed into the red box. The sum $1+2 = 3$ must occur once therefore $2$ must be placed in a separate box than $1$ . Without loss of generality we will assume that this is the white box. Notice that $3$ cannot be placed in the red box because then the sum $1+3=4$ will be impossible to occur. If $3$ is in the blue box. Then the fact that the common differences must be the same forces $4$ to go into the red box. Which gives us a partition based on residue modulo $3$ . If $3$ is in the white box. Since the common differences must be $1$ we cannot put any more numbers into the red box. We also cannot have $100$ and $99$ in the same box because then it will be impossible to obtain $199 = 100 + 99$ as a sum. Therefore we must have $1$ in the red box $2$ through $99$ in the white box, and $100$ in the blue box. The magician can tell which box that no card has been drawn in with the mod $3$ partition because if the sum is $0$ mod $3$ the blue box hasn't been chosen, if the sum is $1$ mod $3$ the white hasn't been chosen, if the sum is $2$ mod $3$ the red has not been chosen. For the $1$ , and $100$ by themselves partition if the sum is between $3$ and $100$ the blue has not been chosen, if the sum is $199$ the white has not been chosen, if else the red has not been chosen. Due to our WLOGS we multiply the number of ways by $6$ because of $3!=6$ permutations of the colors. So the answer is $2 \cdot 6 = 12$ ways to but the cards in the three boxes so that the trick works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sleepy_Head

565 posts

Sleepy_Head

#52 h Apr 14, 2025, 1:36 PM

Y by

The condition is equivalent to $A+B,B+C,C+A$ being disjoint.
Claim. $|A+B| \ge |A|+|B|-1$ , with equality when $A$ and $B$ are arithmetic sequences with a shared common difference.
Proof. Let $A=\{a_1,a_2,\dots,a_m\}$ , $B=\{b_1,b_2,\dots,b_n\}$ . Then
$a_1+b_1<a_1+b_2<\dots<a_1+b_n<a_2+b_n<\dots<a_m+b_n.$ This proves the bound. Now we prove the equality case. We induct: the result is clearly true for $m=1$ or $n=1$ , so henceforth assume $m,n \ge 2$ and $A$ and $B$ are arithmetic sequences with shared common difference $r$ . Suppose adding some element $a_{m+1}>a_m$ to $A$ : we claim that if $|A+B|=m+n$ , then $a_{m+1}=a_m+r$ . Note that
$a_1+b_1<a_1+b_2<\dots<a_1+b_n<a_2+b_n<\dots<a_m+b_n<a_{m+1}+b_n.$ Hence,
$\{a_{m+1}+b_1,a_{m+1}+b_2,\dots a_{m+1}+b_{n-1}\} \subset \{a_1+b_1,a_1+b_2,\dots,a_1+b_n,a_2+b_n,\dots,a_m+b_n\}.$ (Where the latter set is sorted in increasing order.) Note that $a_{m+1}+b_{n-1}>a_{m-1}+b_n$ since $a_{m+1}>a_m=a_{m-1}+r$ while $b_n=b_{n-1}+r$ . Thus, $a_{m+1}+b_{n-1}=a_m+b_n$ . But then $a_{m+1}=a_m+r$ since $b_n=b_{n-1}+r$ , as desired.

The case where we increment $n$ by $1$ is identical. This proves the claim.

Now, taking the claim cyclically, we have
$|A+B \cup B+C \cup C+A| \ge 2|A|+2|B|+2|C|-3=197,$ where we note $|A|+|B|+|C|=100$ . However, we also have that
$A+B \cup B+C \cup C+A=\{3,4,\dots,199\}$ (i.e. the set of all possible sums of two distinct integers from 1 to 100), so equality is achieved and we must have $|A+B|=|A|+|B|-1$ and cyclically. Thus, $A,B,C$ are arithmetic sequences with shared common difference. Note that this common difference is at most $3$ , since if it was $4$ , then $|A|+|B|+|C| \le 3 \cdot \frac{100}{4}=75<100$ (one can also note $A \cup B \cup C$ would have only $3<d$ distinct residue classes mod $d$ ). From here, it’s simply casework to determine the solutions: one finds that they are $\{A,B,C\}=\{\{1\},\{100\},\{2,\dots,99\}\}$ and $\{A,B,C\}=\{\{1,4,\dots,100\}$ , $\{2,5,\dots,98\}$ , $\{3,6,\dots,99\}\}$ , giving $2 \cdot 3!=\boxed{12}$ solutions.

This post has been edited 1 time. Last edited by Sleepy_Head, Apr 14, 2025, 1:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1533 posts

YaoAOPS

#53 h Apr 23, 2025, 3:27 PM

Y by

This is equivalent to partitioning $\{1, 2, \dots, 100\}$ into nonempty $A \sqcup B \sqcup C$ such that $A + B, B + C, C + A$ are all disjoint.

Claim: $|A+B| \ge |A|+|B| - 1$ , with equality if and only if $A$ and $B$ are arithmetic progressions with the same difference, or one has size $1$ .
Proof. Let $a_1 < a_2 < \dots < a_m$ be the elements of $A$ and $b_1 < b_2 < \dots < b_n$ be the elements of $B$ . Then $a_1 + b_1 < a_1 + b_2 < \dots < a_1 + b_n < a_2 + b_n < \dots < a_m + b_n$ giving the inequality.
For equality, we prove the base case $|A| = 2$ by first shifting $A = \{0, d\}$ and noting that for $|B + \{0, d\}| = |B| + 1$ , this means that each arithmetic progression of difference $d$ intersects $B$ one time so $B$ is such an $AP$ .
For $|A| \ge 3$ , we induct downwards. Note that by considering $a_1 + b_1$ , $(A \setminus a_1) + B$ , it must follow for equality that $A \setminus a_1$ and $B$ are APs with the same difference. Similarly, $A \setminus a_n$ and $B$ must have the same difference, so the result follows.
However, note that $|A+B| \ge |A|+|B| - 1$ by taking a chain of monotonically increasing elements, so $|A+B| + |B+C| + |C+A| \ge 2(|A|+|B|+|C|) - 3 = 197$ . At the same time, the elements in these sets can only range from $1+2 = 3$ to $99+100 = 199$ , ergo $(A+B) \sqcup (B+C) \sqcup (A+C) = \{3, 4, \dots, 197\}$ and thus equality must hold in the earlier inequalities. $\blacksquare$
If two of $A, B, C$ , WLOG $A = \{a\}$ and $B = \{b\}$ , have size $1$ , then we can manually check that unless $\{a, b\} = \{1, 100\}$ , there exists $c, d \in C$ such that $|c-d| = |a-b|$ which contradicts this result, else it works.
Next, suppose $A$ has size $1$ and $B, C$ are APs with the same difference $d \in \{1, 2\}$ by size. In this case, WLOG let $A = \{a\}$ and let $1 \le b = a \pm d \le 100$ be WLOG in $B$ . Then if $c, c+d \in C$ , then $|a-b| = |(c+d)-c|$ gives a contradiction.
Finally, $A, B, C$ must be APs with the same size, then the AP difference must be size $3$ , which works by taking $\pmod{3}$ . This gives us in total $12$ ways to do this.

Z K Y