Hard | Probability |

You are initially located at origin in the x-axis. You start a random walk with equal probability of moving left or right one step at a time. What is the probability that you will reach point a before reaching point -b? What is the expected number of steps to reach either a or -b? (a,b are natural numbers)

Answer

b/(a+b) and ab

Solution

If you try markov chain approach, this question will never end! For this problem, we will use Martingales.

Let N = number of steps to reach any of a or -b. Let SN = X1+...+XN. Suppose Pa = probability of touching a before -b, and Pb = the opposite. We use the fact that both SN and (SN^2-N) are martingales, thus:

0 = E(SN) = a*Pa + (-b)*Pb

This gives Pa = b/(a+b)

Similarly, 0 = E(SN^2-N) = Pa*a^2 + Pb*b^2 - E(N)

This gives E(N) = ab

Let N = number of steps to reach any of a or -b. Let SN = X1+...+XN. Suppose Pa = probability of touching a before -b, and Pb = the opposite. We use the fact that both SN and (SN^2-N) are martingales, thus:

0 = E(SN) = a*Pa + (-b)*Pb

This gives Pa = b/(a+b)

Similarly, 0 = E(SN^2-N) = Pa*a^2 + Pb*b^2 - E(N)

This gives E(N) = ab

Source: Top Quant Interview

Enable Like and Comment Hard | Probability |

You are taking out candies one by one from a jar that has 10 red candies, 20 blue candies, and 30 green candies in it. What is the probability that there are at least 1 blue candy and 1 green candy left in the jar when you have taken out all the red candies? (Candies of same color are indistinguishable!)

Hint

Combinatorial problem. Consider a sequence of 60 candies, in which red candies finish before blue and green.

Answer

7/12

Solution

It can be done using combinatorics as well as conditional probability. I don't have time today, but please remind me to put proper solution by commenting down below or by sending me a message. Thank you.

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 |