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?
Morgan
The seoncd one seems pretty easy, unless I’m misunderstanding the rules of the scenario.
Before starting to let the people into the room, tell them the following:
1) the first person in is designated as the Picker
2) the Picker then watches as the subsequent people come into the room
3) if he sees two (or more people) with the same number, he places them together; everyone in that little grouping just calls out the numbers on the others’ hats
4) if he sees two or more hats that, when summed, add up to another number on a different person’s hat, stick them together in a group, indicating which is the “sum” hat and which are the components of it. The “sum” guy calls out the sum of the other hats in the group
Yeah, I guess I didn’t make it clear. The 2nd problem requires that no communication between people can happen. Everyone has time to look at each other’s hats, but you can’t talk or indicate anything to each other in any way.
This problem was posed late in the evening so I haven’t had much of a chance to think about it yet. I hope to get around to it soon though :)
“Hey, how’s it going? I see you have the number 37 on your hat. What else is new?” :-p
First two are okay, but not too tough. I kind of angled the last problem a bit by looking at what information we have and don’t have. The problem is quite constrained — few degrees of freedom makes it easier to get on the right path. I clicked on the right idea rather quickly, but it took longer to work out the exact details.
I’m not going to give you as many hints as Howard did though. He was way way too soft on you guys — he gave me *nothing*!
I actually had an answer for a couple of these, and then realized I can’t read to save my life. So, I am going to sit and stare at this all day some more and blame you for my lack of productivity :p
On #1 there … are there an equal number of red and blue hats?
This is my most commented post on the site by far!
The red/blue hats are assigned randomly to each person, so you can’t assume there is an equal number.
Darn you! I had it down to 99/100 otherwise on #1.
*ponders*
Is there guaranteed to be at least 1 of each color?