Question 1

Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied. A new customer wants to check in, how will you accommodate her? What if infinite number of people want to check in, how will you accommodate them? Suppose infinite number of buses arrive at the hotel, each having infinite number of people, how will you accommodate them?

Accepted Answer

Since there are infinite number of rooms and infinite+1= infinite Just ask person in room k to move to k+1, thus making the first room vacant. :) In the other case, since infinite+infinite = infinite asking person in room k to move to 2k solves the problem. Since NxN is countable set. We can get a 1-1 mapping from N to NxN Hence, we can accommodate (infinite people X infinite buses) in the hotel. Relevant article: http://en.wikipedia.org/wiki/Cantor_pairing_function

Question 2

100 prisoners are lined up and assigned a random hat These hats are available in 10 different unique and distinguishable colors. Each prisoner can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be the color like "red" or "blue" or "green" etc. If the word matches their hat color they are released, if not, they are killed on the spot. They can hear each others answers, no matter how far they are on the line. What strategy should be used to help release maximum number of prisoners?

Accepted Answer

Call the first person in back of row the 100th prisoner. The 10 colours will be given codes from 0 to 9. The 100th prisoner will sum the numbers associated with the 99 colours he sees and will say the colour corresponding to it modulo 10. This is enough for 99th person. All he needs to do now is connect the dots, sum the number of hats he can see, calculate modulo 10, and compare it with what 100th prisoner said. This way all 99 prisoners will be saved, and 100th prisoner dies with probability 9/10.

Question 3

N people team up and decide on a strategy for playing this game. Then they walk into a room. On entry to the room, each person is given a hat on which one of the first N natural numbers is written. There may be duplicate hat numbers. For example, for N=3, the 3 team members may get hats labeled 2, 0, 2. Each person can see the numbers written on the others' hats, but does not know the number written on his own hat. Every person then simultaneously guesses the number of his own hat. What strategy can the team follow to make sure that at least one person on the team guesses his hat number correctly?

Accepted Answer

Let the persons be numbered 0 to N-1. The i-th person should announce 1 + (i-s)mod N, where s is the sum of numbers he sees. With this strategy, if the sum of all N numbers equals 1 + (m mod N), then the m-th gnome is guaranteed to announce the number of his own hat!

Question 4

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. At each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. Devise an algorithm that will eventually find the spy.

Accepted Answer

Since integer 2-tuples (x, y) are countable, there exists a function f: N -> N*N that covers all integer 2-tuples. Let f(n) = (f1(n), f2(n)). The algorithm is to check location f1(n) + n * f2(n) at time step n. Since the spy is at position A + nB at time n, when f(n) = (A, B), we check A + nB which is exactly the spy's location. Since f is a bijection covering all (A, B) pairs, this is guaranteed to find the spy in finite time.

Question 5

Two immensely intelligent players, A & B, engage in a game, the rules of which are as follows. For a natural number N, the board consists of numbers from 1 to N. Each player takes turns to strike off a (new) number from the board. But, to make sure N doesn't affect who wins, there is an added rule. Once you strike off a number, you also have to strike off all its divisors in that same chance, irrespective of whether any of those divisors were already marked. The player to strike off the last number on the board wins. Can A construct a winning strategy? Note: The question asks for the existence of the strategy, not to devise the strategy itself.

Accepted Answer

Yes, A always has a winning strategy, by the strategy-stealing argument. For a given N, either A has a winning strategy or B. If B has the strategy, then A can strike 1 first and then copy B's strategy. This contradicts the assumption that B had a winning strategy, so A must always have one. There is no simple formula for the winning strategy based on N; the argument only proves existence.

Question 6

N undercover agents have been found in don's lair. Less than half of them are terrorists and the rest are anti-terrorists. The nature of their job is so secret that there is no proof what so ever to testify who is who. Although each of them knows who was actual terrorist and who was anti because they worked in teams. A query consists of asking person i if person j is Anti. Anti will always speak truth but a terrorist may lie to confuse you. The goal is to find out one anti in fewest queries.

Accepted Answer

