17
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are the points picked first, and then the separator line is placed with the intent to get all points on one side? If the separator line is placed after the points, it is obvious that an angle can always be chosen, so that any constellation of points is divided between both halfs. $\endgroup$ – jarnbjo May 18 '15 at 11:09
  • 1
    $\begingroup$ You are missing the point here. The "separator line" is not picked anytime, but the points just have to lie on the same half. $\endgroup$ – Dipped Bits May 18 '15 at 11:17
  • 1
    $\begingroup$ @DippedBits: But the definition of "same half" depends on the angle of the separator line. You specify that the separator must pass through the intersection of the diagonals in the rectangle, but not at which angle. Is the angle fixed before the points as picked, or is the angle chosen after the points have been picked, so that an optimal angle can be used to try to get all points on one side of the separator? $\endgroup$ – jarnbjo May 18 '15 at 12:02
  • 1
    $\begingroup$ @jarnbjo : You are still taking the wrong approach to the problem. Lets say the 4 points chosen are very close to each other. Then in that case there will be infinite "separator lines" defining the two halves of the rectangle. They just have to lie in one half of the rectangle, it doesn't matter what the angle of the separator line is. Don't focus on the separator line, just focus on the halves and whether the points belong in the same half. $\endgroup$ – Dipped Bits May 19 '15 at 2:50
  • 2
    $\begingroup$ @DippedBits I don't see any wrong approach; probably you don't understand jarnbjo's point. "Lets say the 4 points chosen are very close to each other. Then in that case there will be infinite "separator lines" defining the two halves of the rectangle. They just have to lie in one half of the rectangle, it doesn't matter what the angle of the separator line is." In other words, yes, the points are chosen first, and then after the points are known it is checked whether there is a separator line for which all points lie on the same half. $\endgroup$ – JiK May 19 '15 at 8:26
3
$\begingroup$

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:
enter image description here
In this case the probability of point $p_3$ lying in the same half is almost $0.5$.

Best Case:
enter image description here
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.

$\endgroup$
  • $\begingroup$ nicely done. +1 $\endgroup$ – Dipped Bits May 28 '15 at 13:40
8
$\begingroup$

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! enter image description here

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$

$\endgroup$
  • 1
    $\begingroup$ If two points are picked at random, there will typically be many ways to divide the table in half so that both points lie on the same half. For three points to lie on the same half, we need to be able to find some half containing the first two that also contains the third. So the probability for three points should be somewhat larger than $1/2$, and similarly for four points the probability should be larger than $1/4$. $\endgroup$ – Julian Rosen May 18 '15 at 14:35
  • $\begingroup$ What if the first two points chosen are very close to each other? Will the probability of the third still be 1/2? $\endgroup$ – Dipped Bits May 19 '15 at 2:43
  • $\begingroup$ @leoll2 you are assuming that the first two points lie at an angle close to 180 degrees with respect to each other and the center. what if the angle was just over 0 degrees? Your approach is correct just need to consider 'all' the cases. $\endgroup$ – Dipped Bits May 19 '15 at 2:55
  • 1
    $\begingroup$ @zlobi.wan.kenobi The size of the rectangle is independent of the probability since there will always be an infinite number of possible locations to put the points (i.e [0.0001, 0.0001]) in a LxW rectangle. So the size doesn't matter. $\endgroup$ – Mark N May 21 '15 at 12:05
  • 1
    $\begingroup$ I get the same answer, is the question wrong when it says 9/16? $\endgroup$ – Ewan May 21 '15 at 15:44
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd say explicitly that we consider only the half that is on, say, the left side of the separator when looked from the point to the centre. Otherwise, there are two ways to choose a rectangle separator so that all points are on the same side of that separator. $\endgroup$ – JiK May 19 '15 at 12:25
1
$\begingroup$

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.

enter image description here
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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The probability of two points being in the same half is 1. Draw a line through the center and one of the two points. Choose the half that contains the other point. $\endgroup$ – LeppyR64 May 19 '15 at 11:38
  • $\begingroup$ You are drawing the line after the points are picked, which is not the intention of the puzzle. My answer tells the probability of picking the points after the rectangle is divided in 2 halves. In this case, it doesn't matter how the rectangle was divided in 2 halves (either by straight lines or curved lines, etc...). The puzzle is about picking points (and probability) and not about drawing a line. $\endgroup$ – aljodAv May 19 '15 at 20:03
  • $\begingroup$ There is no line at all. The probability of two points existing in the same half is 1 because the half can be on any arbitrary line that passes through the intersection of the diagonals. $\endgroup$ – LeppyR64 May 19 '15 at 20:57
  • $\begingroup$ There is no line at all: In your 1st post you say there's a line, now you say there's no line at all. What you say in the post above is not true, unless you draw a line after the 2 points are already determined inside the rectangle. Read the original post and conclude yourself that there's no line drawn after the 1st 2 points are determined inside the rectangle. The puzzle is like this: imagine a rectangle divided in 2 halves (it doesn't matter if by a staright line or by a curved line, as long as the 2 halves are equal). Then, pick 4 points etc... $\endgroup$ – aljodAv May 20 '15 at 3:05
  • 3
    $\begingroup$ Moderator note: Several comments removed. @aljodAv - please remember to follow our Be Nice policy and not post vitriolic or otherwise unconstructive comments. $\endgroup$ – Doorknob May 20 '15 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.