How Many Byes?
If you worked on this problem the hard way, by drawing up actual charts of a tournament for 37 players, you may have noticed that no matter how the chart is drawn there are always just 4 byes. The number of necessary byes is a functionofn, the number of players. How can the number of byes be calculated?
Given n, the number of byes can be determined as follows. Subtract n from the lowest power of 2 that is equal to or greater than n. Express this remainder in binary notation. The number of byes is equal to the number of one s in this binary expression In our case, we subtract37 from 64(which is 26)to get 27. In binary notation27=11011. There are four 1's, therefore the tournamentmust have four byes. It is an interesting exercise to justify this curious algorithm.
The type of tournament described in this problem is often called a"knockout tournament. "It corresponds to what computer scientists call an algorithm for determining the largest element in a set of n elements by comparing them pairwise. As we have seen, exactly n-1 pairwise comparisons are necessary for determing the maximum. Computer sorting can also be done by comparing sets in groups of three, four, five and so on.
If you worked on this problem the hard way, by drawing up actual charts of a tournament for 37 players, you may have noticed that no matter how the chart is drawn there are always just 4 byes. The number of necessary byes is a functionofn, the number of players. How can the number of byes be calculated?
Given n, the number of byes can be determined as follows. Subtract n from the lowest power of 2 that is equal to or greater than n. Express this remainder in binary notation. The number of byes is equal to the number of one s in this binary expression In our case, we subtract37 from 64(which is 26)to get 27. In binary notation27=11011. There are four 1's, therefore the tournamentmust have four byes. It is an interesting exercise to justify this curious algorithm.
The type of tournament described in this problem is often called a"knockout tournament. "It corresponds to what computer scientists call an algorithm for determining the largest element in a set of n elements by comparing them pairwise. As we have seen, exactly n-1 pairwise comparisons are necessary for determing the maximum. Computer sorting can also be done by comparing sets in groups of three, four, five and so on.