Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Here is a question from one of my students:

suppose 8 players are in an elimination match. The players are marked with marked with either R (for rock), P (for paper) or S (for scissors). If two players are marked with the same letter, then one is picked as winner of this round. An example of this sort of matches is:

First round:R-P S-S R-S P-S

Second round: P-S R-S

Third round: S-R

Champion: R

The question is:Given r+p+s=8, for the match that there are r many R, p many P and s many S, if the table for the elimination match is assigned randomly, what is the probability that a S became the champion?

A more general question is: for a match with 2^n players, and given r+p+s=2^n, how much chance can some S wins the champion?

My answer did not meet his satisfaction. What I know is, firstly for small n, one can list all possibilities (there are (2^n)! many, if we make a distinction between two rocks etc.)and find the answer; secondly, one may use a computer program to solve the general question by inputting r,p and s; thirdly, one can also do some induction to find a pattern for the general question; and lastly, if the number r,p and s are assigned randomly and we let n goes to infinity, and the answer should be a third.

So can we have some smart ways to figure out these questions? Or can we reduce them to other known questions? I guess graph theory may help but my knowledge is very limited there.

share|improve this question
6  
Are you permitted to slap the students? –  Will Jagy Oct 18 '12 at 1:43
7  
For large $n$, a relevant keyword is evolutionary game theory. –  Johan Wästlund Oct 18 '12 at 8:01

3 Answers 3

Here is a generating function approach. A $P$-tree $T$ of length $n$ is a complete binary tree of length $n$ with vertices labelled $p,r,s$ such that the root is $p$, the children of $p$ are either $p,p$ or $p,r$, the children of $r$ are either $r,r$ or $r,s$, and the children of $s$ are either $s,s$ or $s,p$. Similarly define $R$-trees and $S$-trees. The weight $w(T)$ is the product of all leaf vertices. Let $P(n)=\sum_T w(T)$, summed over all $P$-trees of length $n$, and similarly define $R(n)$ and $S(n)$. Thus $$ P(0)=p,\ \ \ P(1)=p^2+2pr, $$ $$ P(2)=p^4+4p^3r+6p^2r^2+4sp^2r+4pr^3+8pr^2s. $$ Clearly $$ P(n+1) = P(n)^2+2P(n)R(n), $$ and similarly for $R(n+1)$ and $S(n+1)$. We can eliminate two of the functions from these three recurrences and obtain a recurrence for each function alone. For $P(n)$ the recurrence is the following, writing e.g. $p3$ for $P(n+3)$: $$ 0 = 4 p2^4 p0^4+p2^2 p1^6-p2 p1^8-8 p1^5 p0^2 p3+16 p1^4 p0^4 p3 $$ $$ -8 p1^3 p0^6 p3+4 p1^2 p0^4 p2^3-16 p1 p0^6 p2^3+12 p1^7 p0^2 p2 $$ $$ -18 p1^6 p0^4 p2+12 p1^5 p0^6 p2-4 p2^2 p1^5 p0^2+12 p0^6 p2^2 p1^3$$ $$ -6 p2^2 p1^4 p0^4+9 p1^2 p0^8 p2^2-9 p2 p1^4 p0^8. $$ Is there a simpler recurrence? The highest term is $p3=P(n+3)$, so the initial conditions are $P(0),P(1),P(2)$. The coefficient of $p3$ is $$ -8 p1^5 p0^2+16 p1^4 p0^4-8 p1^3 p0^6. $$ Thus there is a "Laurent phenomenon" behavior, since it is not at all a priori clear why we get an answer that is a polynomial (with nonnegative coefficients). For more on the Laurent phenomenon, see e.g. http://arxiv.org/abs/math/0104241.

share|improve this answer
1  
There seems to be an earlier question about rock-paper-scissors: mathoverflow.net/questions/93669/rock-paper-scissors where David Speyer was also uncovering interesting mathematics related to the game. –  Patricia Hersh Oct 19 '12 at 18:50

Let $R(r,p,s)$, $P(r,p,s)$, $S(r,p,s)$ be the probabilities of rock, paper, scissors with initial distribution $r,p,s$, where $r + p + s$ is a power of $2$. Now for $r+p+s = 2^{n+1}$, rock will win the last round if the results of the second-last round are rock and rock or rock and scissors, so considering the probability ${r \choose r'}{q \choose q'}{s \choose s'}/{{2^{n+1}} \choose {2^{n}}}$ of the first half of the contestants being marked with $r'$, $q'$, $s'$ rocks, paper and scissors, we get $$ \eqalign{R(r,p,s) &= \sum_{r'+p'+s'=2^n} \dfrac{{r \choose r'}{p \choose p'}{s \choose s'}}{{2^{n+1}} \choose {2^{n}}} (R(r',p',s') S(r-r',p-p',s-s')\cr & + R(r',p',s') R(r-r',p-p',s-s') + S(r',p',s') R(r-r',p-p',s-s'))\cr}$$ the sum being over all $r', p', s'$ with $0 \le r' \le r$, $0 \le p' \le p$, $0 \le s' \le s$ and $r' + p' + s' = 2^n$, and similarly with $R,S$ replaced by $P,R$ or $S,P$.

share|improve this answer

It's not immediate whether rock can win at all, although I think it should be possible to work that out. For example, if $(r,p,s) = (3,4,1)$ then rock can't win, but at $(2,4,2)$ rock wins with probability $8/105$.

$3^8$ is only $6561$ so I wrote a few lines of Mathematica code to enumerate the $8$-player tournaments. Here is a table of probabilities with which rock wins:

(8,0,0): 1
(7,1,0): 0  (7,0,1): 1
(6,2,0): 0  (6,1,1): 1/7   (6,0,2): 1
(5,3,0): 0  (5,2,1): 2/21  (5,1,2): 1/3     (5,0,3): 1
(4,4,0): 0  (4,3,1): 1/35  (4,2,2): 23/105  (4,1,3): 19/35  (4,0,4): 1
(3,5,0): 0  (3,4,1): 0     (3,3,2): 6/35    (3,2,3): 3/7    (3,1,4): 26/35   (3,0,5): 1
(2,6,0): 0  (2,5,1): 0     (2,4,2): 8/105   (2,3,3): 2/5    (2,2,4): 74/105  (2,1,5): 19/21  (2,0,6): 1
(1,7,0): 0  (1,6,1): 0     (1,5,2): 0       (1,4,3): 8/35   (1,3,4): 16/35   (1,2,5): 2/3    (1,1,6): 6/7  (1,0,7): 1
share|improve this answer
4  
Rock can win iff $s+\log_2 r\ge n$ and $r\ge 1$. –  Yoav Kallus Oct 18 '12 at 2:03

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.