Wednesday, February 16, 2011
Fairness in Carpooling
Comparing Information Without Leaking It
Ron and Moshe would like to determine whether the same person has complained to each of them, but, if there are two complainers, Ron and Moshe want to give no information to each other about their identities.
The protocol typically used in a situation like this one is akin to the game ``twenty questions,'' but goes by the name of ``delicate conversational probing.'' Ron might ask Moshe if Moshe's complainer is male, and if the answer is ``yes'' Moshe might then ask Ron if Ron's complainer's surname begins with a letter preceding ``M'' in the alphabet. This goes on until Ron and Moshe have ascertained whether they have the same person in mind. When they do not, however (particularly when the first ``no'' occurs late in the game) a great deal of information may have been exchanged.
What can Ron and Moshe do in order not leak more information than necessary?
Nuts & Bolts
The "media power" riddle or the importance of being well-connected
In each node of a simple unweighted n-node graph G there lives a citizen. Tomorrow morning, the citizens of G are about to vote "Yes/No" on a critical and highly controversial proposition whose details I could never really figure out.
Out of curiosity and boredom, each citizen of G spends the afternoon amusing himself by conducting a private poll among his neighbors (including himself), in order to get a sense of the outcome of this all-important election. The alarming and disappointing result found by each "Yes" voter is an astounding 3:1 majority for the "No" voters in his neighborhood.
Should the "Yes" voters be worried?! Should the "No" voters rejoice?! Can all these polls lie?? In short: What can be said with certainty about the minimum guaranteed number of "No" voters in tomorrow's election, given these poll results?
2nd variant:
The result of a 3:1 majority for the "No" voters in the neighborhood, was found by EACH and EVERY voter (not just the "Yes" voting ones).
What can be guaranteed now about the minimum number of "No" voters in the election?
3rd variant:
In order to strengthen the validity of the polls, each citizen performs his poll among all citizens in distance up to 4 from himself. Alas, the poll results remain the same.
What can be deduced now, in both previous cases?
Applied Kid Cryptography
Our story involves two characters; for the sake of anonymity and following a long cryptographic tradition we shall call them Alice and Bob. One day, while Alice and Bob were playing ``Where's Waldo?'', Alice suddenly claimed: ``I know where Waldo is!''. Bob responded with a baffling riddle: ``Alice, do you know what a liar is?''. Worried about her reputation (both as an honest person and as a qualified cryptographer), Alice wondered: ``How can I prove to Bob that I know where Waldo is without revealing his location?''
Can you help Alice and propose a simple solution that does not require complex computation and is low-tech in terms of the required resources?
Amazing telepathetic Tachman Family.
The chief mathematician in FEXI proposed the following experiment. It is performed with a deck of six cards. One card has the symbol X on it, two cards have the symbol Y , and three cards have the symbol Z . The three children are placed in different rooms. Each child is given one of the cards with the symbol Z on it. The other three cards are shuffled and then each child gets one of them (face down). Each child inspects this second card that he receives, and can either return it, or return the Z card (face down). The three cards that are returned are shuffled, and then inspected. If they contain all three symbols, X , Y , and Z , then the children win. Otherwise, they fail.
The mathematician argued that if the children have no telepathic skills, they win with probability at most 2/3 . A child that receives X must return X (otherwise, no X is returned). A child that receives Y has two possible strategies: either to return Y or to return Z . Since each child must base his decision of which card to return only on the card that he receives (he sees no other card), then he must associate himself with exactly one of the two strategies. Since there are three children and only two possible strategies, at least two children share the same strategy. With probability 1/3, both these children will receive a Y card. If this event happens, they both return the same type of card, causing failure.
The mathematician also argued that if at least one child is telepathic, the children need never fail. The telepathic child need not base his strategy only on the card that it sees, but can base it also on the cards that the other children see and return. Using this information, and assuming that each of the other children employs a different strategy, it is always possible to ensure that three different symbols will be returned (by a simple case analysis). Moreover, since the cards are shuffled both before they are dealt, and after they are returned, symmetry arguments show that there is no way of telling who the telepathic child is.
Mr. Tachman praised the mathematician on the wise design, and agreed that his family take part in the experiment. The staff at FEXI was concerned that even without telepathy, the children have probability greater than 1/2 of success. However, the mathematician assured them that the experiment can be repeated in order to build up the confidence in the results. Even if the children succeed in the first experiment, there still is probability 1/3 of failing in the next experiment. If the experiment is repeated 100 times, then the probability of success in all experiments is at most (2/3)^{100} , which is astronomically small. The mathematician was willing to stake his job on his conviction that an event of such low probability will not happen.
For the experiment, FEXI employees prepared hundreds of decks, each containing six cards, as instructed by the mathematician. With the first two deck of cards, the children won, and Mr. Tachman was very pleased. On the third deck, they failed, but Mr. Tachman said that this is due to excitement and pressure. After ten decks were played the children won seven times, and failed on three. Mr. Tachman commented that the children are doing very well. The mathematician disagreed, and said that seven out of ten for this experiment is what one would expect to get by chance. Mr. Tachman said that not being a mathematician, he is unable to comment on the mathematics of the experiment. However, knowing the pressure his children are under, 30%-40% failure rate is to be expected. The experiments were stopped. The mathematician said that under current circumstances, a new experiment needs to be designed. This might take a few days. Mr. Tachman got angry, and said that FEXI are sore loosers, and that he only agreed to come for one day. The head of the lab anxiously called everyone to calm down.
After a few minutes, Mr. Tachman proposed the following modified experiment. Instead of using one deck of cards as was done in each execution of the original experiment, use three: a red deck, a blue deck, and a yellow deck. The original experiment will be executed three times in parallel. As in the original experiment, each child receives a red Z card. The other three red cards are shuffled, and each child gets one more red card at random. Then the same procedure is repeated with the blue deck and the yellow deck. Each child can inspect the six cards that it receives, and return one card of each color. The three cards of each color that are returned will be shuffled and inspected. If there are X , Y and Z cards of every color, the children win. Otherwise, they loose. Mr. Tachman explained that in the extended experiment, the children must win with the red deck, and also with the blue deck, and also with the yellow deck. Since each deck is shuffled independently, then the probability of winning simultaneously with all three decks is at most (2/3)^3 < 0.3 , if no telepathy is involved. He was sure that his children would do much better then that.
The first time the extended experiment was executed, the children won with the red deck, but failed with the blue deck and with the yellow deck. Hence the children failed in the extended experiment. Mr. Tachman was annoyed. The second time the extended experiment was executed, the children won with the red deck and with the yellow deck, but failed with the blue deck. Hence despite the improvement, the children still failed in the extended experiment. Mr. Tachman was furious. He said that his children obviously do not understand what they need to do, and called out a five minute break. In this break he gathered up the children, and gave them instructions (in Hebrew). The children returned to their rooms. The next time the extended experiment was executed, the children failed with all three decks. The mathematician asked Mr. Tachman if he wants another break, but Mr. Tachman expressed complete confidence in his children. And for good reasons. The extended experiment was repeated a hundred times. To everyone's amazement (except for Mr. Tachman), the children won 65 times. The mathematician calculated that the probability of having 65 successes out of a hundred, when the probability of an individual success is 0.3, is bellow one in a million. The Tachman family were the clear winners of the day.
A report on this experiment was prepared by the lab. However, the report was never published, and the mathematician was fired. Can you see why?
Any relation between the first name of the author and the first name of Uri Geller is a coincidence.
The Circular Lake
A swan sits at the center of a perfectly circular lake. At an edge of the lake stands a ravenous monster waiting to devour the swan. The monster can not enter the water, but it will run around the circumference of the lake to try to catch the swan as soon as it reaches the shore. The monster moves at 4 times the speed of the swan, and it will always move in the direction along the shore that brings it closer to the swan the quickest. Both the swan and the the monster can change directions in an instant.
The swan knows that if it can reach the lake's shore without the monster right on top of it, it can instantly escape into the surrounding forest.
How can the swan succesfully escape?
Twelve Balls, One Different
You have twelve balls, identical in every way except that one of them weighs slightly less or more than the balls.
You have a balance scale, and are allowed to do 3 weighings to determine which ball has the different weight, and whether the ball weighs more or less than the other balls.
What process would you use to weigh the balls in order to figure out which ball weighs a different amount, and whether it weighs more or less than the other balls?
Coins on a Table
Your friend pulls out a perfectly circular table and a sack of quarters, and proposes a game.
"We'll take turns putting a quarter on the table," he says. "Each quarter must lay flat on the table, and cannot sit on top of any other quarters. The last person to successfully put a quarter on the table wins."
He gives you the choice to go first or second. What should you do, and what should your strategy be to win?
Flipping Lockers
There are 1 million closed school lockers in a row, labeled 1 through 1,000,000.
You first go through and flip every locker open.
Then you go through and flip every other locker (locker 2, 4, 6, etc...). When you're done, all the even-numbered lockers are closed.
You then go through and flip every third locker (3, 6, 9, etc...). "Flipping" mean you open it if it's closed, and close it if it's open. For example, as you go through this time, you close locker 3 (because it was still open after the previous run through), but you open locker 6, since you had closed it in the previous run through.
Then you go through and flip every fourth locker (4, 8, 12, etc...), then every fifth locker (5, 10, 15, etc...), then every sixth locker (6, 12, 18, etc...) and so on. At the end, you're going through and flipping every 999,998th locker (which is just locker 999,998), then every 999,999th locker (which is just locker 999,999), and finally, every 1,000,000th locker (which is just locker 1,000,000).
At the end of this, is locker 1,000,000 open or closed?
Dropping Eggs from a Building
You stand before a 100-story building with two eggs. Using only these two eggs, you must figure out the highest floor from which you can drop an egg such that the egg won't break when it hits the ground (we'll call this the "highest safe floor"). Every floor is equally likely to be the highest safe floor, including the top floor, and it's also just as likely that the egg will break from every floor. You can assume that if you drop an egg and it doesn't break, its shell is just as strong as it was before you dropped it.
If you want to minimize the expected number of drops you have to perform, what strategy should you use for picking which floors to drop the eggs from? You should write a program to solve this problem.
Prisoners and a Lightbulb
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 lightbulb 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 lightbulb switch if they want. The lightbulb 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?
The King and his Hats
The King calls in three wise men and tells them to all close their eyes. While their eyes are closed, he goes around and puts a hat on each of them.
"I put a blue or white hat on each of you," the King says. "I won't tell you what color each hat is, but I promise you that at least one of you has a blue hat."
"Now open your eyes," he continues. "You may not communicate with each other at all. Within one hour, one of you must call out the color of your own hat. If you aren't able to do this, or if anyone calls out the wrong color, I will have you all exiled from the kingdom."
The wise men open their eyes and look at the other mens' hats. They stand there for almost the whole hour in silence, thinking. Just as time is about to run out, all three men figure out the color of their own hats and yell the colors out at the same time.
You can assume that all three men are perfect logicians, that they know that the others are perfect logicians, and that they all think at the same speed.
What colors are the three men's hats?
Robots on a Line
Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points.
You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions:
- Go left one space
- Go right one space
- Skip the next instruction if there is oil in my current spot
- Go to a label
A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right.
Same Number of Handshakes
At a dinner party, many of the guests exchange greetings by shaking hands with each other while they wait for the host to finish cooking.
After all this handshaking, the host, who didn't take part in or see any of the handshaking, gets everybody's attention and says: "I know for a fact that at least two people at this party shook the same number of other people's hands."
How could the host know this? Note that nobody shakes his or her own hand.
Paying With Rings
A man comes to a small hotel where he wishes to stay for 7 nights. He reaches into his pockets and realizes that he has no money, and the only item he has to offer is a gold chain, which consists of 7 rings connected in a row (not in a loop).
The hotel proprietor tells the man that it will cost 1 ring per night, which will add up to all 7 rings for the 7 nights.
"Ok," the man says. "I'll give you all 7 rings right now to pre-pay for my stay."
"No," the proprietor says. "I don't like to be in other people's debt, so I cannot accept all the rings up front."
"Alright," the man responds. "I'll wait until after the seventh night, and then give you all of the rings."
"No," the proprietor says again. "I don't like to ever be owed anything. You'll need to make sure you've paid me the exact correct amount after each night."
The man thinks for a minute, and then says "I'll just cut each of my rings off of the chain, and then give you one each night."
"I do not want cut rings," the proprietor says. "However, I'm willing to let you cut one of the rings if you must."
The man thinks for a few minutes and then figures out a way to abide by the proprietor's rules and stay the 7 nights in the hotel. What is his plan?
Suitcase Locks
A man needs to send important documents to his friend across the country. He buys a suitcase to put the documents in, but he has a problem: the mail system in his country is very corrupt, and he knows that if he doesn't lock the suitcase, it will be opened by the post office and his documents will be stolen before they reach his friend.
There are lock stores across the country that sell locks with keys. The only problem is that if he locks the suitcase, he has no way to send the key to his friend so that the friend will be able to open the lock: if he doesn't send the key, then the friend can't open the lock, and if he puts the key in the suitcase, then the friend won't be able to get to the key.
The suitcase is designed so that any number of locks can be put on it, but the man figures that putting more than one lock on the suitcase will only compound the problem.
After a few days, however, he figures out how to safely send the documents. He calls his friend who he's sending the documents to and explains the plan.
What is the man's plan?
Quick Bridge-Crossing
Four people come to an old bridge in the middle of the night. The bridge is rickety and can only support 2 people at a time. The people have one flashlight, which needs to be held by any group crossing the bridge because of how dark it is.
Each person can cross the bridge at a different rate: one person takes 1 minute, one person takes 2 minutes, one takes 5 minutes, and the one person takes 10 minutes. If two people are crossing the bridge together, it will take both of them the time that it takes the slower person to cross.
Unfortunately, there are only 17 minutes worth of batteries left in the flashlight. How can the four travellers cross the bridge before time runs out?
Ants on a Board
There are 100 ants on a board that is 1 meter long, each facing either left or right and walking at a pace of 1 meter per minute.
The board is so narrow that the ants cannot pass each other; when two ants walk into each other, they each instantly turn around and continue walking in the opposite direction. When an ant reaches the end of the board, it falls off the edge.
From the moment the ants start walking, what is the longest amount of time that could pass before all the ants have fallen off the plank? You can assume that each ant has infinitely small length.
The Prisoners' 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 preselect 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:
- How do you decide which names to switch, if any at all?
- 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?
Prisoners and a Lightbulb
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 lightbulb 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 lightbulb switch if they want. The lightbulb 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?
The Hat Guessing Game
Three kids, Writey, Fruity, and Spicy, are standing around. Their friend, Bob, proposes a challenge. The three kids will close their eyes, and Bob will go around and put one of two hats on each of them, as follows:
- On Writey, Bob will put a hat with a picture of either a pencil or a pen
- On Fruity, Bob will put a hat with a picture of either an apple or an orange
- On Spicy, Bob will put a hat with a picture of either a salt-shaker or a pepper-shaker
Bob will pick the hat to put on each kid completely randomly (50% chance of either hat). Then, the kids will open their eyes. At this point, each kid will be able to see the hats of the other two kids, but won't be able to see his own hat. The kids cannot give each other ANY indication about what is on the other kids' hats.
Now, on the count of three, simultaneously, each kid will either say a guess for the picture on their hat, or say 'pass'. Specifically, on the count of three:
- Writey will either say 'pencil', 'pen', or 'pass'
- Fruity will either say 'apple', 'orange', or 'pass'
- Spicy will either say 'salt', 'pepper', or 'pass'
Note that the kids say their guesses (or 'pass') at the exact same time and thus cannot give any information to the other kids. To clarify, the only information that each kid has when saying his guess is the pictures on the other kids' hats.
The kids all win the game if at least one person guesses the item on their own hat correctly, as long as nobody guesses the item on their hat incorrectly. For example, if two of the kids say 'pass' and the third kid guesses his hat item correctly, they all win the game, but if two of the kids guess their hats correctly but the third guesses incorrectly, they lose. If all three kids pass, they also lose.
Before the game starts, the kids are allowed to come up with a strategy in order to try to maximize their chances of winning. Bob notes that it's impossible to guarantee a win every time, and that there are simple strategies to ensure the kids will win 50% of the time (Writey and Fruity could always say 'pass', and Spicy could always say 'salt'...then, since Spicy's hat will have a salt-shaker on it 50% of the time, they'll win 50% of the time). But Bob tells them they can do much better than 50%.
What strategy should they use to substantially increase their chance of winning?
Clock Synchronization
Obviously, you can,t carry either of the clocks up or down the hill! And you have a horse to help you transport yourself. And, the time required for going up the hill is not equal to the time required to go down the hill.
Teacher & Network
Logical puzzle of blue-eyed islanders
An island has 1001 people with assorted eye colours (having different eye colours). No one knows their own eye colour, but can see the eyes of everyone else (rest 1000 people), also they are highly logical people, so if it is possible to derive the eye colour, they will know it. Out of 1001,
- 100 have blue-coloured eyes
- 900 have red-coloured eyes
- 1, the leader has Green-coloured eyes
The rule is that, If a person come to know his own eye colour today, then he will leave the island the next morning. No one ever speaks to anyone or give any hint about the eye colours. The Guru, however, is allowed to speak one sentence in his life-time.
One fine day, the Guru exercised his right to speak, and said:
“I can see some blue-eyed men”
What will be the repercussions of his statement?
Towers of Hanoi
Towers of Hanoi is more than a century old mathematical puzzle (1983 to be precise). It consists of 3 rods (pegs), and n disks (n>=1) of different sizes which can slide onto any rod.Lets mark the pegs as S, D & E for Source, Destination and Extra. Initially all the disks are in the S as shown below:
Our task is to move the entire Stack of Disks from Source, S to Destination, D using the extra peg, E. So the final state should be
But, there are some rules of the game to be obeyed:
- Only one disk can be moved at a time.
- Only the topmost disk can be moved (from any peg).
- A bigger disk cannot be placed on the top of a smaller disk ever in the game.
Number Game
Two players Player-A and Player-B are playing a Number game.
Given 2n Number in random, but linear order. All the numbers are visible and not hidden. Each player picks a number alternatively. A player can only pick it from either end of the list (cannot pick a number from middle of the list).
Player-A gets to pick first, Always. The player who has the maximum total at the end wins the game. How will you make sure that Player-A always wins?Camel and Banana Puzzle
A Camel has to transport 3000 bananas from point A to point B, both 1000km apart. There are few constraints
- There is only one Camel.
- Camel can not carry more than 1000 bananas at one time.
- Camel eats one banana every kilometer when he travels.
What is the maximum number of bananas which can be transported from point-A to point-B.
Solution
A Camel has to transport 3000 bananas from point A to point B, both 1000km apart. There are few constraints
1. There is only one Camel.
2. Camel can not carry more than 1000 bananas at one time.
3. Camel eats one banana every kilometer when he travels.
What is the maximum number of bananas which can be transported from point-A to point-B.
Solution:
First of all, the brute-force approach does not work. if Camel start by picking up the 1000 bananas and try to reach point B, then Camel will eat up all the 1000 bananas on the way and there will be no banana left for the Camel to return to point A.
So we have to take an approach that Camel drop the bananas in between and then return to point A, to pick bananas again.
<---p1---><--------p2-----><-----p3---->
A---------------------------------------->B
-----> ------> -------->
<----- <------
-----> ------>
<-----
----->
Since there are 3000 bananas and camel can only carry 1000 bananas, Camel will have to make 3 trips to carry them all to any point in between.
When bananas are reduced to 2000 then Camel can shift them to another point in 2 trips and when the number of bananas left are <= 1000, then he should not return and only move forward.
In the first part, P1, to shift the bananas by 1Km Camel will have to
1. Move forward with 1000 bananas – Will eat up 1 banana in the way forward
2. Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back
3. Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward
4. Leave 998 banana after 1 km and return with 1 banana - will eat up 1 banana in the way back
5. Will carry the last 1000 bananas from point a and move forward – will eat up 1 banana
Note: After point 5 the camel does not need to return to point A again.
So to shift 3000 bananas by 1km Camel will eat up 5 bananas.
After moving to 200 km the camel would have eaten up 1000 bananas and is now left with 2000 bananas.
Hence the length of part P1 is 200 Km.
Now in the Part P2, the Camel need to do the following to shift the Bananas by 1km.
1. Move forward with 1000 bananas - Will eat up 1 banana in the way forward
2. Leave 998 banana after 1 km and return with 1 banana - will eat up this 1 banana in the way back
3. Pick up the next 1000 bananas and move forward - Will eat up 1 banana in the way forward
Note: After point 3 the camel does not need to return to the starting point of P2.
So to shift 2000 bananas by 1km Camel will eat up 3 bananas.
After moving to 333 km the camel would have eaten up 1000 bananas and is now left with the last 1000 bananas.
The camel will actually be able to cover 333.33 km, I have ignored the decimal part because it will not make a difference in this example.
Hence the length of part P2 is 333 Km.
Now, for the last part, P3, the Camel only has to move forward. He has already covered 533 (200+333) out of 1000 km in Parts P1 & P2. Now he has to cover only 467 km and he has 1000 bananas.
He will eat up 467 bananas on the way forward, and at point B the Camel will be left with only 533 Bananas.
Drunken Passanger
100 Airlines passenger are standing in a queue to board a plane. They each hold a ticket to one of the 100 seats in that flight (n’th passenger in the queue hold the ticket for seat # n). First passenger is drunk, and he picks a random seat and sit on it.
All the other passengers go inside one-by-one and occupy seats according to the below logic
- Each passenger will occupy its own seat, if its seat is not already occupied by another.
- If its seat is occupied by another passenger, He will pick a random seat from the available (vacant) seats.
If you are the 100th passenger, what is the probability that you end up in your allotted seat (seat no. 100)?
Doctor & Pill
Your doctor gives you two bottles with pills. Lets call them Pill-A and Pill-B. The Bottles are of different collours to distinguish Pill-A bottle from Pill-B bottle. The pills are otherwise identical and once out of their bottle, it is not possible to say which is Pill-A and which is Pill-B. You are supposed to take one pill of each type daily.
One day, you open the bottle of Pill-A, and tap one out into your hand. Then you open the bottle of Pill-B and try to do the same, but two Pill-B’s comes out in your hand.
Now you have 3 identical Pills, one of which is Pill-A and Pill-B, But you cannot distinguish one from another. How will you ensure that you take only one Pill-A and one Pill-B?
Horse race puzzle
There are n horses who have a transitive relation in terms of their speed (If A runs faster than B and B runs faster than C => A runs faster than C). We don’t have space to conduct a race of all the n horses. We can at most run 4 horses in a race. At least How many races do we need to have to find the two fastest horses?
The question can be asked in binary mode as well, i.e we can only run two horses at a time. How many comparisons do we need to make?
Or, Replace horses with numbers, There are n numbers from which you want to find the largest and the second largest, at least how many comparisons you need to make?
Wires, Batteries and Lightbulbs
You are standing in a house in the middle of the countryside. There is a small hole in one of the interior walls of the house, through which 100 identical wires are protruding.
From this hole, the wires run underground all the way to a small shed exactly 1 mile away from the house, and are protruding from one of the shed's walls so that they are accessible from inside the shed.
The ends of the wires coming out of the house wall each have a small tag on them, labeled with each number from 1 to 100 (so one of the wires is labeled "1", one is labeled "2", and so on, all the way through "100"). Your task is to label the ends of the wires protruding from the shed wall with the same number as the other end of the wire from the house (so, for example, the wire with its end labeled "47" in the house should have its other end in the shed labeled "47" as well).
To help you label the ends of the wires in the shed, there are an unlimited supply of batteries in the house, and a single lightbulb in the shed. The way it works is that in the house, you can take any two wires and attach them to a single battery. If you then go to the shed and touch those two wires to the lightbulb, it will light up. The lightbulb will only light up if you touch it to two wires that are attached to the same battery. You can use as many of the batteries as you want, but you cannot attach any given wire to more than one battery at a time. Also, you cannot attach more than two wires to a given battery at one time. (Basically, each battery you use will have exactly two wires attached to it). Note that you don't have to attach all of the wires to batteries if you don't want to.
Your goal, starting in the house, is to travel as little distance as possible in order to label all of the wires in the shed.
You tell a few friends about the task at hand.
"That will require you to travel 15 miles!" of of them exclaims.
"Pish posh," yells another. "You'll only have to travel 5 miles!"
"That's nonsense," a third replies. "You can do it in 3 miles!"
Which of your friends is correct? And what strategy would you use to travel that number of miles to label all of the wires in the shed?A Fly In Between Trains
Two trains are traveling toward each other on the same track, each at 60 miles per hour. When they are exactly 120 miles apart, a fly takes off from the front of one of the trains, flying toward the other train at a constant rate of 100 miles per hour. When the fly reaches the other train, it instantly changes directions and starts flying toward the other train, still at 100 miles per hour. It keeps doing this back and forth until the trains finally collide.
If you add up all the distances back and forth that the fly has travelled, how much total distance has the fly travelled when the trains finally collide?
The Missing Dollar
Three people check into a hotel room. The bill is $30 so they each pay $10. After they go to the room, the hotel's cashier realizes that the bill should have only been $25. So he gives $5 to the bellhop and tells him to return the money to the guests. The bellhop notices that $5 can't be split evenly between the three guests, so he keeps $2 for himself and then gives the other $3 to the guests.
Now the guests, with their dollars back, have each paid $9 for a total of $27. And the bellhop has pocketed $2. So there is $27 + $2 = $29 accounted for. But the guests originally paid $30. What happened to the other dollar?
A Fox, A Sheep, and A Sack of Hay
A farmer is travelling with a fox, a sheep and a small sack of hay. He comes to a river with a small boat in it. The boat can only support the farmer and one other animal/item. If the farmer leaves the fox alone with the sheep, the fox will eat the sheep. And if the farmer leaves the sheep alone with the hay, the sheep will eat the hay.
How can the farmer get all three as well as himself safely across the river?
Any Five Cards
You meet a magician and his assistant, who decide to show you a trick.
The assistant leaves the room, and the magician hands you an ordinary deck of 52 cards. He has you choose any 5 cards from the deck and give them to him.
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?
Ten Pirates and their Gold
Ten pirates find a buried treasure of 100 pieces of gold.
The pirates have a strict ranking in their group: Pirate 1 is the lead pirate, Pirate 2 is second-in-command, Pirate 3 is the third most powerful pirate, and so on.
Based on this ranking, the pirates decide on a system to determine how to split up the 100 pieces of gold. The lead pirate (Pirate 1) will propose a way to divy it up. Then all the pirates (including the lead pirate) will vote on that proposal. If 50% or more of the pirates agree on the system, then that is how the gold will be divied up. However, if less than 50% of the pirates vote for the proposal, then the lead pirate will be be killed. The next-most powerful pirate will then become the lead pirate, and they'll restart the process (Pirate 2 will suggest a way to divy up the gold and it will be voted on by the rest of the pirates). This will keep going on until finally a proposal is agreed upon.
All of the pirates are very smart and very greedy. Each pirate will vote against a proposal if they know that they would end up with more gold if that proposal were to fail. A pirate also will never vote for a proposal that gives him 0 pieces of gold.
You are Pirate 1. You must come up with a proposal that will give you as much gold as possible, without getting yourself killed. Keep in mind that the rest of the pirates all know that if your proposal fails, then Pirate 2 will succeed at coming up with a plan that benefits him the most while not getting him killed.
What's your proposal?
Answer
You should keep 96 pieces of gold for yourself, and give 1 piece of gold each to Pirate 3, Pirate 5, Pirate 7, and Pirate 9.
To see why, let's look at the situation where there are only two pirates, and you're the lead pirate. Your proposal would be to give yourself all 100 pieces gold. Pirate 2 would vote against this and you would vote for it, giving you 50% of the vote and letting it pass. And you would get 100 pieces of gold.
What about for 3 pirates, with you as the lead pirate? Well, Pirates 2 and 3 know that if your proposal fails, then they will find themselves in the situation described above for 2 pirates, in which Pirate 2 will get all the gold, and Pirate 3 will get none. Pirate 2 would love this situation, but Pirate 3 would hate it. So you just propose to give Pirate 3 one piece of gold, while giving Pirate 2 no gold. Pirate 2 will vote against this, but Pirate 3 will vote for it because he knows that if this proposal fails, he'll get no gold. So your proposal will pass, you'll get 99 pieces of gold, and Pirate 3 gets 1 piece.
For 4 pirates, the situation is similar again. Pirates 2 and 4 would love your proposal to fail since they know that with only 3 pirates, they'll both get gold, whereas Pirate 3 will get none. So you just give Pirate 3 one piece of gold and keep the other 99 for yourself, and this proposal will hold up with 50% of the votes (from you and Pirate 3).
We can follow this same logic all the way up to 10 pirates, where you give one piece of gold each to Pirates 3, 5, 7, and 9, and keep the rest for yourself. You know these four pirates will support your proposal because they know they'll each get 0 pieces of gold if your proposal fails.
Cards in the Dark
You are standing in a pitch-dark room. A friend walks up and hands you a normal deck of 52 cards. He tells you that 13 of the 52 cards are face-up, the rest are face-down. These face-up cards are distributed randomly throughout the deck.
Your task is to split up the deck into two piles, using all the cards, such that each pile has the same number of face-up cards. The room is pitch-dark, so you can't see the deck as you do this.
How can you accomplish this seemingly impossible task?
Two Threads Are Bruning.?????
You have two lengths of rope. Each rope has the property that if you light it on fire at one end, it will take exactly 60 minutes to burn to the other end. Note that the ropes will not burn at a consistent speed the entire time (for example, it's possible that the first 90% of a rope will burn in 1 minute, and the last 10% will take the additional 59 minutes to burn).
Given these two ropes and a matchbook, can you find a way to measure out exactly 45 minutes?