Prisoners again

A jailer devices a game for the prisoners so that he can eliminate them.

Each prisoner goes in a room where there are 100 envelops put on a table in a line. Each envelop has a card with a number between 1-100 such that all envelops combined have all numbers 1-100. The sequence of the numbers in the envelop is random.

Each person is asked to open 50 envelops and see the number written on the card inside the envelop. Each prisoner has been assigned a number between 1-100. If the prisoner's number matches with the number on one of those 50 cards, he is safe. Then, the next prisoner goes in and does the same.

If even one prisoner fails, everyone dies, otherwise everyone is safe.

Devise a strategy - what should each prisoner do so that the probability of their escaping is maximized.

Cards puzzle

I give you 4 cards from a deck of 52 playing cards. You intelligently select 4 out of those 5 and give those to your friend. He analyzes the 4 cards and tells you the fifth one. You have to pre-decide a strategy to do so. The puzzle is – What will the strategy be?

On a higher level - I shuffle 4 decks of cards and then select 6 cards from the shuffled decks. This time you have to do the same with 5 cards. What will the strategy be ?

Encryption- decryption !

The following problem is inspired from quantum encryption.

You are Alice and you want to send a coded message to Bob. The way you will send the message is with up and down arrows or diagonal arrows, shown below.
The way you can generate a message is with zeros and ones. When zeros and ones are passed though these + and X, arrows are generated. The only way the message can be measured is with + and X.

The compatibility of + and X with arrows is such that plus aligns the arrows along its direction and crosses align the arrows along itself, for example as shown in the figure.



If someone intercepts these messages in between and sends them to Bob, the situation will change and number of matchings will differ between Alice and Bob. The question is – How many such arrows need to be send in order for probability of matching exceeding 0.99999 even if someone intercepts in between.

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 ?