This question relates to the solution give in Peter Winkler's Mathematical Mind-Benders to the "Red and Blue Dice" problem appearing on page $23.$
You have two sets (one red, one blue) of $n\ n-$sided dice, each die labeled with the numbers from $1$ to $n.$ You roll all $2n$ dice simultaneously. Prove that there must be a nonempty subset of the red dice and a nonempty subset of the blue dice with the same sum!
I tried to prove it by induction. There must be an $n$ rolled or we can remove one die of each color and get a counterexample to the $n-1$ case. If there is only on $n$ rolled, we can remove it, and any die of the other color, and again get a counterexample. So there are at least two red $n$'s, say. But I couldn't carry the induction idea any further. I proved it up to $n=6,$ hoping to spot a pattern, but all I got was a collection of ad hoc arguments. After several days, I gave up and looked at the answer.
A solution is given on pages $33-34.$ Winkler advises proving a stronger statement.
In fact, there is a much stronger statement than the one you were asked to prove, which is nonetheless still true. Organize the red dice into a line, in any way you want, and do the same with the blue dice. Then there is a contiguous nonempty subset of each line with the same sum.
To put it more mathematically, given any two vector $\langle a_1,\dots,a_n\rangle$ and $\langle b_1,\dots,b_n\rangle$ in $\{1,\dots,n\}^n,$ there are $j\le k$ and $s\le t$ such that $\sum_{i=j}^k{a_i}=\sum_{i=s}^t{b_i}.$
To see this, let $\alpha_m$ be the sum of the first $m\ a_i$'s and let $\beta_m$ be the sum of the first $m\ b_i$'s. Assume that $\alpha_n\le\beta_n$ (otherwise we can switch the roles of the $a$'s and $b$'s), and for each $m,$ let $m'$ be the greatest index for which $\beta_{m'}\le\alpha_m.$
Winkler gives a diagram with two sample strings, lines joining $a_m$ and $b_{m'}$ labeled by $\alpha_m-\beta_{m'}$
It is apparent that the $a_i$ are the dice on top and the $b_i$ those on bottom. Note that we have $\alpha_6=22,\ \beta_6=18,$ contradicting $\alpha_n\le\beta_n,$ so I imagine that the latter was a typo. Also, the line labeled $3$ joining $a_3$ and $b_4$ should really end at $b_5$ and be labeled $0,$ but I guess this is just a mistake.
Anyway, Winkler says,
We always have $\alpha_m-\beta_{m'}\ge0,$ and at most $n-1$ (if $\alpha_m-\beta_{m'}$ were larger than or equal to $n,\ m'$ would have been a larger index.)
He then goes on to observe that if any of the labels is $0$ we are done, so we have $n$ labels from $1$ to $n-1$ and two are equal. Then the sum of the intervening dice must be the same. For example, in the picture we have two lines labeled $2,$ and we have $6+5+3=3+2+3+6.$
It seems to me that there are two holes in this proof. The first is in the statement that the labels must be less than $n$. Suppose that $\alpha_n-\beta_n\ge n.$ Then $n'=n,$ and there is no larger index available. Then perhaps $\alpha_n\le\beta_n$ is right after all, and the diagram is wrong. But this leaves the second problem, which doesn't depend on the relation between $\alpha_n$ and $\beta_n.$ Suppose that $a_1<b_1.$ How is $1'$ to be defined?
I thought about abandoning the stronger statement, and attempting to solve the puzzle by arranging the $a_i$ in decreasing order and the $b_i$ in increasing order, but I don't see how to dispose of the case $\max{a_i}>\min{b_i}.$ Winkler's argument can't be applied, and I don't see how to dispose of it otherwise.
I haven't been able to rescue this proof. Am I overlooking something? Can you solve the puzzle?
Note: Winkler say that some similar results can be found in a paper by Diaconis, Graham, and Sturmfels. I haven't tried to read the paper yet, but it looks a little heavy for the solution to a puzzle. Also, Winkler says that the source of the puzzle was David Kempe of USC, "who needed the result in a computer science paper," but gives no further reference.
P.S.
I found a list of David Kempe's publications, but I can't tell which is likely to contain a proof of the theorem.
Best Answer
The figure is mistaken, but the proof is not, after a small clarification. Ignore the figure.
Winkler intended to assume $\alpha_n\le \beta_n$. Furthermore, he intended $0$ to be an allowable index when choosing $m'$, where $\beta_0=0$. This ensures ${m'}$ exists. For each $m\ge 1$, we have $\alpha_m \ge \beta_0$. This implies that $\{i:0\le i\le n,\alpha_m\ge \beta_i\}$ is nonempty; possibly it only contains $i=0$. We then let $m'$ be the largest element of this set.
By definition, $\alpha_m-\beta_{m'}\ge 0$. If $\alpha_m-\beta_{m'}\ge n$, then it must be that $m'<n$, because $\alpha_m\le \alpha_n \le \beta_n$. We can then consider $\beta_{m'+1}$, and would have $\beta_{m'+1}=\beta_{m'}+((m'+1)^{st}\text{ dice})\le \beta_{m'}+n\le \alpha_m$, contradicting the maximality of $m'$. Therefore you have $0\le \alpha_m-\beta_{m'}\le n-1$ and the rest of the proof follows.