Please note that this question cannot be solved with any algorithm if terrorists are more than or equal to anti, because terrorists can plan to always lie. Another solution taking only N-1 queries: We will try to find a chain of persons (i1,i2,i3....im) such that each ij is queried about i(j+1) and answer is correct. Note that if such chain contains an anti then last person in the chain would be anti. So query person 1 about 2. If answer is yes query person 2 about 3. continue till answer is correct. suppose at some point person i when queried about person j says wrong, in that case remove person i and j from the chain, and continue query process by querying predecessor of i about successor of j. Here note that when we remove person i and j from the chain at-least one of them must be faulty. here for each person except the first one, we are querying once. Hence N-1 comparison in worst case. Think about the best case using this algorithm.

Question 7

Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons?

Accepted Answer

Solution requires approximately 1.5n comparisons instead of 2n comparisons. Break n numbers into pairs of 2. So, that is n/2 pairs. Find maximum and minimum in each pair. Cost = n/2. Now given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2 So, overall cost 3n/2 comparisons.

Question 8

A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed? Solution It uses Axiom of choice in a special way. Before night of execution, prisoners will create some equivalent classes among the set of all possible infinitely long binary strings. Let us say two infinite strings s1 and s2 are related, if they differ at finitely many places, and are same otherwise. This creates the equivalence relation. Thus they create all equivalence class. From each class, we mark one representative string. Now, a person pi looks ahead, and instantly knows his equivalent class & recalls the representative string S. When his turn comes, he speaks the ith digit of S as his guess. Since S and actual (current) string only differ upto a finite (say N) number of position. Thus only atmost N people may die using this technique. Now, first person will count number of places S differs from current string, and answer it in modulo 2. Based on answer of first person, second person can deduce his hat color. now the third person can deduce his color and so on. Except possibly for the first person, everyone will guess correctly.

Accepted Answer

It uses Axiom of choice in a special way. Before night of execution, prisoners will create some equivalent classes among the set of all possible infinitely long binary strings. Let us say two infinite strings s1 and s2 are related, if they differ at finitely many places, and are same otherwise. This creates the equivalence relation. Thus they create all equivalence class. From each class, we mark one representative string. Now, a person pi looks ahead, and instantly knows his equivalent class & recalls the representative string S. When his turn comes, he speaks the ith digit of S as his guess. Since S and actual (current) string only differ upto a finite (say N) number of position. Thus only atmost N people may die using this technique. Now, first person will count number of places S differs from current string, and answer it in modulo 2. Based on answer of first person, second person can deduce his hat color. now the third person can deduce his color and so on. Except possibly for the first person, everyone will guess correctly.

Question 9

You are in a dark room with a deck of 52 cards. You know exactly 10 cards are face up. You can't see or feel which way cards face. Split the deck into two piles so each pile has the same number of face-up cards.

Accepted Answer

Take any 10 cards off the top and flip them over. This pile now has the same number of face-up cards as the remaining 42-card pile. If the top 10 cards had k face-up cards, then the bottom pile has 10-k face-up cards. After flipping all 10, the top pile has 10-k face-up cards too.

Question 10

You have 12 balls, one is heavier or lighter. You have a balance scale and 3 weighings. Find the odd ball and whether it's heavier or lighter.

Accepted Answer

Divide into 3 groups of 4. Weigh group A vs group B. Case 1: they balance — the odd ball is in group C. Take 3 from C, weigh against 3 known-good balls. If they balance, the remaining ball is odd — weigh it against a known ball to determine heavier/lighter. If they don't balance, you know whether the odd ball is heavier or lighter; weigh 2 of the 3 suspects against each other to isolate it. Case 2: A and B don't balance — you now know which side is heavier. Relabel and use the third weighing to isolate the odd ball among the suspects.

Question 11

You have 25 horses and can race 5 at a time. What is the minimum number of races needed to find the 3 fastest horses (no stopwatch)?

Accepted Answer

7 races. First, run 5 races of 5 horses each (5 races). Rank the winners and race them against each other (race 6). Now the overall fastest horse is the winner of race 6. The 2nd and 3rd fastest must be among: the 2nd and 3rd place from the winner's original group, the 2nd place from the group whose winner came 2nd in race 6, and the winner who came 3rd in race 6. That's 5 candidates — race them (race 7). The top 2 from race 7 plus the overall winner are your 3 fastest.

Question 12

You are standing outside a closed room with three light bulbs and three switches. You can flip switches as much as you want but can only enter the room once. How do you determine which switch controls which bulb?

