3
$\begingroup$

Consider a rock, paper scissors (one wins, one loses) tournament with n players where everybody plays against eachother exactly once:

what's the maximum number, $z=z(n)$, of games that assure that at least one player has won z times?

The first thing i think is needed is to determine the number of matches, N, which is $N=\frac{(n-1)n}{2}$, now what i dont know is how to calculate how many of those $N$ matches need to be played before someone has won at least $z$ times.

$\endgroup$
3
$\begingroup$

Note that if $N \geq n(z-1)+1$, then by the Pigeonhole principle there must be some player who has won at least $z$ games. Thus setting $z = \lfloor (N-1)/n \rfloor + 1 = \lceil (n-1)/2 \rceil$ is always safe. To show that this is the best we can do, consider the following: all players sit in a circle. For the match between player $A$ and player $B$, let $A$ win if and only if $B$ is closer on $A$'s right side than on $A$'s left. For matches where $A$ and $B$ are directly across from one another, either $A$ or $B$ may win (this only happens when $n$ is even). If the results of the rock-paper-scissors matches follow this pattern, then the number of matches won by each player is easy to calculate: it is $(n-1)/2$ if $n$ is odd, and either $n/2$ or $n/2 - 1$ if $n$ is even. In either case, each player wins at most $z = \lceil (n-1)/2 \rceil$ games, so we could not have chosen $z$ to be any larger.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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