Medium | Probability |

On a given highway, trucks arrive at the station according to a Poisson process with Lambda = 0.1/minute. This means that after a truck is just passed, the time for the next truck to arrive is an exponential random number with average arrival time of 10 minutes. Your car just broke on this highway, and you are waiting for the next truck for hitchhiking, what is your expected waiting time? On average how many minutes ago the last truck left?

Hint

It's not 5 minutes. Exponential distribution has memoryless property.

Solution

Using memoryless property of exponential distribution, the expected waiting time is 10 minutes. This also holds backwards, hence the expected time last truck passed is also 10 minutes. But this does not violate the total inter-arrival time of 10 minutes, because if your car breaks at a random time, you are more likely to be in long interval than a short one. I don't have time today, remind me to post a more mathematical explanation.

Medium | Probability |

A very sharp, consistently skillful blind archer aimed for the center of a circular board and shot 2 arrows. He is expected to hit the aim, but doesn't hit it for sure. The archer is told that his first shot is better than second. He tried one more shot. What is the probability that this 3rd shot is the best shot among 3?

(ie, Probability that 3rd arrow lands closer to center than his first two shots?)

(ie, Probability that 3rd arrow lands closer to center than his first two shots?)

Hint

Enumeration; Symmetry between random variables.

Answer

1/3

Solution

Suppose x1, x2 and x3 are the distances of the arrows from center. As the archer is consistent, we can use symmetry, i.e., there are six equally likely cases: x1<x2<x3, (or 5 others, which are its permutations). Since archer is told that x1<x2, we are left with following equally likely cases:

x1<x2<x3 , x2<x1<x3 , x1<x3<x2

Among these three, one is favorable. Hence The probability of last shot being best is 1/3.

Notice that if there were (N-1) arrows, with first being better than rest, and then he shoots Nth arrow. The probability that Nth shot is best is 1/N.

x1<x2<x3 , x2<x1<x3 , x1<x3<x2

Among these three, one is favorable. Hence The probability of last shot being best is 1/3.

Notice that if there were (N-1) arrows, with first being better than rest, and then he shoots Nth arrow. The probability that Nth shot is best is 1/N.

Medium | Strategy |

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?

Hint

the answer is ~1.5n calculations. It uses a trick. When you compare two elements, one comparison is sufficient to find both min & max of those two elements.

Solution

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.

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.

Source: H. Cormen

Enable Like and Comment Medium | Discrete Maths |

There is a crazy clock in Alice's Dream, it has two hands initially pointing at 12. The minute hand moves clockwise, making 5 rounds (with varying speeds) and comes back to 12. In the same time, the hour hand goes anti-clock wise, finishing 4 rounds and returns to 12. How many times did the two cross each other ? (Cross means meet & pass through, hence ignore start & end)

Answer

8

Solution

In the reference frame of minute hand, hour hand moves exactly (5+4) = 9 rounds anti-clockwise with varying speeds (by adding total angular distance covered). 'Cross' occurs just in between two consecutive rounds. Thus hour hand crosses minute hand exactly 9-1=8 times. Same answer in ref. plane of hour-hand.

Source: Self

Enable Like and Comment Medium | Discrete Maths |

A group of students are sitting in a circle with the teacher in the center. They all have an even number of candies (not necessarily equal). When the teacher blows a whistle, each student passes half his candies to the student on his left. Then the students who have an odd number of candies obtain an extra candy from the teacher. Show that after a finite number of whistles, all students have the same number of candies.

Hint

Look at minimum & maximum count of candies.

Solution

1. The maximum number of candies held by a single student can never increase.

2. The minimum number of candies held by a single student always strictly increases, unless the student to his right also has the minimum number of candies, in which case the length of the longest consecutive segment of students who have minimum number of candies strictly decreases. Thus eventually the minimum has to strictly increase.

3. Since the minimum has to strictly increase in a finite number of steps and cannot go beyond the maximum, all the numbers must eventually be equal in atmost n(max-min) steps.

2. The minimum number of candies held by a single student always strictly increases, unless the student to his right also has the minimum number of candies, in which case the length of the longest consecutive segment of students who have minimum number of candies strictly decreases. Thus eventually the minimum has to strictly increase.

3. Since the minimum has to strictly increase in a finite number of steps and cannot go beyond the maximum, all the numbers must eventually be equal in atmost n(max-min) steps.

Source: puzzletweeter

Enable Like and Comment Latest solved Puzzles

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

© BRAINSTELLAR |