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 Hard | Strategy |

Two immensely intelligent players, A & B, engage in a game, the rules of which are as follows. For some 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 does't affect who wins, there is an added rule. Once you strike of 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?

Solution

Source: Krishnamurthy Iyer

Enable Like and Comment Hard | Strategy |

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.

Hint

It can be done in less than N queries. End of a chain is testified by one anti somewhere in the middle.

Solution

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.

Solution by jadu, on CSE Blog, 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.

Solution by jadu, on CSE Blog, 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.

Source: Toad Puzzles

Enable Like and Comment Latest solved Puzzles

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

© BRAINSTELLAR |