Points in a Rectangle

Question

I was asked this question in an interview, so I am not sure what the optimal answer is. But here it goes:

Given a rectangle with length l and breadth b, I pick 4 random points inside it. What is the probability that the 4 points lie in the same half of the rectangle?

Notes:

1. Two halves of the rectangle are defined by a single line passing through the intersection of its diagonals. So the rectangle cannot be divided into two halves of any arbitrary shapes of equal length.
2. A line passing through a picked point and the center does not contain another picked point. That is, A line passing through any two picked points does not pass through the center of the rectangle (= intersection of the diagonals).

Addition: (Maybe a Hint)

I was asked about 3 points first. They saw my approach and were satisfied and then asked me what if there were 4 points.

Answer

9/16

The one to prove it gets the check mark.

Answer 1

Well, after seeing the solution I guess I have a proof for the question.

Like many others earlier, the probability for the first and the second points to lie on the same half is $1$. I would not get into that as it is already shown by other.

Now we know that the 1st and the second points will always lie in the same half. Considering the 3rd point, lets define the worst case as when the probability of the 3rd point to lie in the same half is minimal, and best case when the probability of the 3rd point lying on the same half is maximum.

Worst Case:

In this case the probability of point $p_3$ lying in the same half is almost $0.5$.

Best Case:

In this case the probability of point $p_3$ lying in the same half is almost $1.0$.

Now comes a little complicated part. Consider the "separating line" is changing it's slope continuously by a very small amount. In that case the two halves will keep changing shapes. It's important to notice that in the intervals of $180$ degrees and $360$ degrees the all the halves are taken into consideration and since the halves can be defined by any "separating line", we can safely say that the probability of the point $p_3$ will increase uniformly from worst case to best case. That is, uniformly from $0.5$ to $1.0$.
Thus, the overall probability of point $p3$ lying in the same half will be
$(1.0 + 0.5) \div 2 = \frac{3}{4}$

Similarly, for the point $p_4$, it's not difficult to see that the worst case and best case probability to lie in the same half would be the same as point $p_3$, that is, $0.5$ and $1.0$ respectively. And, the overall probability would be the same as well, i.e. $\frac{3}{4}$.

Now, the easy part. The overall probability of the $4$ points lying in the same half would be: $\frac{3}{4} \times \frac{3}{4} = \frac{9}{16}$

Thus, proved. Thanks for the check mark in advance :P.

Please correct me if you think I am wrong.

Answer 2

My answer is

$\frac12$

We can obtain a general formula for $n$ with a simple idea.
You have $n$ points inside the rectangle. Now you choose one (there are $n$ choices) and draw a line passing through it and the centre, determining two halves. Now, what's the probability that each point is in the same half of the previous? Of course it is $\frac12$ for each point! Now, we have all we need to deduce a general formula:

$p(n)=n\times (\frac12)^{n-1}=\frac{n}{2^{n-1}}$.

Obviously, we have $p(1)=1$ and $p(2)=1$.
We can also observe that $p(3)=\frac34$ and $p(4)=\frac12$.

You may say: "Hey, but there are infinite halves that contain one point! Why did you choose the one passing through the point itself?"
I did because that's the limit case! If you don't think so, check the pictures below. The yellow area shows all the valid halves given $n$ points. As you can see, the yellow area is delimited by lines passing through the points themselves!

Additional note: when you draw a line, you're actually drawing 2 vectors, with opposite direction. Each vector represents one of the two halves. That is, the above formula is actually the simplification of $p(n)=n\times (\frac12)^{n-2}\times2$

Answer 3

The answer is heavily based on this and I've tried to simplify it a bit.

And is:

0.5

Basically the solutions is:

Let one of the points lie on the "rectangle separator". From there on, we want all other points to be on the same halfplane. Picking a point we practically make "coinflip" on which side will the point land (this is correct as the two halves have equal area). So we get $1/2^{n-1}$ for each separator point. Since the separator can be anywhere (in terms of rotation around the diagonal intersection point), trying out which point lies on the separator are disjoint events. So we sum that up for all separators getting $n/2^{n-1}$.

This results in:

$4/2^{4-1} = 0.5$

Also, we can do a "sanity check" that for 1 and 2 the answer is 1.

Alternatively, one can try to get the odds that 4 points do not lie in the same half. Will write that up later.

Answer 4

Similar to leoll2's answer, but with a different explanation.

Now, the first 1 and 2 points places can always be on the same half since they would define a line itself. So there is a 100% chance that 2 points can be on the same half.

Now if we added a third point things get slightly more interesting. Here the third point can be on a part where we would not be able to divide the rectangle in half (the red area in picture). There is a 1/4 probability for this, or rather 3/4 that it is on the same half. (If the points are the closest to the lower right corner) In the extreme case where the points are on the line, there is a 100% chance the third dot is the same half.

The red dots are in the most extreme position(s).

Now assuming that the third dot is on the same half, there is are two locations, the blue area and the green area. If it was in the blue area, then again for the 4th dot, there would be a 3/4 chance of being on the same half. [green + blue area]

If the third dot was in the green area, then there is only 1/2 chance of the 4th dot being on the same half.

So green has (2/4) [(1/8) * 4] for the third point, and (1/2) for the fourth point.

And blue has 2/8 [(1/8) * 2] for the third point, and then 3/4 for the fourth.

Expanded we get (2/4)*(1/2)+[(1/8)*(3/4)+(1/8)*(3/4)] = 0.5
So there is a 50 percent chance that the 4 points are on the same half.

I realize now that it can be dealt with in quarters, but I didn't feel like changing the picture again.

Answer 5

The first point can fall anywhere. Divide the area into quarters arbitrarily and the second point can fall either in the same half (1/2 chance) in the same quarter (1/4 chance) or in the opposite quarter.

If the second point falls in the opposite quarter (1/4 chance) there is a 1/2 chance that a different division of the board would result in the points sharing a half (resulting 1/8 chance for each outcome.)*

This results in four possible outcomes for the second point:

1/4 - same quarter

5/8 - same half 1/2 + 1/8

1/8 - opposite quarters

The simplified 3 point problem yields this probability tree:

A      B
1/4 -> 1/4 = 1/16
5/8 -> 1/2 = 5/16
1/8 -> 1   = 2/16
          += 7/16 probability of failure, of success 9/16

A : Chance of second point falling in 1. Same quarter 2. Adjacent quarter 3. Opposite quarter.

B : Chance of failure, third point falls in the other half to existing points.

Extending to the main 4 point problem:

A      B**      C
1/4 -> 1/4 -> 1/4 = 1/64
       5/8 -> 1/2 = 5/64
       1/8 -> 1   = 2/64

5/8 -> 1/2 -> 1/2 = 10/64
    -> 1/2 -> 1   = 20/64

1/4 -> 1   -> 1   = 16/64

                 += 54/64 probability of failure, of success  10/64

**In the scenario with 4 points stage B may be a repeat of stage A if the first two points fell in the same quarter or may be a 1/2 chance of failure

C: Chance of failure, fourth point in the other half to existing points.

*Yet to be proven.

Answer 6

My answer is

0.125

That's why:

The probability of the 1st point be picked in one of the 2 halves is, obviously, 1 => partial probability = 1
The probability of the 2nd point be picked in the same half is 0.5 => partial probability = 1 × 0.5
The probability of the 3rd point be picked in the same half is 0.5 => partial probability = 1 × 0.5 × 0.5
The probability of the 4th point be picked in the same half is 0.5 => total probability = 1 × 0.5 × 0.5 × 0.5 = 0.125