Some Interesting Probablity Puzzles

Balls into Bins



1. Given n balls and n bins. We throw each ball uniformly randomly into the bins. What is the expected number of (i) empty bins (ii) bins containing one ball (iii) bins containing k balls



2. Given an unlimited supply of balls and a set of n empty bins. We take a ball from the supply and throw it randomly among the bins so that its chances of landing into any of the n bins is same. We continue throwing the balls until no bin is left empty. What is the expected number of balls thrown before no bin is left empty ?



3. Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have n balls, which are thrown uniformly randomly into n bins. After round i , we discard every ball that fell into a bin itself in round i . The remaining balls are retained for i+1 round, in which they are again thrown independently and uniformly at random into the n bins. We stop when there is no ball left. Prove that with probability 1- o(1) the experiment will finish in loglog n number of rounds.



Balls out of Bin

1. A bin contains a white balls and b black balls. We take out the balls at random from the bin without replacement. What is the probability that first ball is white, second ball is white, kth ball is white.



2. A bin contains n balls numbered 1,2,...,n . We pick a bunch of k balls from the bin uniformly randomly. What is the
(i) expected number of the greatest numbered ball in the bunch.
(ii) expected number of the least numbered ball in the bunch.



3. There are n bins and n players, and each player has an infinite supply of balls. The bins are initially empty. We have a sequence of rounds : in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable Z be the number of rounds before every bin is non-empty. Determine the expected value of Z. What can you say about the distribution of Z?



4. A bin contains m white balls and n black balls. We take out the balls uniformly randomly from the bin without replacing them. What is the expected number of black balls left when all the white balls have been taken out.

given a 6x6 matrix with all the elements as either 1 or -1. find the number of ways the elements can b arranged such that 1.the product of all elements of all columns is 1 2.the product of all elements of all rows is 1

There are four dogs each at the corner of a unit square. Each of the dogs starts chasing the dog in the clockwise direction. They all run at the same speed and continuously change their direction accordingly so that they are always heading straight towards the other dog. How long does it take for the dogs to catch each other and where?

Since the dogs are moving symmetrically, the distance saperating them will decrease evenly as they case each other, so the dogs should catch each other in the center of the room. Their path will be curved, but for sake of approximation, lets se it’s a straigt line to the center.

Assuming that the dogs run at 1m/sec, and room is y x y in diamater.

h^2 = (y/2)^2 + (y/2)^2
h^2 = 2(y/2)^2
h = sqrt(2) * y/2
h = y/sqrt(2) meters

thus it would take the dogs approximtly y/sqrt(2) seconds to catch each other. This is a lower bounds, as the dog will not be traveling in a straight line, but along a curve.

Some Other & Good Aproaches are

Each dog starts at the corner and moving symmetrically. So each dogs start moving perpendicular to the adjacent dogs. Lets assume v.

So each one start moving with v towards the next dog.

If we see realtive speed of the dog1 (v1), w.r.t dog 2, it changes perpendicularly. So it’ll not affect the time taken along the direction of the dog1 to dog2 and the speed will be v only always.

So it they have started at corners with the distance of the length of the square(s).

Time = s/v. They’ll meet at the center.

Another Similar Approach is

Let’s the dogs be A, B, C and D where A is chasing B, B is chasing C, C is chasing D and D is chasing A.
All the dogs will eventually meet in the center of the square. Since all the dogs move in symmetry, the only logical answer to the location of their meeting is the center of the square.
At any point in time, dog A is perpendicular to dog B and B perpendicular to C and so on. Dog A moves towards dog B but dog B does not move towards or away from dog A since it is moving perpendicular to dog A. Therefore, the distance that dog A needs to cover to reach dog B is the same as the original distance between them, one unit.

The speed of each of the dog towards the dog it is chasing is given by (1 + cos(t)) where t is the angle on each corner of the square.

Speed of dog = 1 + cos(90) = 1 + 0 = 1
Time needed = Distance/Speed = 1 / 1 = 1 unit.

A Heavan Puzzle

Josephus Problem - Puzzle

A Barcode Puzzle

Google Puzzle- who keeps the fish?

Facts:*

1: There are 5 villas in 5 different colors
2: In each villa lives a person with a different nationality.
3: These 5 owners drink a certain beverage, smoke a certain brand of cigar
and keep a certain pet.
4: No owner has the same pet, smoke the same brand of cigar or drink the
same drink.


*Hints:*

1: The British lives in a red villa.
2: The Swede keeps dogs as pets
3: The Dane drinks tea
4: The green villa is on the left of the white villa (it also means they are
next door to each other)
5: The green villa owner drinks coffee
6: The person who smokes Pall Mall rears birds
7: The owner of the yellow villa smokes Dunhill
8: The man living in the villa right in the center drinks milk
9: The Norwegian lives in the first villa
10: The man who smokes Blend lives next to the one who keeps cats
11: The man who keeps horses lives next to the man who smokes Dunhill
12: The owner who smokes Blue Master drinks beer
13: The German smokes Prince
14: The Norwegian lives next to the blue villa
15: The man who smokes Blend has a neighbor who drinks water.

*The question is: who keeps the fish?