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