There is a chess tournament planned. It is a single-elimination tournament, and for spectacle purposes, only one match at a time will take place, on a table in the middle of the stage (winners will have to move if they don't play the next match).

Luckily, the organisers succeeded in inviting a grand chess champion to the tournament. Let's call him MC (for main character, of course).

However, MC doesn't like to stand once he's seated. Also, as the grand champion, he's sure to win every match he would play. His condition to come to the tournament is to never stand once he's asked to play. It is quite easy to find a solution: just let all other matches take place and let him come at the end to play the remaining matches. The following figure shows how to do it (sources are players, internal vertices are matches, blackened vertices are finished matches before MC comes). The matches could take place in order 1-2-3-5-4-6-7 to get what the organisers want.


Now consider the following problem: if we don't consider MC as a special player, but just want to minimize the number of times a player has to stand, how to do it. A natural order to play the matches in the previous tree would be 1-2-3-4-5-6-7, but that would result in a total of 5 players standing after a match. The order 1-2-5-3-4-6-7 would result in only 3 players standing after a match. This could be generalized to $n=2^k$ players: let $S(n)$ be the number of times a non-eliminated person has to stand before playing again. Then with the same idea, we could get $S(2) = 0$ and $S(n) = 2S(n/2) + 1$, meaning $S(n) = \frac{n}2-1$ (note that this is the same solution as the one to let MC sit), which is better than the $n-3$ naive order .

Now my questions are:

  1. Is this optimal? (this looks like it, but who knows)
  2. How to find the optimal order if there is a loser bracket?
  3. In general, how to find the optimal order if we consider an acyclic directed graph with only one sink, and indegrees/outdegrees at most 2?
  4. For the last two points, is there a difference if we try to find an order before the matches, or if we try to adapt the order depending on who lost or won their matches? (I don't think so, but I am not so sure if there is no direct elimination).


Your Answer

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