Qfyilyi

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_nrangle$ and $langle b_1,dots,b_nrangle$ in ${1,dots,n}^n,$ there are $jle k$ and $sle 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_nlebeta_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'}lealpha_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_nlebeta_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_nge n.$ Then $n'=n,$ and there is no larger index available. Then perhaps $alpha_nlebeta_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.

The figure is mistaken, but the proof is not, after a small clarification. Ignore the figure.

Winkler intended to assume $alpha_nle beta_n$. Furthermore, he intended $0$ to be an allowable index when choosing $m'$, where $beta_0=0$. This ensures ${m'}$ exists. For each $mge 1$, we have $alpha_m ge beta_0$. This implies that ${i:0le ile n,alpha_mge 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_mle 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'}+nle alpha_m$, contradicting the maximality of $m'$. Therefore you have $0le alpha_m-beta_{m'}le n-1$ and the rest of the proof follows.

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_nge n.$ Then $n'=n,$ and there is no larger index available. Then perhaps $alpha_nlebeta_n$ is right after all, and the diagram is wrong.

Yes, take $alpha_nleq beta_n.$

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?

Set $1'=0.$ When you take the intervening dice between two different "$m$"'s the lower "$m$" is excluded, so it's fine to use zero here. The higher "$m$" is included, but that's ok: if $alpha_m-beta_{m'}=alpha_M-beta_{M'}=c$ with $m<M$ then necessarily $M'>0$ because $beta_{M'}>beta_{m'}.$