Accepted Answer

Turn on switch 1 and wait 5 minutes. Turn it off, turn on switch 2, and enter. The lit bulb is switch 2. The warm but off bulb is switch 1. The cold, off bulb is switch 3.

Question 13

You have a 3-litre jug and a 5-litre jug with unlimited water. How do you measure exactly 4 litres?

Accepted Answer

Fill the 5L jug, pour into the 3L jug (leaving 2L). Empty the 3L jug, pour the 2L into it. Fill the 5L jug again and pour into the 3L jug until full (1L poured). Exactly 4L remain in the 5L jug.

Question 14

Why are manhole covers round rather than square?

Accepted Answer

A round cover cannot fall through its own opening. A circle has constant diameter regardless of orientation, whereas a square cover could be tilted diagonally and fall through since the diagonal is longer than the side.

Question 15

A single lily pad doubles in size every day. It takes 48 days to cover the entire lake. On which day was the lake half-covered?

Accepted Answer

Day 47. Since the lily pad doubles every day, if it covers the full lake on day 48, it must have been half-covered on day 47.

Question 16

100 prisoners in a line each wear a red or blue hat. Starting from the back, each must guess their hat color. They can see all hats in front but not their own. What strategy guarantees 99 are released?

Accepted Answer

The last prisoner counts blue hats in front and says 'Blue' if even, 'Red' if odd (parity check). Each subsequent prisoner tracks the running parity from previous guesses and what they see ahead to deduce their own hat color. All 99 after the first are guaranteed correct.

Question 17

On a standard analog clock, what is the exact angle between the hour and minute hands at 3:15?

Accepted Answer

7.5 degrees. At 3:15, the minute hand is at the 3 (90 degrees). The hour hand moves 0.5 degrees per minute, so in 15 minutes past 3 it has moved 7.5 degrees beyond the 3. The gap is 7.5 degrees.

Question 18

A blind man has 10 black socks and 10 navy blue socks in a drawer. How many must he pull out to guarantee a matching pair?

Accepted Answer

3 socks. By the Pigeonhole Principle, with only 2 colors, the 3rd sock must match one of the first two.

Question 19

You have two ropes, each burns for exactly 1 hour but not uniformly. How do you measure exactly 45 minutes?

Accepted Answer

Light rope 1 from both ends and rope 2 from one end simultaneously. Rope 1 burns out in 30 minutes. At that moment, light the other end of rope 2. Rope 2 had 30 minutes of burn left, but now burning from both ends it takes 15 more minutes. Total: 30 + 15 = 45 minutes.

Question 20

You have 10 people in a room. How many total handshakes if they all shake hands?

Accepted Answer

45. (10 choose 2) = 10! / (2! × 8!) = 45 — this is the total number of ways two people can shake hands.

Question 21

A group of people wants to determine their average salary on the condition that no individual would be able to find out anyone else's salary. Can they accomplish this, and, if so, how?

Accepted Answer

Yes. The first person thinks of a random number X and adds it to their salary. The rest of the group simply adds their salary to the running total. Then, the first person subtracts X and divides by the group size to get the average.

Question 22

You have a 3 gallon jug and 5 gallon jug, how do you measure out exactly 4 gallons?

Accepted Answer

Fill the 3-gallon jug and pour into the 5-gallon. Fill the 3-gallon again and pour until the 5-gallon is full (1 gallon remains). Empty the 5-gallon, pour in the 1 gallon, then fill the 3-gallon and add it. 1 + 3 = 4 gallons.

Question 23

You're in a room with three light switches, each controls one of three bulbs in the next room. All lights are off. You can only inspect the other room once. How do you determine which switch controls which bulb?

Accepted Answer

Turn switch 2 on for ten minutes, then turn it off and quickly turn on switch 3. Go into the room. The lit bulb is switch 3. The off but warm bulb is switch 2. The remaining cold bulb is switch 1.

Question 24

N undercover agents have been found in a lair. Less than half of them are terrorists and the rest are anti-terrorists. The nature of their job is so secret that there is no proof to testify who is who. Although each of them knows who is a terrorist and who is anti because they worked in teams. A query consists of asking person i if person j is anti. An anti-terrorist will always speak the truth but a terrorist may lie to confuse you. The goal is to find out one anti-terrorist in the fewest queries. Note that this problem cannot be solved if terrorists are greater than or equal to anti-terrorists, because terrorists can coordinate to always lie.

