单交叉 2

Single-Cross 2

专题: Discrete Math / 离散数学
难度: L6
来源: Jane Street

个人笔记

题目详情

这是 Single-Cross 的三维推广。题目在三维空间中随机放置长度固定的线段，研究线段发生一次交叉的概率，并要求给出满足题目条件的数值答案。

英文原题

Consider 3-space (i.e. R³) partitioned into a grid of unit cubes with faces defined by the planes of all points with at least one integer coordinate. For a fixed positive real number D, a random line segment of length D (chosen uniformly in location and orientation) is placed in this cubic lattice.

What length D maximizes the probability that the endpoints of the segment lie in orthogonally adjacent unit cubes (that is, the segment crosses exactly one integer-coordinate plane), and what is this maximal probability? Give your answer as a comma-separated pair of values to 10 significant places (e.g. “1.234567891,0.2468135792”).

解析

这是三维版 Single Cross。对长度 $D\le1$ 的情形，精确计算单次交叉概率可化为一个球坐标二重积分，并进一步化简为 $\frac{1}{4\pi}D(-16D+3D^2+6\pi)$ 。该函数在 $D=(16-\sqrt{256-54\pi})/9\approx0.7452572091$ 处取局部最大值，概率约为 $0.5095346021$ 。

英文解析

August’s puzzle was a three dimensional throwback to Single Cross from three years ago. Careful computation determined that for lengths D <= 1, the probability of a single cross comes to the pleasantly symmetric spherical coordinate double integral. (As seen above.)

This double integral miraculously simplifies to (1/(4π))*D(-16D + 3D^2 + 6π). This function has a local maximum at D = (16 - sqrt(256 - 54π))/9 ~ 0.7452572091, with value ~ 0.5095346021. The argument that there can’t be a second higher local maximum with D > 1 is left to the puzzler.

Congrats to this month’s solvers who successfully completed the optimal length and probability!