Since the NBA playoffs are on the horizon we will be topically appropriate.
You have N NBA teams (say 8) and each is assigned a 'goodness' value between [0,1]. They play a tournament to find the best team. A tournament is a series of games between 2 teams.
Unfortunately, teams can have off days, and so there is a small probability p that in game the weaker team wins.
Design a tournament so that the probability that the best team does not win the tournament is less than some Q.
For the sake of your audience we want only O(N) games!
Adding even more (fake) reality, how many days must the tournament last if each team can play only one game on any given day ?
Subscribe to:
Post Comments (Atom)
Posts
What is the winning condition? Having maximum number of wins?
ReplyDeleteapproximate soln which is probably wrong: wlog assume p < 0.25, Q=1/3, as these only change constant in front of games played. First round N/2 games, winners proceed. Second round everyone plays 2 games, teams with at least 2 wins so far proceed. Third round each team again plays 2 games, teams with at least 3 wins so far proceed and so on. Now the best team is doing a random walk on Z, with prob of jumping right = 3/4, left = 1/4. Prob that this random walk ever goes below 0 is at most 1/3, so (assuming this ends in O(N) games) the best team wins with prob at least 2/3.
ReplyDelete