Game of NIM

Two people play a game of NIM. There are 100 matches on a table, and the players take turns picking 1 to 5 sticks at a time. The person who takes the last stick wins the game. Who has a winning strategy?

The first person has a winning strategy. First, he takes 4 sticks. Then every time the second player takes X sticks, the first player takes 6 – X sticks.

Short Friends

Two very short friends, John and Jack, were living together in an apartment. Since they used to lose their apartment key very often, they decided to leave it on top of the door frame when they leave home. In order to reach the key, John was climbing on Jack’s shoulders and thus taking it down from the frame. However, John was the taller and the heavier guy of the two. Why didn’t Jack climb on top of his shoulders instead?

The reason is that as being taller, John also had longer arms. If Jack climbed on John’s shoulders, he wouldn’t have reached the key.

FEATURED

Two Monks on a Mountain

Two monks are standing on the two sides of a 2-dimensional mountain, at altitude 0. The mountain can have any number of ups and downs, but never drops under altitude 0. Prove that the monks can climb or descend the mountain at the same time on both sides, always staying at the same altitude, until they meet at the same point.

Coming soon.

Enemies in the Parliament

In a parliament, there are 100 people, and some of these people are enemies with each other. Show that you can split the people into 2 groups so that each person has at least as many enemies in the opposite group as he has in his own.

For each split of the people into 2 groups, compute the animosity level of each person by subtracting the number of enemies in the opposite group from the number of enemies in his own group. Then, split the people into 2 groups so that the total animosity level of all of them is as little as possible. If there is a person, who has more enemies in his own group than the opposite one, then by transferring him to the other group, we will reduce the total animosity level of the people and will get a contradiction.

The Warden and the Three Doors

An evil warden holds you as a prisoner but offers you a chance to escape. There are 3 doors A, B, and C. Two of the doors lead to freedom and the third door leads to lifetime imprisonment, but you do not which door is what type. You are allowed to point to a door and ask the warden a single yes-no question. If you point to a door that leads to freedom, the warden does answer your question truthfully. But if you point to the door that leads to imprisonment, the warden answers your question randomly, saying either “YES” or “NO” by chance. Can you figure out a way to escape the prison?

You can point towards door A and ask whether door B leads to freedom. If the warden says “YES”, then you open door B. It can not lead to imprisonment because this would mean that door A leads to freedom and the warden must have told you the truth. If the warden says “NO”, then you open door C. This is because either the warden lied, and then the imprisonment door is A, or he told you the truth, and then the imprisonment door is B.

Three Doors

Somehow, you end up in a room that has three doors. Behind the first door, there is a deadly poisonous gas. Behind the second door, there are trained assassins with knives. Behind the third door, there are lions that have not eaten in years. Which door would you choose to open?

You should open the door with the lions. If they have not eaten in years, they will be dead already.

Stones on a Chessboard

You place two stones on a chessboard and start moving them one by one, every time shifting a stone to an adjacent cell – left, right, up, or down, without letting the stones at any time occupy the same cell. Is it possible to find such a sequence of moves, that all possible combinations for the position of the stones occur exactly once?

No, such sequence does not exist. Call a position of the stones “matching” if the stones occupy cells of the same color, and “opposite” if the stones occupy cells of opposite colors. If such sequence exists, then the number of matching and opposite positions must differ by at most 1. However, the number of matching positions is 64×31, whereas the number of opposite positions is 64×32, so this is not true.