3 switches 1 light puzzle
You have a set of 3 light switches
outside a closed door. One of them controls the light inside the
room. With the door closed from outside the room, you can turn the
light switches on or off as many times as you would like.
You can go into the room - one time only - to see the light. You cannot see the whether the light is on or off from outside the room, nor can you change the light switches while inside the room.
No one else is in the room to help you. The room has no windows.
Based on the information above, how would you determine which of the three light switches controls the light inside the room?
You can go into the room - one time only - to see the light. You cannot see the whether the light is on or off from outside the room, nor can you change the light switches while inside the room.
No one else is in the room to help you. The room has no windows.
Based on the information above, how would you determine which of the three light switches controls the light inside the room?
Answer
First any one of the switch and let it
be on for 10 min and then close on the another switch and go inside
the room if the bulb is lighted then the correct switch is 2 and if
the bulb if not lighted but it is hot (feel it by touching) then it
is the 1st switch otherwise the 3 rd switch .
Five Pirates splitting 100 coins puzzle
5
pirates of different ages have a treasure of 100 gold coins.
On their ship, they decide to split the coins using this scheme:
The oldest pirate proposes how to share the coins, and ALL pirates (including the oldest) vote for or against it.
If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.
As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.
Assuming that all 5 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?
On their ship, they decide to split the coins using this scheme:
The oldest pirate proposes how to share the coins, and ALL pirates (including the oldest) vote for or against it.
If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.
As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.
Assuming that all 5 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?
Answer
:
To
understand the answer,
We
need to reduce this problem to only 2 pirates. So what happens if
there are only 2 pirates. Pirate 2 can easily propose that he gets
all the 100 gold coins. Since he constitutes 50% of the pirates, the
proposal has to be accepted leaving Pirate 1 with nothing.
Now let’s look at 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.
If there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the distribution will be {0, 1, 0, 99}.
Smart right? Now can you figure out the distribution with 5 pirates? Let’s see. Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.
Bonus:
Think about what would happen if there are 15 pirates or 25 pirates.
Post the answer in the comments section.
Three mislabeled jars/bucket problem
Puzzle :
This problem is also called Jelly Beans problem. You have three jars that are all mislabeled. one contains apples, another has grapes, and the third has a mix of both.
Now you are allowed to open any one jar and you can able to see one fruit. [ The jar you are open may contain one fruit or two fruit. but you could able to see only one fruit and you can't find weather the opened jar has one or two fruit]. How could you fix the labels on the jars ?
This problem is also called Jelly Beans problem. You have three jars that are all mislabeled. one contains apples, another has grapes, and the third has a mix of both.
Now you are allowed to open any one jar and you can able to see one fruit. [ The jar you are open may contain one fruit or two fruit. but you could able to see only one fruit and you can't find weather the opened jar has one or two fruit]. How could you fix the labels on the jars ?
You have three jars that are all
mislabeled. one contains peanut butter jelly beans, another grape
jelly jelly beans, and the third has a mix of both (not necessarily a
50/50 mix, could be a 1/99 mix or a 399/22 mix). how many jelly beans
would you have to pull out, and out of which jars, to find out how to
fix the labels on the jars?
| | | | | | |jar 1| |jar 2| |jar 3| | | | | | | ======= ======= ======= p.b. grape p.b./grape
Answer :
1. Need to open Apple+Orange jar. If it has apple. then it should be labeled as Apple. The jar which has label Orange should be labeled as "Apple+Orange" and the last one should be "Orange".
2. You have three jars that are all mislabeled. one contains peanut butter jelly beans, another grape jelly jelly beans, and the third has a mix of both (not necessarily a 50/50 mix, could be a 1/99 mix or a 399/22 mix). how many jelly beans would you have to pull out, and out of which jars, to find out how to fix the labels on the jars?
| | | | | |
|jar 1| |jar 2| |jar 3|
| | | | | |
======= ======= =======
p.b. grape p.b./grape
solution: 1 jelly bean from the p.b./grape jar will do the trick.the trick here is to realize that every jar is mislabeled. therefore you know that the peanut butter jelly bean jar is not the penut butter jelly bean jar, and the same goes for the rest.
you also need to realize that it is the jar labeled p.b./grape, labelled as the mix jar, that is your best hope. if you choose a jelly bean out of there, then you will know whether that jar is peanut butter or grape jelly jelly beans. it can’t be the mix jar because i already said that every jar is mislabeled.
once you know that jar 3 is either peanut butter, or grape jelly, then you know the other jars also. if it is peanut butter, then jar 2 must be mixed because it can’t be grape (as its labelled) and it can’t be peanut butter (that’s jar 3). hence jar 1 is grape.
if jar 3 is grape, then you know jar 1 must be the mix because it can’t be p.b. (as its labelled) and it can’t be grape (that’s jar 3). hence jar 2 is peanut butter.
if you pick jelly beans from jar 1 or jar 2, then you would have to pick out all of the jelly beans before you knew what that jar was. this is because jar 1 and 2 could be the mix, so in order to disprove that they were the mix, you would have to pull out every jelly bean just to make sure (since there could just be one bean of the opposite flavor in there)
Tumblers on a Rotating Table
Tumblers
on a Rotating Table Puzzle :
A blind gnome and an evil
goblin take turns to play a game. Four tumblers are placed at the
corners of a square table. The initial configuration of the tumblers
(facing up or facing down) is chosen by the evil goblin. When the
blind gnome gets his turn, he is allowed to specify a subset of the
four tumblers and flip them simultaneously. To be precise, he may
choose “one tumbler”, “two diagonally opposites”, “two
adjacent”, “three tumblers” or “four tumblers” lying in
front of him, and flip them simultaneously. After flipping, if all
four tumblers are upright, he wins the game! Otherwise, the game
continues and the evil goblin is allowed to rotate the table by an
amount of his choice. Can the blind gnome win the game with a
deterministic strategy?
Solution
:
If there were only two
cards, then “flip both” — “flip one” — “flip both”
would ensure a victory for the blind gnome. For the case of four
cards, let F denote “all four cards”, A denote “two adjacent
cards”, D denote “two diagonally opposite cards”, O denote “one
card”. Then the following 15-step sequence ensures victory for the
blind gnome: F, D, F, A, F, D, F, O, F, D, F, A, F, D, F. The
procedure can be generalized to 2^n cards. This problem is studied in
detail by Ehrenborg and Skinner (see bibliography below); they call
it “The Blind Bartender’s Problem”.
A variant of the above
problem allows the blind gnome to first “touch” any t out of n
tumblers on a polygonal table with n sides. Touching allows the gnome
to deduce which of the t tumblers he touched are upright, and then to
decide which of these t tumblers to flip. It was this variant that
was originally published in Martin Gardner’s article in Feb 1979.
For four tumblers, the blind gnome can win in five moves, as Gardner
showed in his subsequent article in Mar 1979. The problem generated
quite some interest. Two pairs of mathematicians independently proved
that the blind gnome can win with a deterministic strategy if and
only if t ≥ n(p-1)/p where p is the largest prime factor of n
(Lewis and Willard in 1980; Laaser and Ramshaw 1981). These proofs
are quite involved
Four ships Puzzle
Puzzle :
Four ships are sailing on
a 2D planet in four different directions. Each ships traverses a
straight line at constant speed. No two ships are traveling parallel
to each other. Their journeys started at some time in the distant
past. Sometimes, a pair of ships collides. A ship continues its
journey even after a collision. However, it is strong enough only to
survive two collisions; it dies when it collides a third time. The
situation is grim. Five of six possible collisions have already taken
place (no collision involved more than 2 ships) and two ships are out
of commission. What fate awaits the remaining two?
Solution
:
Let z-axis denote time.
let x- and y- axes denote the 2D planet. Then the four trajectories
are straight lines. Since no collision involved more than two ships,
these four lines must all lie in a plane. So, one might be tempted to
believe that the two other ships will also collide. But, they might
have collided in negative time. So, it cannot be decided from the
given information that the two ships will collide or not?
This can be made clearer through the following two diagrams. In the first one, the four ships move such that there is no collision between the two ships. In the other diagram, the four ships move such that there is a collision between them.
This can be made clearer through the following two diagrams. In the first one, the four ships move such that there is no collision between the two ships. In the other diagram, the four ships move such that there is a collision between them.
Engineers and Managers Puzzle
Puzzle :
In a city, The police has surrounded the Bank. There are 50 people in
the building. Each person is either an engineer or a manager of the
bank. All computer files have been deleted, and all documents have
been shredded by the managers. The problem confronting the police is
to separate the people into these two classes, so that all the
managers are locked in a room and all the engineers are freed.
every people knows the status of all others. The interrogation
consists entirely of asking person i if person j is an engineer or a
manager. The engineers always tell the truth. What makes it hard is
that the managers may not tell the truth. In fact, the managers are
evil geniuses who are conspiring to confuse the interrogators.
1. Under the assumption that more than half of the people are engineers, can you find a strategy for the Police to find one engineer with at most 49 questions?
2. Is this possible in any number of questions if half the people are managers?
3. Once an engineer is found, he/she can classify everybody else. Is there a way to classify everybody in fewer questions?
1. Under the assumption that more than half of the people are engineers, can you find a strategy for the Police to find one engineer with at most 49 questions?
2. Is this possible in any number of questions if half the people are managers?
3. Once an engineer is found, he/she can classify everybody else. Is there a way to classify everybody in fewer questions?
Answer :
Part 1:
Here's an n-1 query solution to part 1. Maintain three sets of people: UNSEEN, STACK, and DISCARD. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN. Repeat the following step until UNSEEN is empty:
Pick an UNSEEN element x, remove it from UNSEEN. Ask the top of the STACK y about x. If y says "manager" pop y off the stack and DISCARD both x and y. If it says "engineer" add x to the top of the STACK.
After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer.
Why does this work? First observe that whenever we discard a pair, at least one of them is a manager. So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end, when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.
This can be improved to 48 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer.
first step we can just throw out one person, and appy this algorithm to the remaining 49 obtaining 47 comparisons. This gives the optimal algorithm.
This is optimal. The proof appears in the solution of homework assignment 7 of Steven Rudich's course 15-251 taught at CMU in the spring semester of 2002. See Solution 7.
Part 2: If half or more of the people are managers, then the problem cannot be solved. The managers can ensure this simply by always lying. Now there's way to separate the two sets of people. Each one simply claims the others are Managers.
Part 3: I don't know any better solution than to simply using the solution to Part 1 to identify everybody.
Here's an n-1 query solution to part 1. Maintain three sets of people: UNSEEN, STACK, and DISCARD. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN. Repeat the following step until UNSEEN is empty:
Pick an UNSEEN element x, remove it from UNSEEN. Ask the top of the STACK y about x. If y says "manager" pop y off the stack and DISCARD both x and y. If it says "engineer" add x to the top of the STACK.
After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer.
Why does this work? First observe that whenever we discard a pair, at least one of them is a manager. So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end, when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.
This can be improved to 48 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer.
first step we can just throw out one person, and appy this algorithm to the remaining 49 obtaining 47 comparisons. This gives the optimal algorithm.
This is optimal. The proof appears in the solution of homework assignment 7 of Steven Rudich's course 15-251 taught at CMU in the spring semester of 2002. See Solution 7.
Part 2: If half or more of the people are managers, then the problem cannot be solved. The managers can ensure this simply by always lying. Now there's way to separate the two sets of people. Each one simply claims the others are Managers.
Part 3: I don't know any better solution than to simply using the solution to Part 1 to identify everybody.
MACHINE WEIGHING - COIN Puzzle
Coin Puzzle :
This is another coin puzzle. As per the puzzle you have 20 coin
machines, each of which produce the same kind of coin. you know how
much a coin is supposed to weigh. one of the machines is defective,
in that every coin it produces weighs 1 ounce less than it is
supposed to. you also have an electronic weighing machine. how can
you determine which of the 20 machines is defective with only one
weighing? (by one use, we mean you put a bunch of stuff on the
machine and read a number, and that's it -- you not allowed to
accumulate weight onto the machine and watch the numbers ascend,
because that's just like multiple weighings). you are allowed to
crank out as many coins from each machine as you like.
This puzzle is like another coins puzzle (Box
of Defective balls...) But It's solution is somewhat different.
In other coins puzzle you can weigh number of times. But
here it is only once. Try to think differently and post your
answers..
Answer :
In case of normal coin
puzzle they ask number if times required to use the balance to find
the answer. Here it is different. Here you can use only one time the
balance.
The solution is to take the coins in the following order. Take one coin from the first machine, two coins from the second machine, three coin from the third mechine etc.. So that totally you can take
(20 * (20+1) )/2 = 210 coins. Lets consider each coins have 10 ounce weight except one machine coins. So totally you have 2100 ounce weight for 210 coins. If you weigh it now you can get less weight because one machine produces less weight. From the weight you can find the machine which produces less weight coins. Suppose the resultant weight is 2099 then the first machine is fault. If it is 2098 then second machine is fault. That is the fault machine number = 2100 - Obtained weight from balance.
The solution is to take the coins in the following order. Take one coin from the first machine, two coins from the second machine, three coin from the third mechine etc.. So that totally you can take
(20 * (20+1) )/2 = 210 coins. Lets consider each coins have 10 ounce weight except one machine coins. So totally you have 2100 ounce weight for 210 coins. If you weigh it now you can get less weight because one machine produces less weight. From the weight you can find the machine which produces less weight coins. Suppose the resultant weight is 2099 then the first machine is fault. If it is 2098 then second machine is fault. That is the fault machine number = 2100 - Obtained weight from balance.
A Box of Defective Balls
You
have 10 boxes of balls (each ball weighing exactly10 gm) with one box
with defective balls (each one of the defective balls weigh 9 gm).
You are given an electronic weighing machine and only one chance at
it. How will find out which box has the defective balls?
Answer :
For convenience sake, let’s name the boxes from 1 to 10. In order to solve this problem, you have to leverage the fact that you know exactly what each good ball is supposed to weigh and what each defective ball is supposed to weigh. Many of us instinctively will take one ball out of each box and try to find a way to make it work but the trick to take different number of balls from each box.
The number of balls you pick from each bag is equal to the box number. For example, pick 1 ball from box 1, 2 balls from box 2 and so on. In total you will have 55 balls. If all of the boxes have good balls, then the total weight of these balls would be 550gm.
If box 1 has defective balls, then the total weight should be 1gm less than expected (only one ball weighing 9 gm). If box 2 has defective balls, then the total weight should be 2gm less than expected (two balls weighing 9 gm). So once you weigh the set of chosen balls, find out the difference between the total weight and the expected weight. That number represents the box number which contains the defective balls.
Answer :
For convenience sake, let’s name the boxes from 1 to 10. In order to solve this problem, you have to leverage the fact that you know exactly what each good ball is supposed to weigh and what each defective ball is supposed to weigh. Many of us instinctively will take one ball out of each box and try to find a way to make it work but the trick to take different number of balls from each box.
The number of balls you pick from each bag is equal to the box number. For example, pick 1 ball from box 1, 2 balls from box 2 and so on. In total you will have 55 balls. If all of the boxes have good balls, then the total weight of these balls would be 550gm.
If box 1 has defective balls, then the total weight should be 1gm less than expected (only one ball weighing 9 gm). If box 2 has defective balls, then the total weight should be 2gm less than expected (two balls weighing 9 gm). So once you weigh the set of chosen balls, find out the difference between the total weight and the expected weight. That number represents the box number which contains the defective balls.
Puzzle Question : 4 Quarts/Litres of Water
If you had an infinite supply of water and a 5 Quart/Litre and 3 Quart/Litre pails, how would you measure exactly 4 Quart/Litres? and What is the least number of steps you need?
Answer:
This question is very simple actually. Since we can’t hold 4 Quart/Litres/Litres in the 3 Quart/Litre pail, we have to look to filling up the 5 Quart/Litre pail with exactly 4 Quart/Litres. Lets count the steps as we move along
1. Fill 3 Quart/Litre pail ( 5p – 0, 3p – 3)
2. Transfer to 5 Quart/Litre pail (5p – 3, 3p – 0)
3. Fill 3 Quart/Litre pail ( 5p – 3, 3p – 3)
4. Transfer to 5 Quart/Litre pail (5p – 5, 3p – 1)
5. Empty 5 Quart/Litre pail (5p – 0, 3p – 1)
6. Transfer to 5 Quart/Litre pail (5p – 1, 3p – 0)
7. Fill 3 Quart/Litre pail ( 5p – 1, 3p – 3)
8. Transfer to 5 Quart/Litre pail (5p – 4, 3p – 0) We are done!!!
That was easy right. Now for those who are mathematical and need everything solved in terms of a formula, here comes a little more mathematical solution.
Now the general steps are to fill up the 3 Quart/Litre pail and keep transferring to the 5 Quart/Litre pail (empty if full) until we hit 4 Quart/Litres. Therefore, the total amount of water we filled in the 3 Quart/Litre pail must be equal to 4 more than a multiple of 5 (since we discard 5 Quart/Litres of water at a time). From this, we can derive this formula.
5n + 4 = 3m, where n and m are arbitrary positive integers
n represents the number of times we had to empty the 5 Quart/Litre pail and m represents the number of times we had to fill up the 3 Quart/Litre pail.
Now all we have to do is solve for the lowest set of positive integer solutions for {n,m}. {1, 3} is the lowest set. Some of the other solutions are {4, 8}, {7, 13}, {10, 18} and so on.
No comments:
Post a Comment