Accepted Answer

The answer is N-1 queries. Build a chain of persons (i1, i2, i3, ..., im) such that each ij is queried about i(j+1) and the answer is "yes" (anti-terrorist). Start by querying person 1 about person 2. If the answer is "yes," query person 2 about person 3, and continue until someone says "no." Suppose at some point person i says person j is a terrorist. In that case, remove both person i and person j from the chain, and continue the query process by querying the predecessor of i about the successor of j. The key insight is that when we remove persons i and j, at least one of them must be a terrorist. Since terrorists are fewer than anti-terrorists, after all removals the chain still contains at least one anti-terrorist, and the last person in such a chain must be an anti-terrorist. For each person except the first, we query exactly once, giving N-1 queries in the worst case.

Question 25

You are given N coins which look identical (assume N = 2^k). Some of them are pure gold coins (heavy) and the rest are aluminum coins with thin gold plating (light). You are given one beam balance with two pans. All gold coins have equal weight and all fake coins have the same weight. What is the minimum number of weighings required to separate the gold coins from the fake coins?

Accepted Answer

The answer is k(k+1)/2 weighings where k = log2(N), which is O((log N)^2). The approach is recursive: divide the set of 2^k coins (with d heavy coins) into two equal sets, each containing exactly floor(d/2) heavy coins. If we can do this division, we can solve the problem with T(n) = T(n/2) + O(log n), giving T(n) = O(log^2 n). The division sub-algorithm works in O(log n) steps: split the coins into sets A and B of equal size. If A is heavier, we need to swap some coins between A and B to equalize the number of heavy coins. Divide A into A1, A2 and B into B1, B2. Swap A2 with B1 and weigh (A1, B1) against (B2, A2). If the first side is heavier, we have not moved enough heavy coins out of A, so subdivide A1 further. If lighter, we moved too many, so undo part of the swap. Each iteration halves the number of coins being moved, so in O(log n) weighings the sets are balanced. By induction, the difference in heavy coins after the kth iteration is at most 2^(n-1-k), so after n-1 iterations the difference is at most 1, completing the separation.

Question 26

An aircraft hovers above the sea, trying to catch a submarine moving with a constant velocity under the sea. The submarine is completely invisible, but using a radar once, the aircraft knows the exact location of the submarine. The direction of the submarine is unknown but constant. The aircraft can move at twice the speed of the submarine. As soon as the aircraft is directly above the submarine, it can magnetically pick it up. How does the aircraft catch the submarine, and how much time will it take?

Accepted Answer

Let the speed of the plane be p and the submarine be s, with p > s, and let d be the initial distance between them. Let Op and Os be the initial positions of the plane and submarine. For time t0 = d/(s+p), the plane moves toward Os along the OpOs direction. After reaching Os, with Os as the origin, the plane maintains a constant radial velocity of s (matching the submarine radial expansion) while using its remaining speed tangentially. At angle theta from OpOs, the tangential displacement in time dt is sqrt(p^2 - s^2) * dt = r * d(theta) = s * t * d(theta). This gives dt/t = s/sqrt(p^2 - s^2) * d(theta). Integrating t from t0 to tf and theta from 0 to 2*pi yields tf = t0 * exp(2*pi*s / sqrt(p^2 - s^2)) = [d/(s+p)] * exp(2*pi*s / sqrt(p^2 - s^2)). For the specific case where p = 2s, the plane moves 2/3 of the distance d toward the submarine original position, then spirals outward with increasing radius at speed s. The submarine is caught after one full spiral revolution. The worst-case time is tf, though the plane could be above the submarine at any point between t0 and tf depending on the submarine direction.

Question 27

Five pirates need to divide 100 Gold Coins. Pirates have a hierarchy, from Level 1 to level 5. The highest level pirate is the leader. The leader proposes a plan to distribute the gold and all the pirates vote on it (including the leader). If at least 50% of the pirates agree on the plan, the gold is split according to the proposal. If not, level-5 pirate is kicked from the ship, and the level-4 pirate now proposes a new plan. This process continues until a proposal is accepted. All pirates are extremely smart and extremely greedy. How does level-5 Pirate divide the treasure?

