THE PRISONER'S BOXES

You are the janitor at a prison with 100 prisoners locked in separate, soundproof and windowless cells.

You watch one day as the warden brings the prisoners out to a central room where there are 100 boxes laid out, labeled 1 through 100. He hands each prisoner a slip of paper and a pen, and asks everyone to write their name on their slip and hand it back to him. All the prisoner's have different names.

The warden then makes a proposition to the prisoners. He will put them back in their cells and will put each of the 100 slips of paper into a different box. The prisoners will then be brought out one by one in a random order. When a prisoner comes out, he will get to open 50 boxes. He doesn't need to pre-select which boxes he'll open; he can choose as he goes along. He is also not allowed to rearrange the boxes or the names as he does this.

If any of the 50 boxes he opens contains the slip with that prisoner's name on it, then that prisoner "passes" the test. He will be sent back to his cell, all of the boxes will be closed, and the next prisoner will be brought out. However, if any prisoner opens 50 boxes and none of them contain his name, then all 100 prisoners will be executed. Note that prisoners have no way of passing information on to any of the prisoners who go after them.

If all of the prisoners are able to "pass" the test, then they will all be set free, and you'll receive a big promotion.

Luckily for the prisoners, the warden is going to let you help them in the following way. After he's put all of the names in the boxes, he will bring you into the room, let you look at all the names in all the boxes, and then, if you choose to, switch two names with each other. For example, you could switch the names in boxes 35 and 77. You are only allowed to make one switch.

After you help with this task, you will be sent out of the prison and will not be able to communicate with the prisoners.

Before this strange game begins, you get to meet with the prisoners to discuss a strategy. 

This strategy must have two parts:

1. How do you decide which names to switch, if any at all?
2. How does each prisoner decide which 50 boxes he will open?

What plan do you come up with to ensure that the prisoners will all go free?

[[HINT]]>>

     This is a tough riddle. Here are a few hints:

• If you assign each prisoner a different number between 1 and 100, you can correlate each prisoner with one of the 100 boxes in a manner unrelated to the slips of paper. This could help with the prisoners' process for deciding which boxes to open.
• You need to ensure that certain combinations of names/boxes do or do not arise as the warden puts the slips in the boxes in order to make sure that the prisoners' box-choosing strategy works. You can do this with your switch (if you choose to make one).]]

SOLUTION: 

To start with, assign each prisoner a different number between 1 and 100. Every prisoner should remember every other prisoner's number.

Don't think of names any more. Instead of thinking of each box as having a prisoner's name in it, think of it as having that prisoner's number in it. In fact, let's pretend that in addition to their name, each prisoner also wrote their own number on their piece of paper. This is a useful abstraction as we go forward.

If you open a box and look at the number inside of it, you can think of that as pointing you to another box. For example, if you opened box 61 and it had a the number 9 inside of it, then that would be pointing you to box 9. We can say that "box 61 is pointing to box 9." You could then open box 9, look at the number inside, and it would point you to another box.

So box A might point to box B, which might point to box C, which might point to box D, and so on. We see a sort of chain forming. It is guaranteed that eventually, one of the boxes in this chain will point back to A, forming a sort of chain loop.

This means, for example, that if you open box 61, then open the box that it points to, then open the box that that points to, and so on, you are guaranteed to eventually get to a box with the number 61 inside of it.

Now that we have these concepts, let's present a strategy for the prisoners choosing their 50 boxes. Each prisoner first opens the box with his number on it. Then, he open the box which that box points to, then to the box which that box points to, and so on, until he opens the box with his number (name) in it. We've already shown that it is guaranteed that the prisoner will eventually get to a box with his number in it if he starts on the box with his number on it; now we just need to find a way to guarantee that every prisoner will have to open at most 50 boxes before he gets to his number. This is where you come in with your switch.

Remember that all of these chains of boxes pointing to each other are actually loops. For example, if box 71 points to box 3, box 3 points to box 98, and box 98 points back to box 71, then this would be a loop containing 3 boxes. Or if box 44 had the number 44 in it, it would point to itself and be a loop of length 1. Every box is part of one loop, and one loop only.

Given this fact, it turns out that the number of boxes a prisoner will have to open is exactly equal to the number of boxes in his loop (by "his loop", we mean the loop containing his number). This is because he'll start with the box with his number on it, and end with the box with his number IN it, which is the box at the end of the loop since it points back to the starting box.

So if we can ensure that there are no loops longer than 50 boxes, then we've guaranteed that no prisoner will have to look through more than 50 boxes to find his number. Alternatively, if there are any loops of length 51 or longer when the prisoners start picking boxes, then they are guaranteed to lose.

