# Problems like the handshake problem

I am in college and my RA has been putting up little thought problems on his door for us to see as we pass by, but the ones he puts up aren't too interesting. I wrote up the handshake problem (invite 8 other couples to a party...) and we all had a fun time solving that problem together. So I am wondering what math.SE can tell me in terms of similar problems. Other ones I know of are the prisoners and the warden, and the blue eyed islanders.

-
Here's a particularly tricky one. – icurays1 Nov 22 '12 at 17:49

A classic problem in computer science, attributed to Dijkstra, is the Dining Philosopher's Problem, also described in Wikipedia, which exemplifies the problem of "deadlock".

But it is worth exploring apart from its utility in comp sci, and worth trying to solve by creating the conditions and/or restrictions that will prevent starvation!

Also:

You might want to explore the work of Ian Stewart, and perhaps better yet, Martin Gardner, as both have been prolific in writing and publishing challenging problems and "brain-teasers".

-
Gardner and Ian Stewart are great ideas thanks I had forgotten about them. – Moderat Nov 22 '12 at 18:44
Yes, they provide fun, interesting, and thought provoking problems! – amWhy Nov 22 '12 at 18:54

A difficult one which I found very enjoyable was the following:

A group of people are gathered together to play a game. The rules are explained to them as follows. They will each be given a hat with a positive number on it. It may be any positive number, not necessarily an integer and they will not necessarily be sequential.

Everybody will be allowed to see everybody else's hat, but not their own. At this stage, there is no communication allowed, even implicitly (for example, standing next to the person with the largest number you can see would be disallowed). If this is a sticking point, the problem can be modified so that the players are given their hats separately and only shown photographs of each other player with their hat, so that they are never in communication while wearing that hats.

Once everybody knows the hat number of everyone except themself, each person is taken to a separate room and asked to put on either a white or black shirt. Finally, all of the players will be taken into a large room and made to line up in hat number order (smallest to largest).

The goal of the game is for the players to devise a strategy by which, when they are ordered by hat number, their T-shirt colors will alternate. Given these rules, they are allowed to discuss a strategy (before seeing any hats). What strategy should they use to guarantee a win?

And here's another, simpler one:

You are playing a game with a genie. The genie, being magical, is capable of producing any real number, even ones which are not computable. The game is taken in turns, where each turn the genie will write a number on each of two cards (he can write very small!) and present these cards to you face down.

You can take pick one card and read its value. Then you must bet whether the card you selected has a higher or lower value than the other card.

Other than that the genie will never write the same number on both cards, you know nothing about his procedure for choosing numbers. What should your strategy be to ensure that you have a greater than 50% chance of winning every turn? Assume that you have a computer with a bit of genie magic to allow you to perform whatever mathematical operations you want on the numbers you're given (i.e. don't worry about practical limitations with calculations involving your numbers, random number generation, etc.)

Also if you use the prisoners and warden question (I assume you're referring to the one with the room and the light switch), you can add a bit of trickiness by not specifying whether the switch is initially turned on or off. This is still solvable, but requires a bit of a modification to the solution.

Answers provided on request. If I remember any more, I'll add them here.

-

This one can be described as follows:

If in a group of $12$ people there are at most $16$ pairs of friends then there is at least one pair of people (maybe friends) which don't have a common friend.

or as:

If in a group of $12$ people at most $16$ handshakes are made then there is at least one pair of people which didn't shake hands with a common person.

-