Accepted Answer

Coin distribution is: (98, 0, 1, 0, 1) from levels (5, 4, 3, 2, 1) respectively. Let the pirates be called P5, P4, P3, P2, P1. P5 is the leader. Let's study a simpler case with only 2 pirates. P2 can propose to take all the 100 gold coins. Even if P1 votes against this, P2 will vote in favor and the proposal will still be accepted (50% acceptance) leaving P1 with zero coins. The distribution is (100, 0) for levels (2, 1) respectively. Now let's look at the case with 3 pirates. P3 knows that if this proposal is not accepted, then P2 will get all the gold and P1 will get nothing. So P3 can bribe P1 with one gold coin. P1 knows that one gold coin is better than zero, and hence votes in favor of this proposal. Therefore, P3 can propose the following distribution {Level 3 pirate: 99, Level-2: 0, Level-3: 1}. Since pirate 1 and 3 will vote in favor, this proposal will be accepted. The distribution is (99, 0, 1) for levels (3, 2, 1) respectively. If there are 4 pirates, P4 can extend this pattern by bribing those who would get nothing in 3-pirates case, to ensure their votes. So the distribution will be (99, 0, 1, 0) for levels (4, 3, 2, 1) respectively, this will ensure that P2 will vote in favor and with the help of self voting (P4), we have 50% votes to accept this proposal. Similarly, P5 can bribe P3 and P1 pirates because they get nothing if the proposal is rejected, as P4 was giving them nothing. Hence, at level-5, the proposal is (98, 0, 1, 0, 1). This proposal will get accepted and provide the maximum amount of gold to the leader. This puzzle gives a basic idea of game theory and dynamic programming.

Question 28

Hundred tigers and one sheep are put on a magic island that only has grass. Tigers can live on grass, but they want to eat sheep. If a Tiger bites the Sheep then it will become a sheep itself. If 2 tigers attack a sheep, only the first tiger to bite converts into a sheep. Tigers don’t mind being a sheep, but they have a risk of getting eaten by another tiger. All tigers are intelligent and want to survive. Will the sheep survive?

Accepted Answer

Sheep survives!. If there is 1 tiger, then it will eat the sheep because he does not need to worry about being eaten. Sheep will not survive. If there are 2 tigers, both of them knows that if one eats the Sheep, the other tiger will eat him. So, the sheep will survive. If there are 3 tigers, then they each of them knows that if one tiger eats up the sheep, then Iceland will be left with 1 sheep and 2 tigers and as shown in the previous case, the sheep will survive. Hence each tiger will try to eat up the sheep. The sheep will not survive. If there are 4 tigers, then the sheep will survive. And so on…. So, If there are even number of tigers the sheep will survive, else it will die. Hence, if there are 100 tigers the sheep will survive.

Question 29

A duck is sitting at the center of a circular lake. A fox is waiting at the shore, not able to swim, wishing to eat the duck. The Fox can move around the whole lake at a speed four times the speed at which the duck can swim. The duck can fly, but only once it reaches the shore of the lake, it can't fly from the water directly. Can the duck always reach the shore without being eaten by the fox? Note: This is an old duck, and cannot take a flight while swimming. The duck cannot submerge in the water.

Accepted Answer

Yes. At a radius of slightly less than R/4, the duck can swim in circles, forcing the fox to run around. Once the duck is at a phase of π from the fox, it starts swimming towards the shore and flies away. The duck begins by swimming in a circle with radius r < R/4 where R is the radius of the lake. The fox is four times as fast as the duck. By swimming in a small circle, the duck can create an angular separation between itself and the fox. The duck continues swimming in its smaller circle until the fox is straight across the lake from it. At this point, the duck swims straight to the shore. The duck has to travel around R * 3/4, while the fox has to run πR (half the circumference). Since πR > 4 * (3R/4) = 3R only if π > 3, which is true, the duck escapes.

Question 30

A traveler meets a pair of twins at a fork in the road: one path is correct and one incorrect. One of the twins always tells the truth (knight), and the other one always lies (knave). Which single question can the traveler ask one of the twins to determine the correct path?

Accepted Answer

