Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
How does someone win this game? For what reason are the stick fragments compared? –  Arthur Fischer Aug 9 '12 at 12:38
    
@ArthurFischer Updated! –  Fan Zhang Aug 9 '12 at 12:42
    
@Arthur: I suspect that the larger piece in each comparison scores a point, and the player with the larger number of points wins. –  Brian M. Scott Aug 9 '12 at 12:42
1  
@joriki Thank you for your advice. I will read about Nash equilibria. –  Fan Zhang Aug 9 '12 at 13:12
1  
@joriki Thank you, updated. –  Fan Zhang Aug 9 '12 at 13:31
show 12 more comments

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.