What's Your Problem?

The first time I remember asking about another graduate student's research was during a meeting with Bobak on June 25, 2004. It was Bobak's birthday, and my job was to distract him while others were setting up his surprise party. While I still have a copy of Bobak's LaTeXed writeup from that day, it didn't appear that talking to other students about their research would become a common occurrence.

Things changed once we moved into the Wong Center. In fact, during our first year there, Paolo and I developed a habit of sharing interesting technical problems that were coming out of our research on an almost daily basis. While I like to believe this frequent interaction led us to solutions faster, the real reason I did it was simple. Another person's problems offered me a welcome break from my routine, especially on days when I wasn't gaining any traction on my own problems.

As student interaction became more common, conversations started to shift away from research into areas that ranged from politics to musical preferences. While sharing our problems has declined (at least of the research variety), brain teasers have been on the rise. Many of these have been initiated by Prasad, so I thought I'd share a personal favorite from his collection.

Alice and Bob each roll a six-sided die. Each of them can only see the outcome of the other's roll. Without communicating with one another, Alice and Bob will each win a dollar if both of them correctly guess the outcome of their own rolls. If either Alice or Bob guesses incorrectly, neither wins anything. Is there a way for them to win with a probability of at least 1/6? The answer is yes, which they do by guessing the other person's die roll as their own. Note that if each of them simply guessed at random without looking at the other person's die, they would only win with probability 1/36.

Now suppose 1000 people each roll a six-sided die and observe the outcome of everyone else's roll. Without communicating with one another, they each win a dollar if all of them correctly guess the outcome of their own rolls. If any of them guesses incorrectly, none of them wins anything. Is there a way for them to win with a probability of at least 1/6?