环上的点:一个流行的数学问题的互动讲解
Points on a ring: An interactive walkthrough of a popular math problem

原始链接: https://growingswe.com/blog/points-on-ring

这段文字探讨了一个反直觉的概率问题:四个随机放置在圆上的点全部落在同一半圆内的概率是多少? 初步的推论认为概率为12.5% (1/8),基于每个点有50%的几率落在给定的半圆内。然而,模拟显示实际概率更接近50%。 关键在于认识到半圆并非固定的。问题不是点是否适合*某个*特定的半圆,而是是否能找到*某个*半圆包含所有点——有效地允许半圆“旋转”并以四个点中的任意一个点为锚点。 正确的计算方法是考虑每个点作为潜在的锚点。所有其他点落在从该锚点开始的顺时针半圆内的概率是1/8。由于有四个可能的锚点,并且这些事件互斥,总概率为4 * (1/8) = 1/2 或 50%。这个原理可以扩展到球体和更高维度,N个随机点落在半球内的概率为N/2^(N-1)。

黑客新闻 新 | 过去 | 评论 | 提问 | 展示 | 招聘 | 提交 登录 环上的点:一个流行的数学问题的互动演示 (growingswe.com) 9 分,由 evakhoury 1小时前发布 | 隐藏 | 过去 | 收藏 | 讨论 帮助 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 申请YC | 联系 搜索:
相关文章

原文

Thinking about my undergrad days studying math, I wish I more problems were visualized like this

N=4 N=5 N=3 N=6 N=4 N=5

Here's a problem that shows up in math competitions and quant interviews:

Drop 4 points randomly on a circle. What are the chances they all land in the same half?

click drop to place points

Try it a few times. Sometimes all four cluster into one semicircle, sometimes they spread out. What probability would you guess?

The obvious (wrong) answer

The circle is symmetric, so place one point anywhere and ask whether the other three land in the same semicircle. Each of those 3 points independently has a 1/21/2 chance of landing in that half, so the probability should be (1/2)3=1/8=12.5%(1/2)^3 = 1/8 = 12.5\%

Test that reasoning here. Click on the circle to fix your point, then drop 3 more and see whether they land in your semicircle. Repeat it many times and watch the rate:

click on the circle to fix your point

The rate hovers around 12.5%. The reasoning checks out for a fixed semicircle. But go back to the first demo and drop 4 points a bunch of times. The rate there is closer to 50%, not 12.5%. Something is off.

The semicircle is not fixed

We are not asking "do the points fit in this particular semicircle?" We are asking "do the points fit in any semicircle?" The semicircle gets to move. It can be anchored at whichever point makes it work.

Drop 4 points below and click each one to try anchoring a semicircle there. Notice that at most one anchor ever works:

Fixing the semicircle in advance ignores configurations where the points do cluster together, just not around the chosen anchor. The real question is whether some point is a valid anchor. That is a much more generous condition.

Anchoring at each point

Label the 4 points 1,2,3,41, 2, 3, 4

Ei="all other points lie in the clockwise semicircle starting at point i"E_i = \text{"all other points lie in the clockwise semicircle starting at point } i\text{"}

We already know the probability of each individual event. Once point ii is the anchor, each of the other N1N - 1

P(Ei)=(12)N1P(E_i) = \left(\frac{1}{2}\right)^{N-1}

For 4 points, that is (1/2)3=1/8(1/2)^3 = 1/8

The points all fit in some semicircle exactly when at least one of these events occurs. We want the probability of the union E1E2ENE_1 \cup E_2 \cup \cdots \cup E_N

N×12N1N \times \frac{1}{2^{N-1}}

For N=4N = 4

Only one anchor ever works

Go back to the anchor picker and try clicking different points. Whichever anchor's semicircle contains all the others, click the remaining points. Their semicircles always miss somebody.

Place points below and click one to see its semicircle. Watch the gap (the empty arc going counterclockwise from the farthest point back to the anchor):

When EiE_i

Step through this argument on concrete points:

At most one EiE_i

P(all in some semicircle)=i=1NP(Ei)=N12N1=N2N1P(\text{all in some semicircle}) = \sum_{i=1}^{N} P(E_i) = N \cdot \frac{1}{2^{N-1}} = \frac{N}{2^{N-1}}

For 4 points: 4/8=1/24/8 = 1/2

Checking the formula

The formula predicts that any two points always fit in a semicircle (N=2N = 2

NNP(all in semicircle)P(\text{all in semicircle})Decimal
22/2=12/2 = 1100%
33/43/475%
44/8=1/24/8 = 1/250%
55/165/1631.25%
66/32=3/166/32 = 3/1618.75%
1010/51210/5121.95%

Adjust NN and run batches. The simulated rate converges to the prediction:

Smaller arcs

Nothing in the argument required the arc to be a semicircle. If the arc has length xx times the circumference (where x1/2x \leq 1/2

P(all N points in some arc of length x)=NxN1P(\text{all } N \text{ points in some arc of length } x) = N \cdot x^{N-1}

Adjust the arc size and number of points:

For example, 5 points all fitting in an arc covering 1/31/3 of the circumference: 5×(1/3)4=5/816.2%5 \times (1/3)^4 = 5/81 \approx 6.2\%

Beyond the circle

The same decomposition works in higher dimensions. For NN random points on a sphere, the probability they all lie in a hemisphere is also N/2N1N / 2^{N-1}

联系我们 contact @ memedata.com