There can be at most 1 loop among the 100 boxes that contains more than 50 boxes (if there was more than one loop with 51 or more boxes, this would mean there would have to be at least 102 boxes, which there are not). If there is no such long loop, then you don't need to switch any boxes. However, if there is such a loop, it's easy for you to break it up into two smaller loops using your switch. To do this, simply pick two boxes that are at opposite sides of the loop, and switch the numbers in them.

Let's go through a quick example on a smaller loop of size six. Let's say that Box 1 points to Box 2, which points to Box 3, which points to Box 4, which points to Box 5, which points to Box 6, which points back to Box 1. If you switch the contents of Box 3 and Box 6 (which are on opposite each other in the loop), then we'll now have two rings of size 3 (Box 1 points to Box 2, which points to Box 3, which newly points to Box 1. And Box 4 points to Box 5, which points to Box 6, which newly points to Box 4).

So, we are able to turn this long loop into two smaller loops of half the size, which are each guaranteed to each contain 50 or fewer boxes. Now we can be sure there are no loops that contain more than 50 boxes, and so when the prisoners follow their box-choosing strategy, they are guaranteed to open the boxes with their own numbers (names) in them.

Please share your views>>

PRISONERS AND A LIGHT-BULB

There is a prison with 100 prisoners, each in separate cells, which are sealed off, soundproof and windowless. There is a lobby in the prison with a light-bulb in it. Each day, the warden will pick one of the prisoners at random (even if they have been picked before) and take them out to the lobby. The prisoner will have the choice to flip the light-bulb switch if they want. The light-bulb starts in the "off" position.

When a prisoner is brought out to the lobby, he also has the option of saying "Every other prisoner has been brought out to the lobby." If a prisoner chooses to say this and it is true, all the prisoners will go free. However, if a prisoner chooses to say this and it's wrong, all the prisoners will be executed. So a prisoner should only say this if he knows it is true for sure.

Before the first day of this process begins, all the prisoners are allowed to get together to discuss a strategy to eventually save themselves.

What strategy could they use to ensure their eventual salvation?

(HINT: Try appointing a "lead" prisoner who has a different role than the rest of the prisoners.)

SOLUTION:

Make one of the prisoners the "lead" prisoner. This prisoner is the ONLY one who is allowed to turn the light off.

Each time any of the other prisoners goes into the lobby, if the light is off, they will turn the light on, but only if they've never turned it on before. This means that each prisoner will only ever turn the light on once.

Meanwhile, every time the lead prisoner goes into the lobby, he will turn the light off if it's on. He will keep track of the number of times he has turned the light off.

Once the lead prisoner turns off the light for the 99th time, he knows that every other prisoner has turned the light on once (and thus has been in the lobby). At this point, he may say that all the prisoners have been to the lobby, and they will all go free.

Please share your views >>

RIDDLE : ANY FIVE CARDS

He looks over the 5 cards you chose, takes one of them, and hands it back to you.

"That going to be your card," he says. He asks you to put it in your pocket out of sight.

He then takes the four remaining cards and arranges them in a stack in a special order. All four cards in the stack are face-down.

