Hats !

A group of n people meet, and agree to play as a team in a game whose rules are explained to them. They are then allowed to discuss strategy. After the strategy session, an adversary puts red or blue hats on everyone's head; from this point on, no communication is allowed between the players. Each person can see the color of all hats but their own. After exactly one minute, the players simultaneously predict their hat color by sending email saying either "my hat is red" or "my hat is blue." The team wins if the n emailed statements are either all true or all false.

Devise a strategy that guarantees that the team wins, no matter how the adversary chooses to place the hats.

(extra credit) Consider the same situation, except that the goal of the group is to maximize the number of correct answers, assuming that the adversary knows exactly what strategy every member of the group is using. If each member of the group guesses red or blue with equal probability (1/2), then the expected number of correct answers will be n/2, no matter how the adversary arranges the hats. Is there a strategy (either deterministic or randomized) that does better than n/2?

Knight's win

Two knights start on a chess board at opposite corners.

Call them A and B. When A makes a move in a particular cell of the chess board, that cell is marked with A. Same is true with B. A can not move to a cell already marked by B and B can not move to a cell already marked by A. The one marking the most cells wins - Lets say - A wins - He can often trap B into a situation where he can not move to any of the cells which are already marked by A.

Two questions - Is that possible ?
If possible what is the strategy for A to win this ?

Who is the last man standing ?

1000 men are standing in a circle. All of them are numbered from 1 to 1000. I give a sword to the first man. He kills the one standing next to him (numbered 2) and hands over the sword to the man numbered 3. He in turn kills the one numbered 4 and hands it over to the one numbered 5 and so on. This killing cycle goes on and on until the last man standing.

1) Who is the last man standing ?

2) Generalize this with a formula to find the last man standing given a finite number of men starting the killing cycles.

Break the jars

There are 27 floors in a building and you have been given three jars. You have to find from which floor the jar will break when dropped. If you start from the bottom most floor and drop the jar and keep raising the height, you will require only one jar, however the maximum attempts you will require can be 27.

Now with three jars you can reduce your attempts easily sacrificing all three of them. The question is - How many attempts are required ?