# Puzzles

These are little logic puzzles. They are difficult when you see them the first time. They have simple solutions, which will be found by someone with effective thinking habits, although, I stress this again, not as quickly as you might expect if you read the hints.

### Christmas hats

[Google interview question mentioned on a forum]One hundred people enter a room one by one. When they enter, each is
given a red or green hat, and they can't see it. Moreover they are not
allowed to turn so they can't see the color of the hats of people
that enter later. They do see the hats of people that are already in
the room when they enter. So the last person sees 99 hats, the second
to last sees 98 hats and so on. The first person to enter sees no hat.
The *n*th person to enter sees the *n-1* hats of the persons
already in the room.

Now each person says a word: `red' or `green'. If the color matches his or her's hat the group gets a point. The total score the group is the total number of people that guessed correctly the color of their hat. They are allowed to speak in any order they wish. They are also told beforehand what the game is and they are allowed to come up with a strategy.

Can you find a strategy that maximizes the number of guaranteed correct answers?

### Friendship

[van Lint and Wilson]Prove that in a group of people there are two with the same number of friends. (Friendship is symmetric.)

### Chocolate bar

[Henry's Algorithmic Problem Solving course at UCD]The following game is played between two players with a chocolate. The player to move splits the chocolate in two pieces (along a vertical or horizontal) and eats one of them. You start this game with a 5 by 8 squares chocolate which has a poisoned bottom-down square. Find a strategy to stay alive.

### Chessboard

[classic]You cut the bottom-left and top-right squares of a chessboard. Your job is to cover the rest with dominos or show that it is impossible. A domino is a piece of size 2 by 1 (which can cover two squares).

### Touristic tour

[classic]You are in a foreign city; you would like to visit all of its streets... exactly once. What condition should the road system satisfy so that you can do what you want?

# Hints

- Let's say red=0 and green=1 (because it's longer). The first person to speak is the last one that entered the room and he gives the sum modulo 2 of the seen hats.
- Let's say there are N people. The number of friends one might have is 0, 1, 2, ..., N-1. Look at 0 and N-1.
- Keep it square.
- Each domino covers one white and one black square.
- Connected and even.

Last updated: 8 June 2007