Hangin' With Howard Lederer

One thing Diane didn't mention about the games party last Saturday that one of the guests was none other than Howard Lederer. Howard is one of the Full Tilt poker pros. His poker nickname is "the Professor of poker", in part because of his thoughtful approach to the game. He's appeared on television not only as a poker player, but also as a poker analyst on a couple of different shows. My research position at the UofA, and now my job here has put me into a position to meet some pretty big name poker players. With the CPRG, I met Phil Laak, Ali Eslami, Matt Hawrilenko, Bryce Paradis, Ed Miller, and a few others. Now working at Pocket Kings, I've met Howard Lederer, and I understand that several of the Full Tilt pros stop by the office every so often.

Anyways, on Wednesday night, Diane and I headed out to company trivia night at a local pub. People who know me know that I'm not a trivia person, but I wanted to go hang out with fellow company people so that I could get to know people a little more. So we went and had some food and some drinks. Before the trivia started, Howard joined the group. He presented us with several logic problems that were quite interesting and that stumped several of us for quite awhile. Here they are if you'd like to take a crack at them.

  • One hundred people are allowed to come up with a strategy before this scenario. They are then assembled in a line, and each person is given either a red or a blue hat. The person at the back of the line can see all the coloured hats in front of him, but cannot see his own hat. The second last person in the line can see the 98 hats in front of him, but not his own hat nor the hat of the person behind him. Each person, starting with the person at the back of the line, can only say "red" or "blue". If they get the colour of their hat wrong, they will be killed off. If they get it right, they'll survive. Come up with a strategy that will maximize the guaranteed number of survivors.
  • One hundred people are let into a room one at a time, and they are given a hat with a random number on it in the range 1-100. People could potentially get assigned the same number. The players are allowed to walk around the room looking at all the numbers everyone has on their hats, but cannot see the number on their own hat. When everyone is ready, they must simultaneously call out a number. Come up with a strategy for the players such that at least one person is guaranteed to correctly guess the number on their hat.
  • One hundred prisoners are held in a room. One at a time, they are randomly selected and brought into a second room where there are 100 boxes. Each box contains a number that is uniquely attached to one of the prisoners (each prisoner has a unique number, and it is contained in one of the boxes in the room). The person must now choose up to 50 of the boxes to open and check if their number is inside. If they find their number, they get to walk free. If not, they are executed. Come up with a strategy for the prisoners to maximize the likelihood that they ALL walk free.

I've always kind of been interested in these problems, but I've been really bad at them in the past. I've only come up with a solution to the first problem, and haven't managed to figure out and prove solutions to the other two, but I think I shall ponder them for awhile. I'm quite enjoying the mental exercise so far, and I felt pretty proud of myself when I finally solved the first problem this morning.

Can you solve them?