Project Euler 695
Project Euler 695
题目
Random Rectangles
Three points, \(P_1\), \(P_2\) and \(P_3\), are randomly selected within a unit square. Consider the three rectangles with sides parallel to the sides of the unit square and a diagonal that is one of the three line segments \(\overline{P_1P_2}\), \(\overline{P_1P_3}\) or \(\overline{P_2P_3}\) (see picture below).
We are interested in the rectangle with the second biggest area. In the example above that happens to be the green rectangle defined with the diagonal \(\overline{P_2P_3}\).
Find the expected value of the area of the second biggest of the three rectangles. Give your answer rounded to \(10\) digits after the decimal point.
解决方案
我们假设随机取三点为\(P_i=(x_i,y_i)(i=1,2,3)\)。对每一对点 \(P_i,P_j\)，作一条对角线为 \(\overline{P_iP_j}\)，对应该矩形面积为 \(A_{ij}=|x_i-x_j|\cdot|y_i-y_j|.\)
三条线段对应三块矩形面积 \({A_{12},A_{13},A_{23}}\)。题目要的是三者中第二大的期望值，即三者的中位数： \(\mathbb E[M],M=\mathrm{median}(A_{12},A_{13},A_{23}).\)
分别看三点的 \(x\) 坐标与 \(y\) 坐标的极值：\(x_{\min}=\min(x_1,x_2,x_3),x_{\max}=\max(x_1,x_2,x_3),y_{\min}=\min(y_1,y_2,y_3),y_{\max}=\max(y_1,y_2,y_3).\)三点的轴对齐外接矩形是\(B=[x_{\min},x_{\max}]\times[y_{\min},y_{\max}],S(B)=(x_{\max}-x_{\min})(y_{\max}-y_{\min}).\)
对外接矩形做仿射归一化（把 \(B\) 拉伸到单位正方形）：\(u=\dfrac{x-x_{\min}}{x_{\max}-x_{\min}},v=\dfrac{y-y_{\min}}{y_{\max}-y_{\min}}.\)任意两点在 \(u\) 方向的距离会被缩放 \(x_{\max}-x_{\min}\)，在 \(v\) 方向的距离会被缩放 \(y_{\max}-y_{\min}\)，因此每个矩形面积都整体乘上同一个比例：\(A_{ij}=(x_{\max}-x_{\min})(y_{\max}-y_{\min})\cdot \widetilde A_{ij},\)其中 \(\widetilde A_{ij}\) 是归一化后在单位正方形里的对应面积。于是中位数也同样缩放：\(M=S(B)\cdot \widetilde M.\)并且由于 \(x\) 与 \(y\) 独立，外接矩形的尺度与归一化后的形状（由相对次序决定）可以分开处理，最终\(\mathbb E[M]=\mathbb E[S(B)]\cdot \mathbb E[\widetilde M].\)
对三个独立均匀 \([0,1]\) 的变量，设最大值为 \(X_{(3)}\)，最小值为 \(X_{(1)}\)。用尾积分可得：
\[\mathbb E[X_{(3)}]=\int_0^1 \mathbb P(X_{(3)}\ge t),dt=\int_0^1 \bigl(1-t^3\bigr),dt=\frac34,\mathbb E[X_{(1)}]=\int_0^1 \mathbb P(X_{(1)}\ge t),dt=\int_0^1 (1-t)^3,dt=\frac14.\]
因此三点在 \(x\) 方向的期望跨度为\(\mathbb E[x_{\max}-x_{\min}]=\dfrac34-\dfrac14=\dfrac12.\)
同理 \(\mathbb E[y_{\max}-y_{\min}]=\dfrac12\)。并且 \(x\) 系列与 \(y\) 系列独立，所以\(\mathbb E[S(B)]=\mathbb E[x_{\max}-x_{\min}]\cdot \mathbb E[y_{\max}-y_{\min}]=\dfrac12\cdot\dfrac12=\dfrac14.\)
不妨按 \(x\) 坐标给点重新编号，使 \[ x_1<x_2<x_3. \] 此时 \((y_1,y_2,y_3)\) 的相对大小次序共有 \(3!=6\) 种且等概率。
- 若 \(y\) 的次序与 \(x\) 同向（\(y_1<y_2<y_3\)）或反向（\(y_1>y_2>y_3\)），那么外接矩形的两个对角点恰好由 \(P_1\) 与 \(P_3\) 占据，\(P_2\) 在内部。这类共 2 种排列，所以概率 \(2/6=1/3\)。
- 其余 4 种排列属于“交叉”情形：只有一个点占据外接矩形的一个角，另外两个点分别落在与该角相对的两条边上（归一化后可视作在上边与右边）。概率 \(4/6=2/3\)。
因此 \[ \mathbb E[\widetilde M]=\frac13 I_1+\frac23 I_2, \] 其中 \(I_1,I_2\) 是两种类型在归一化单位正方形内的中位数面积期望。
首先计算\(I_1\)，对于这种情况，归一化后可设两个角点为 \((0,0)\) 与 \((1,1)\)，第三点为 \((x,y)\)，且 \((x,y)\) 在单位正方形内均匀分布。三条对角线对应矩形面积为：\(\widetilde A_{13}=1,\widetilde A_{12}=xy,\widetilde A_{23}=(1-x)(1-y).\)其中 \(1\) 永远最大，因此中位数就是\(\widetilde M=\max\bigl(xy,(1-x)(1-y)\bigr).\)比较两者：\(xy\ge (1-x)(1-y)\iff xy\ge 1-x-y+xy\iff x+y\ge 1.\)
于是
\[ I_1=\int_0^1\int_0^1 \max(xy,(1-x)(1-y))dydx. \]
利用对称替换 \((x,y)\mapsto(1-x,1-y)\)，两部分贡献相等，因此
\[ I_1=2\int_0^1\int_{1-x}^1 xydydx =2\int_0^1 x\cdot\left[\frac{y^2}{2}\right]_{1-x}^1 dx =2\int_0^1 x\cdot\frac{1-(1-x)^2}{2}dx. \]
化简 \(1-(1-x)^2=2x-x^2\)，得
\[ I_1=\int_0^1 (2x^2-x^3)dx =\left[\frac{2x^3}{3}-\frac{x^4}{4}\right]_0^1 =\frac{2}{3}-\frac{1}{4} =\frac{5}{12}. \]
接下来计算\(I_2\)，对于这种情况，归一化后可设占角点为 \((0,0)\)，另外两点分别在上边与右边：\(P_a=(x,1), P_b=(1,y), x,y\sim U(0,1),\)并且\(x\)和\(y\)是独立的。那么三块矩形面积变为\(\widetilde A_1 = x,\widetilde A_2 = y,\widetilde A_3 = (1-x)(1-y).\) 所以
\[ I_2=\int_0^1\int_0^1 \mathrm{median}\left(x,y,(1-x)(1-y)\right)dydx. \]
被积函数对交换 \(x\leftrightarrow y\) 对称，因此
\[ I_2 = 2\int_{0}^{1}\int_{0}^{x} m(x,y)dydx, m(x,y)=\mathrm{median}\left(x,y,(1-x)(1-y)\right). \]
在该三角形中 \(y\le x\)。设\(z=(1-x)(1-y).\)此时中位数的三种可能：若 \(x\le z\)，则排序 \(y\le x\le z\)，中位数为 \(x\)；若 \(z\le y\)，则排序 \(z\le y\le x\)，中位数为 \(y\)；否则 \(y<z<x\)，中位数为 \(z\)。
有如下2条边界曲线：\(x=z \iff (1-x)(1-y)=x \iff y=\dfrac{1-2x}{1-x},y=z \iff (1-x)(1-y)=y \iff y=\dfrac{1-x}{2-x}.\) 令\(f(x)=\dfrac{1-2x}{1-x},g(x)=\dfrac{1-x}{2-x}\)两曲线与对角线 \(y=x\) 的交点由 \(x=g(x)\) 给出：\(x=\frac{1-x}{2-x}\iff x(2-x)=1-x\iff x^2-3x+1=0,\)在 \([0,1]\) 内的根为\(\alpha=\dfrac{3-\sqrt5}{2}.\)并且可检验：在 \(x\in[\alpha,1/2]\) 上有 \(0\le f(x)\le g(x)\le x\)，而在 \(x\in[1/2,1]\) 上恒有 \(x>z\)，只剩 \(y\) 与 \(z\) 的比较。
因此三角形区域可分解为五块（对应下面的五个积分）：
- \(x\in[0,\alpha],y\in[0,x]\)：中位数为 \(x\)。
- \(x\in[\alpha,1/2],y\in[0,f(x)]\)：中位数为 \(x\)。
- \(x\in[\alpha,1],y\in[g(x),x]\)：中位数为 \(y\)。
- \(x\in[\alpha,1/2],y\in[f(x),g(x)]\)：中位数为 \(z=(1-x)(1-y)\)。
- \(x\in[1/2,1],y\in[0,g(x)]\)：中位数为 \(z\)。
于是 \[ \frac{I_2}{2} =\int_{0}^{\alpha}\int_{0}^{x} xdydx +\int_{\alpha}^{1/2}\int_{0}^{f(x)} xdydx +\int_{\alpha}^{1}\int_{g(x)}^{x} ydydx +\int_{\alpha}^{1/2}\int_{f(x)}^{g(x)} (1-x)(1-y)dydx +\int_{1/2}^{1}\int_{0}^{g(x)} (1-x)(1-y)dydx. \]
计算后可化简得到：
\[ I_2=\frac{11\sqrt5-23}{12}+\log\left(\frac{3+\sqrt5}{4}\right). \]
由\(\mathbb E[\widetilde M]=\dfrac13 I_1+\dfrac23 I_2.\)和原问题所求\(\mathbb E[M]=\mathbb E[S(B)]\cdot \mathbb E[\widetilde M]=\dfrac14\left(\dfrac13 I_1+\frac23 I_2\right)=\dfrac{I_1+2I_2}{12}.\)代入 \(I_1=\dfrac{5}{12}\) 与上面的 \(I_2\)，整理得最终闭式：
\[ \mathbb E[M] =-\frac{41}{144} +\frac{11\sqrt5}{72} +\frac16\log\left(\frac{3+\sqrt5}{4}\right) \]
代码
1 | from math import log, sqrt |