Medium | Strategy |

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?

Hint

Try prisoner's Hat puzzle first

Solution

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.

Medium | Strategy |

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?

Hint

Modulo?

Solution

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!

Source: lieno

Enable Like and Comment Hard | Strategy |

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

PS: This scene is from X-men: First Class. Good x-men are in the aircraft called blackbird, human radar is Banshee, Magnet is Magneto. Bad x-men are in submarine, with Sebastian Shaw is about to cause a war, better catch him soon!

PS: This scene is from X-men: First Class. Good x-men are in the aircraft called blackbird, human radar is Banshee, Magnet is Magneto. Bad x-men are in submarine, with Sebastian Shaw is about to cause a war, better catch him soon!

Hint

The locus of submarine from its spotted location is a circle of radius (speed of sub)*(time passed). We only need to move around this locus for some time.

Solution

Let speed of plane be 2s, submarine: s, original distance d

Locus of submarine after time t is circle of radius s*t centered at original location of submarine. Thus the plane moves 2/3 distance towards submarine, and then spirals out by increasing radius with speed 's'. The submarine is caught after one round.

For General case, with speeds p > s, see Palak's Answer:

Let Op, Os be the initial positions of the plane and the submarine, resp. For time t0 = d/(s+p), the plane will move towards Os in the OpOs direction. After that, with Os as the origin, the plane will maintain a constant velocity of s along the radial direction. Thus, at an angle theta from OpOs, tangential displacement in time dt is sqrt(p^2-s^2)*dt = r*d(theta) = s*t*d(theta) => dt/t = s/sqrt(p^2-s^2)*d(theta). Integrating t from t0 to tf, and theta from 0 to 2*pi, we get tf = t0*exp[2*pi*s/sqrt(p^2-s^2)] = [d/(s+p)]*exp[2*pi*s/sqrt(p^2-s^2)].

Note that the plane can be vertically above the submarine any time between t0 and tf, depending on the direction theta of the velocity of the submarine wrt OpOs, thus making tf the worst case time.

Locus of submarine after time t is circle of radius s*t centered at original location of submarine. Thus the plane moves 2/3 distance towards submarine, and then spirals out by increasing radius with speed 's'. The submarine is caught after one round.

For General case, with speeds p > s, see Palak's Answer:

Let Op, Os be the initial positions of the plane and the submarine, resp. For time t0 = d/(s+p), the plane will move towards Os in the OpOs direction. After that, with Os as the origin, the plane will maintain a constant velocity of s along the radial direction. Thus, at an angle theta from OpOs, tangential displacement in time dt is sqrt(p^2-s^2)*dt = r*d(theta) = s*t*d(theta) => dt/t = s/sqrt(p^2-s^2)*d(theta). Integrating t from t0 to tf, and theta from 0 to 2*pi, we get tf = t0*exp[2*pi*s/sqrt(p^2-s^2)] = [d/(s+p)]*exp[2*pi*s/sqrt(p^2-s^2)].

Note that the plane can be vertically above the submarine any time between t0 and tf, depending on the direction theta of the velocity of the submarine wrt OpOs, thus making tf the worst case time.

Source: Inspired from Rustan Leino's puzzle

Enable Like and Comment Hard | Strategy |

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. The means by which you can attempt to do that is: 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. That is, you will ask a question like "Is the spy currently at location 27?" and you will get a yes/no answer. Devise an algorithm that will eventually find the spy

Solution

Here is a detailed solution with images

And here is a short solution by Palak Bhushan

since integer 2-tuples (x,y) are countable, there exists a function f:N->N*N such that f covers all integer 2-tuples. Let f(n)=(f1(n),f2(n)). The algorithm will be to check for location f1(n)+n*f2(n) at time instant n. Given A and B, there exists n0 such that f(n0)=(f1(n0),f2(n0))=(A,B), and thus at time instant n0 we will be checking for location f1(n0)+n0*f2(n0) which is =A+B*n0 -- the actual location of the spy.

And here is a short solution by Palak Bhushan

since integer 2-tuples (x,y) are countable, there exists a function f:N->N*N such that f covers all integer 2-tuples. Let f(n)=(f1(n),f2(n)). The algorithm will be to check for location f1(n)+n*f2(n) at time instant n. Given A and B, there exists n0 such that f(n0)=(f1(n0),f2(n0))=(A,B), and thus at time instant n0 we will be checking for location f1(n0)+n0*f2(n0) which is =A+B*n0 -- the actual location of the spy.

Source: Written Test; leino

Enable Like and Comment Hard | Strategy |

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

Hint

Divide and conquer

Solution

It takes about (log N)^2 operations:

Divide the set of 2^k with d heavy coins into two sets, each with 2^(k-1) coins with floor(d/2) heavy coins. If we can do this, we can determine the number of heavy coins in O(log n)^2 operations.

Dividing the set can be done in O(log n). (*Later)

So, T(n) = T(n/2) + O(log n)

T(n) = O(log^2 n).

To be exact, this is k*(k+1)/2 . where k = log N

(*Sub-Algorithm)

Divide the set into two sets A and B of equal number of coins. Let A greater than B and to make both side of equal weight, I need to shift few coins from A to B and equal number of coins from B to A. So divide A into A1 and A2, and B into B1 and B2. Move A2 from A into B and B1 from B into A now if (A1,B1) is greater than (B2,A2) then I have not moved enough coins from A into B so as to make B part heavy enough hence you divide A1 into A11,A12 and move A12 in B side similarly u move B21 into A side on the other hand if (A1,B1) is less than (A2,B2) I have more than enough coins from A into B hence move B12 back into B and A21 back into A now measure again. Do it so on...

Note that we are doing this in O(log n) as each time the number of coins we are moving is reduced by half. So, In O(log n), we are done.

To prove that solution always exists, we do it by induction:

difference in the number of heavy coin after kth iteration cannot be more than 2^(n-1-k)

So, after n-1th iteration, it can be more that 1 coin. Hence, done. :)

Divide the set of 2^k with d heavy coins into two sets, each with 2^(k-1) coins with floor(d/2) heavy coins. If we can do this, we can determine the number of heavy coins in O(log n)^2 operations.

Dividing the set can be done in O(log n). (*Later)

So, T(n) = T(n/2) + O(log n)

T(n) = O(log^2 n).

To be exact, this is k*(k+1)/2 . where k = log N

(*Sub-Algorithm)

Divide the set into two sets A and B of equal number of coins. Let A greater than B and to make both side of equal weight, I need to shift few coins from A to B and equal number of coins from B to A. So divide A into A1 and A2, and B into B1 and B2. Move A2 from A into B and B1 from B into A now if (A1,B1) is greater than (B2,A2) then I have not moved enough coins from A into B so as to make B part heavy enough hence you divide A1 into A11,A12 and move A12 in B side similarly u move B21 into A side on the other hand if (A1,B1) is less than (A2,B2) I have more than enough coins from A into B hence move B12 back into B and A21 back into A now measure again. Do it so on...

Note that we are doing this in O(log n) as each time the number of coins we are moving is reduced by half. So, In O(log n), we are done.

To prove that solution always exists, we do it by induction:

difference in the number of heavy coin after kth iteration cannot be more than 2^(n-1-k)

So, after n-1th iteration, it can be more that 1 coin. Hence, done. :)

Source: CSEblog

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |