The qual is finally done!

I had my qual exams this Thursday and Friday. According to the qual web site, normally the qual has 8 questions on it, and a passing score requires "nearly perfect" answers to about 3 of the questions and partial answers to 3 more. This time there were 10 questions on the qual, and I was able to get complete answers to 5 of them and partial answers to 4 more of them. So I think I passed, though I won't know for sure until the results come in, probably next week.

One thing that this does mean for the blog is that you will get to see more of my "Gaming Math" problems. The main reason I haven't been able to put up more of those problems recently is not because I haven't played any games with interesting math or computer science problems in them, but rather because most of the time I can't actually solve the problems I come up with. But preparing for the qual has helped me get better at solving those kinds of problems so that means that you will see more of them.

Here is a problem:

Gaming Math - Problem 15: "For Science!"

In the board game "Battlestations," players control crew members aboard a spacecraft, and they are sent on dangerous missions. In one of the missions, the players are trapped in a region of space containing N wormholes, and the only way to get out is to go through the wormholes in a specified sequence. The only way of finding out what that sequence is is by using the ship's Science Bay, which allows the player to ask any yes-or-no question about the sequence.

1. In the scenario described in the game, N=4. What is the minimum number of questions required to guarantee figuring out the correct sequence?
2. For an arbitrary N, what is the minimum number of questions required? Find an algorithm that achieves this minimum number, and prove its optimality.

(Hint: Don't forget that you can ask any yes-or-no question about the sequence.)

The answer is here.