Mind Games
Here are some fun questions for you! Check back upon occasion to see if we've added more problems!
Tennis
125 male tennis players attended this year’s US Open 2008 Men’s Single Championship. (BTW, Rafael Nadal is the number 1 seed and Roger Federer is seeded number 2 this time.)
All matches of the championship are organized in rounds. In the first round, the players are paired for a match. The winner of a match advances into the next round while the loser exits. Because the number of players is not exactly a power of 2, it is possible that a player is not assigned any opponent in a round and he goes to next round directly; this is called a bye. To be fair, such bye positions are randomly chosen.
Here comes the question: how many matches does the US Championship have in order to decide a champion? Why? (The reason should be as simple as possible! Remember Occam’s razor?)
String Combinatorics
Given an input of a string (such as 12345), how do you do the following?
1) How to generate all of its permutations? (For example, 21345 is one permutation of 12345.) Write a small program to do it.
[Yes, this problem is exponential in terms of the input size (the input size of 12345 is 5) but for small instances, we should still be able to do it.]
2) How do you generate one (just one) random permutation of the input? By random, I mean uniformly random. Write a small program to do it; prove that the output of your program is really random.