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 ?

Rubick's Cube and switch Puzzles.

Consider the moves of the Rubick's cube as follows.

R -- Flip the right face in clockwise direction
Ri -- Flip the right face in anticlockwise direction

D -- Flip the down face in clockwise direction
Di -- Flip the down face in anticlockwise direction

F -- Flip the front face in clockwise direction
Fi -- Flip the front face in anticlockwise direction

U -- Flip the up face in clockwise direction
Ui -- Flip the up face in anticlockwise direction

Now consider the topmost, rightmost, and frontmost piece call it piece FTR.
I will do following moves

Ri Di R D - 6 times
R U Ri U R U U Ri - 6 times
U R Ui Li U Ri Ui L - 3 times

What will be the final position of the piece FTR after everything is done.

Four switches can be turned on or off. One is the light switch for the incandescent overhead light in the next room, which is initially off, but you don't know which. The other three switches do nothing. From the room with the switches in it, you can't see whether the light in the next room is turned on or off. You may flip the switches as often and as many times as you like, but once you enter the next room to check on the light, you must be able to say which switch controls the light without flipping the switches any further. (And you can't open the door without entering, either!) How can you determine which switch controls the light?

No retrace and 3 D to 2 D without bridge

Two more puzzles.

I will give you a set of points on a plane and also define the connectivity of all points which are connected with straight lines. There will be certain figures which can not be drawn without lifting the pen or without retracing the path. For example – You can not draw A without lifting the pen or without retracing any part of any line. You have to device a simple algorithm check which should tell this about any complicated figure.

What will the algorithm be?

Hint: While thinking about the solution – think about the counter examples.

Imagine a cube made of wires. This can be represented on a 2-D as given in the figure which follows.

I bridge is defined as in the figure which follows next.

If I connect two opposite points of the cube with a wire, will it be possible to draw that structure on 2D without using a bridge?

Hint: Think this problem as a current resistance problem.

Key Coding

Here are two -

Represent 1 as a summation of repetitive decimals containing either 0 or seven.
Hint : One of them is Bar [0.777777] -- where Bar means the sequence 777777 is repeated indefinitely.

Here is another :

Suppose you have n keys on a circular key chain and wish to put a colored sleeve on each key so that it is identifiable by its color alone, without reference to its shape. For some n this can be done with fewer than n colors. For example, if you have 4 keys then you can place the colors on the keys as follows:

Red
Red Green
Blue

The top key is the red key that is across from the blue key; and the leftmost key is the red key that is adjacent to a blue one; the other two are identifiable by their colors.
An identification scheme must work even if the key chain is flipped over, so one cannot use the words right and left. Let f(n) be the least number of colors necessary so that each key on a chain of n keys can be uniquely identified as explained above. Then f(1) = 1, f(2) = 2,
and f(3) = 3. What is f(123)?

Board to Reverse-Board

Imagine a chess board with 64 squares.

Define a Board :

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32
33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64

Define a Reverse-Board

64	63	62	61	60	59	58	57
56	55	54	53	52	51	50	49
48	47	46	45	44	43	42	41
40	39	38	37	36	35	34	33
32	31	30	29	28	27	26	25
24	23	22	21	20	19	18	17
16	15	14	13	12	11	10	9
8	7	6	5	4	3	2	1

A 'Move' is defined as a horizontal or vertical swap between adjacent cells on the board.

The puzzle is -- How many minimum Moves are required to transform Board to Reverse-Board.