## 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.