He hands you the stack of four cards and asks you to place them on the table however you like (as long as you don't change the order). He then calls the assistant back in. The assistant picks up the four cards, looks them over, and promptly tells you what your card is.

Note that the magician did not do anything extra to communicate information to the assistant. The only information the assistant has in figuring out your card is the order of the four cards on the table.

How was the assistant able to figure out your card?

(HINT: Because you picked five cards, it's guaranteed that at least two of those cards have the same suit. What if the magician decided to make one of these cards "your" card?) 

SOLUTION:

There are probably a number of possible solutions to this problem. We present a rather elegant one.

The high-level strategy the magician uses is as follows: 

He uses the suit of the top card in the stack of four to indicate the suit of your card. 

He uses the value of this top card, along with the ordering of the other 3 cards in the stack, to indicate the numeric value of your card.

Here are the specific details:

1. Picking "your" card

First, the magician looks at the five cards you handed him. It is guaranteed that at least two of these cards have the same suit since there are only four suits total. So he takes two cards having the same suit from the stack (it's fine if more than two cards have this suit, and it doesn't matter which two he chooses). Call these cards A and B. One of these two will be "your" card. He decides which one using the following method:

1. He imagines the numbers 1 through 13 as numbers on a strange wall clock, evenly spaced along the circumference (like a normal clock)
2. With Jack=11, Queen=12, and King=13, he circles the values of cards A and B on the "clock"
3. He measures the number of clockwise unit from A to B, and then does the same from B to A.
4. For whichever distance is shorter (let's call this distance the "shorter clockwise distance"), he looks at the second number, takes the corresponding card (A or B), and makes it "your" card.

For example, if the two cards are a 3 and a Jack, then there are 8 clockwise units from the 3 to the Jack (4, 5, 6, 7, 8, 9, 10, 11), but only 5 units from the Jack to the 3 (12, 13, 1, 2, 3). For this shorter distance, the second card is the 3, and so he would make the 3 "your" card. Notice that in this case, the "shorter clockwise distance" is 5.

He will place the other card (the one he didn't make "your" card) on the top of the stack of four that he hands to his assistant.

2. Ordering the other cards

The second part of the magician's strategy is to use the remaining three cards to convey the "shorter clockwise distance" to his assistant. Then the assistant will simply need to look at the top card and add the "shorter clockwise distance" to the value of this top card, and it will give him the value of your card.

A key observation here is that the "shorter clockwise distance" can never be greater than 6. This is because if the clockwise distance from A to B is greater than 6, then the clockwise distance from B to A is less than or equal to 6 (and is thus the "shorter clockwise distance"). Also, the "shorter clockwise distance" can never be less than 1. So this distance is always either 1, 2, 3, 4, 5, or 6.

So the magician needs to order the final 3 cards in the stack to convey a number between 1 and 6 to his assistant. This is easy to do. He and his assistant have already decided on an ordering on all the cards in the deck (Ace is lowest, King is highest, ties are broken by some order of suits, let's say Hearts < Diamonds < Spades < Clubs).

The magician and the assistant have mapped the following orderings of the final 3 cards to the numbers 1 - 6 as follows:

• Lowest, Middle, Highest : 1
• Lowest, Highest, Middle : 2
• Middle, Lowest, Highest : 3
• Middle, Highest, Lowest : 4
• Highest, Lowest, Middle : 5
• Highest, Middle, Lowest : 6

So if the "shorter clockwise distance" was 5, and the remaining three cards were 2-hearts, 2-diamonds, and Queen-clubs, then he would order them [Queen-clubs, 2-hearts, 2-diamonds] (Highest, Lowest, Middle) to convey the number 5.

That's it. 

The assistant comes in and looks at the top card in the stack of four. This tells him the suit. He then looks at the ordering of the next 3 cards and determines the "shorter clockwise distance". He adds this distance to the value of the top card (wrapping around at 13 if necessary), which gives him the value of your card. So he has the suit and the value of your card, which is to say, he knows what your card is.

Please share your views >>

RANDOM AIRPLAIN SEATS                                           

People are waiting in line to board a 100-seat airplane. Ashish is the first person in the line. He gets on the plane but suddenly can't remember what his seat number is, so he picks a seat at random. After that, each person who gets on the plane sits in their assigned seat if it's available, otherwise they will choose an open seat at random to sit in.

The flight is full and you are last in line. 

What is the probability that you get to sit in your assigned seat?

                                         HINT: 

You don't need to use complex math to solve this riddle.

Consider these two questions

What happens if somebody sits in your seat?

What happens if somebody sits in Ashish's assigned seat?

Solution:

There is a 1/2 chance that you'll get to sit in your assigned seat.

A common way to try to solve this riddle is to try to mathematically determine the chance that each person sits in your seat as they get on the plane. However, this math gets complicated quickly, and we can solve this riddle with a more analytical approach.

We first make two observations:

1. If any of the first 99 people sit in your seat, you WILL NOT get to sit in

     your own seat.

2. If any of the first 99 people sit in Ashish's seat, you WILL get to sit in

     your seat.

To see why, let's say, for the sake of example, that Ashish sat in A's seat, then A sat in B's seat, then B sat in C's seat, and finally, C was the person who sat in Ashish's seat.

We can see that this forms a sort of loop in which every person who didn't sit in their own seat is actually sitting in the seat of the next person in the loop. This loop will always be formed when a person finally sits in Ashish's seat (and if Ashish sits in his own seat, we would consider this to be a loop of length 1), and so after that point, everybody gets to sit in their own seat.

Based on these observations, we know that the instant that a passenger sits in either Ashish's seat or your seat, the game for you is "over", and it is fully decided if you will be sitting in your seat or not.

Our final observation is that for each of the first 99 people, it is EQUALLY LIKELY that they will sit in Ashish's seat or your seat.

For example, consider Ashish himself. There is a 1/100 chance that he will sit in his own seat, and a 1/100 chance that he'll sit in your seat. Consider any other person who has been displaced from their own seat and thus must choose a seat at random...if there are N seats left, then there is a 1/N chance that they'll sit in Ashish's seat, and a 1/N chance that they'll sit in your seat.

So, because there is always an equal chance of a person sitting in your seat or Ashish's seat (and one of these situations is guaranteed to happen within the first 99 people), then there is an equal chance that you will or will not get your seat.

So the chance you get to sit in your seat is 50%.

Please share your views >>