This can be constructed in many ways. The traveler can ask, "Would the other twin agree that the road on the left is correct?" The answer is guaranteed to be 'Yes' if and only if the road on the right is correct. The traveler can also ask, "If I were to ask you whether the road on the right is correct, would you say 'Yes'?", both the twins tell yes only if the right path is indeed correct.

Question 31

An Egg breaks only if dropped from above a threshold floor, within a 100-story building. Every time you drop an egg, it is counted as an attempt. You are given 2 eggs to deduce the threshold floor, with a minimum number of attempts in the worst case!

Accepted Answer

It can be done in 14 steps in the worst case. We can skip some floors and jump ahead when testing with the first egg (egg1). Whenever egg1 breaks, egg2 has to scan linearly from the last safe floor to the floor where egg1 broke. We can improve by reducing the gap on each attempt of egg1. If we test at floor 10, 10+9, 10+9+8, and so on, then in the worst case, the number of attempts will be at most (1+9)=10 or (2+8)=10 and so on. This sequence ends at 10+9+8... = n(n+1)/2 = 55 and does not span 100 floors. The solution for minimum steps in the worst case is the smallest integer >= the positive solution of x(x+1)/2 = 100, giving x = 13.651. Start at floor 14; if the egg breaks, start linearly from 1. If it does not break, drop the egg from 14+13 = 27, and so on. The gaps decrease: 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, covering up to floor 105 which spans all 100 floors. The worst case is 14 attempts.

Question 32

A certain town comprises of 100 married couples. Some husbands secretly cheat on their wives. All wives know about the nature of every husband except their own. When a wife concludes that her husband cheated, she kicks her husband into the street at midnight. All husbands remain silent about their secret. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. After announcement, no one talks, waiting for someone to get kicked. Till 9th night from announcement, no husband was kicked, but on the 10th night, some husbands got kicked out simultaneously. How many are they?

Accepted Answer

It must be 10 husbands kicked out. If there was only 1 cheating husband in the town, there will be 99 women who know exactly who the cheater is. The 1 remaining woman, who is being cheated on, would have assumed there are no cheaters. But now that the mayor has confirmed that there is at least one cheater, she realizes that her own husband must be cheating on her. So her husband gets kicked on the day of the announcement. Now let’s assume there are 2 cheaters in the town. There will be 98 women in the town who know who the 2 cheaters are. The 2 wives, who are being cheated on, would think that there is only 1 cheater in the town. Since neither of these 2 women know that their husbands are cheaters, they both do not report their husbands in on the day of the announcement. The next day, when the 2 women see that no husband was kicked, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are kicked. Through induction, it can be proved that when this logic is applied to n cheating husbands, they are all kicked on the n th day after the mayor’s announcement. Hence it must be 10 husbands kicked in our case.

Question 33

So there's this king. Someone breaks into his wine cellar where he stores 1000 bottles of wine. This person proceeds to poison one of the 1000 bottles, but gets away too quickly for the king's guard to see which one he poisoned or to catch him. The king needs the remaining 999 safe bottles for his party in 4 weeks. The king has 10 prisoners who deserve execution. The poison takes about 3 weeks to take effect, and any amount of it will kill whoever drinks it. How can he figure out which bottle was poisoned in time for the party?

Accepted Answer

The king has to mix wine in order to isolate the single poisoned one. 2) There are 10 servants. After about 3 weeks, each one can be either dead or alive, meaning that there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it's actually possible for some scheme to work. Here's the scheme: The king assigns each servant a number from 1-10. The king assigns each bottle a number from 0-999. When he labels them, though, he writes the number on the bottle in binary with ten digits, like this: 0: 000000000 1: 000000001 2: 000000010 3: 000000011 4: 000000100 5: 000000101 ... 999: 1111100111 and so on. Now the strategy is simple: Pick bottle 1, write its binary form, look at the positions where '1' appears (here: 1st only). Make the corresponding prisoner drink small quantitiy of that wine. (ie prisoner 1 takes a sip of wine #1). Continue this process upto 1000th wine. After 3 weeks, suppose only prisoner number 4 & 7 die. This means the binary representation of poisoned wine has '1' at position 4 & 7, and rest all zeros. Convert this binary number to decimal and that gives the poisoned wine.

Quantitative Finance

Quantitative Finance

Quantitative Finance

Quantitative Finance