# Error in solution of Peter Winkler “red and blue dice” puzzle?

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 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_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', 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.

• Thanks. I tried setting $1'=0,$ but somehow I couldn't make it work. – saulspatz Dec 11 '18 at 18:49

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.

Yes, take $$\alpha_n\leq \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 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 then necessarily $$M'>0$$ because $$\beta_{M'}>\beta_{m'}.$$