Strategy for a game of breaking sticks

Two persons have 2 uniform sticks with equal length which can be cut at any point. Each person will cut the stick into $n$ parts ($n$ is an odd number). And each person's $n$ parts will be permuted randomly, and be compared with the other person's sticks one by one. When one's stick is longer than the other person's, he will get one point. The person with more points will win the game. How to maximize the probability of winning the game for one of the person. What is the best strategy to cut the stick.

Solution 1:

When intuition doesn't help, try brute force.

trials = Table[With[{k = RandomReal[{0, 1}, {7}]}, k/Total[k]], {50}]; Column[Sort[Transpose[{Total /@ Table[Total[Sign[trials[[a]] - trials[[b]]]], {a, 1, 50}, {b, 1, 50}], trials}]]]

Now we can look at some best/worst performers.

{-55, {0.018611, 0.0405574, 0.032157, 0.333219, 0.311017, 0.17885, 0.0855879}},
{-39, {0.313092, 0.178326, 0.0454452, 0.064321, 0.228231, 0.0907115,0.0798742}},

{29, {0.0360088, 0.220396, 0.13208, 0.145903, 0.180813, 0.240151, 0.044648}},
{29, {0.0799122, 0.0547817, 0.234127, 0.119589, 0.0290167, 0.255561,0.227013}},
{33, {0.0541814, 0.216338, 0.0619272, 0.204252, 0.0254828, 0.225743,0.212075}}

So, in the case of 7 pieces, best strategy seems to be to give 3 tiny pieces and 4 larger pieces. With some bigger trials, 2 tiny pieces and 5 larger pieces seemed best. But this is a competitive game ... so I selected the top 10% of a larger trial, and then had those guys compete. This time the winner was to have 3 values of 2/7 and one value of 1/7 {0.0263105, 0.0848388, 0.228165, 0.249932, 0.0788568, 0.215831, 0.116066}

Your iterations may behave differently.

Solution 2:

Here's a (partial) answer to the setting where the number of sticks is 3 (i.e. $n = 3$). With some effort, one can show the following claims:

Given the strategy $(a,a,b)$ where $a \ge b$ (i.e. you break your stick into two equal parts of size $a$ and one smaller part of size $b = 1-2a$), the optimal value for $a$ is $\frac13$. That is, breaking your stick into three equal parts maximizes the number of strategies you beat.

Another similar claim: given the strategy $(a,b,0)$ (i.e. break your stick into three parts - one of length $a$, one of length $b = 1-a\le a$ and one of length 0), the optimal value of $a$ is $a = \frac12$.

Generally speaking, this is proven by drawing the space of strategies as an equilateral triangle in barycentric coordinates, dividing that triangle into spaces of strategies (triangles, trapezoids and such), and seeing what's the likelihood of your given strategy beating another strategy in that space.

For example, the strategy $(\frac13,\frac13,\frac13)$ beats any strategy that has two sticks of length $<\frac13$, and loses to all other strategies (there are some strategies with one stick of length $\frac13$, but these have measure 0 so are ignored) at all times. Two thirds of the strategies have two sticks of length $< \frac13$, so it beats strategies $2/3$ of the time.

Alternatively, for $(\frac12,\frac12,0)$, It surely beats any strategy that has two sticks of length $<\frac12$, and beats any strategy with one stick of length $>\frac12$ and two with length $< \frac12$ w.p. $\frac13$. So in total its expected winning probability is $\frac14\cdot 1 + 3\cdot\frac14\cdot \frac13 = \frac12$. (take an equilateral triangle and divide into 4 equal equilateral triangles.

I'll be happy to write a formal proof of this, but now I'm a bit busy :)

My thought is that in general it would be hard to prove anything about this setting for $n \ge 5$, but I may be wrong...