Project Euler 855
Project Euler 855
题目
Delphi Paper
Given two positive integers \(a,b\), Alex and Bianca play a game in \(ab\) rounds. They begin with a square piece of paper of side length \(1\).
In each round Alex divides the current rectangular piece of paper into \(a \times b\) pieces using \(a-1\) horizontal cuts and \(b-1\) vertical ones. The cuts do not need to be evenly spaced. Moreover, a piece can have zero width/height when a cut coincides with another cut or the edge of the paper. The pieces are then numbered \(1, 2, \dots, ab\) starting from the left top corner, moving from left to right and starting from the left of the next row when a row is finished.
Then Bianca chooses one of the pieces for the game to continue on. However, Bianca must not choose a piece with a number she has already chosen during the game.
Bianca wants to minimize the area of the final piece of paper while Alex wants to maximize it. Let \(S(a,b)\) be the area of the final piece assuming optimal play.
For example, \(S(2,2) = 1/36\) and \(S(2, 3) = 1/1800 \approx 5.5555555556\mathrm {e}{-4}\).
Find \(S(5,8)\). Give your answer in scientific notation rounded to ten significant digits after the decimal point. Use a lowercase e to separate the mantissa and the exponent.
解决方案
把编号视作固定坐标 \((i,j)\)（第 \(i\) 行第 \(j\) 列），其中\(R=\{1,\dots,a\}, C=\{1,\dots,b\}.\)任意时刻可被 Bianca 选择的坐标集合记为 \(S\subseteq R\times C\)。定义：\(A(S)\)表示从状态\(S\)出发（当前面积归一化为1）的最优最终面积；$ r_i(S)=|S({i}C)|, c_j(S)=|S(R)|, n=|S|.$
一轮切割中，Alex 选择行高比例 \(u_1,\dots,u_a\) 和列宽比例 \(v_1,\dots,v_b\)，满足\(\displaystyle u_i\ge0,\sum_{i=1}^a u_i=1, v_j\ge0,\sum_{j=1}^b v_j=1.\) 则坐标 \((p,q)\) 的面积占比为 \(u_pv_q\)。若 Bianca 选 \((p,q)\)，状态变为 \(S\setminus{(p,q)}\)。因此递推为 \[ A(S)=\max_{u,v}\{\min_{(p,q)\in S}\{u_pv_qA(S\setminus\{(p,q)\})\}\}. \tag{1} \]
现在我们的目标是把 \((1)\) 中“删一个点”产生的变化因子标准化。 设 \(G(S)\) 满足 \[ \frac{G(S\setminus\{(p,q)\})}{G(S)}=\frac{n^2}{r_p(S)c_q(S)}. \tag{2} \] 这样把 \(A(S)\) 写成乘积 \(A(S)=G(S)B(S)\) 后，可把递推中的依赖项整齐分离出来。
可见，\(G(S)\)可以写成：
\[ G(S)=\frac{\Big(\prod_{i=1}^a r_i(S)!\Big)\Big(\prod_{j=1}^b c_j(S)!\Big)}{(n!)^2}. \tag{3} \]
那么由 \((1)\)、\((2)\) 得 \[ B(S)=\dfrac{A(S)}{G(S)}=\max_{u,v}\left\{\min_{(p,q)\in S} \left\{\frac{n^2u_pv_q}{r_p(S)c_q(S)}B(S\setminus\{(p,q)\})\right\}\right\}. \tag{4} \]
下面证明 \(B(S)\equiv 1\)（对所有 \(S\)）。
基础情形：\(S=\varnothing\) 时，游戏结束，\(A(\varnothing)=1\)；由 \((3)\) 也有 \(G(\varnothing)=1\)，故\(B(\varnothing)=1.\)
归纳步骤：设对所有真子集 \(T\subsetneq S\) 都有 \(B(T)=1\)。令 \(n=|S|>0\)，则 \((4)\) 化为 \[ B(S)=\max_{u,v}\left\{\min_{(p,q)\in S}\left\{\frac{n^2u_pv_q}{r_pc_q}\right\}\right\}. \tag{5} \]
首先证明上界：\(B(S)\le1\)。
对任意正数集，\(\min \le\)几何平均总成立，故\(\displaystyle\min_{(p,q)\in S}\frac{n^2u_pv_q}{r_pc_q}\le\left(\prod_{(p,q)\in S}\frac{n^2u_pv_q}{r_pc_q}\right)^{1/n}.\)右侧整理为\(\displaystyle n^2\left(\prod_{(p,q)\in S}\frac{u_p}{r_p}\right)^{1/n}\left(\prod_{(p,q)\in S}\frac{v_q}{c_q}\right)^{1/n}.\)
再分别对两项用 AM-GM 不等式（把 \(u_p/r_p\) 视作重复 \(r_p\) 次）：\(\displaystyle\left(\prod_{(p,q)\in S}\frac{u_p}{r_p}\right)^{1/n}\le\frac1n\sum_{(p,q)\in S}\frac{u_p}{r_p}= \frac1n\sum_{p:r_p>0}u_p\le \frac1n,\)同理\(\displaystyle\left(\prod_{(p,q)\in S}\frac{v_q}{c_q}\right)^{1/n}\le\frac1n.\)故\(\displaystyle\min_{(p,q)\in S}\frac{n^2u_pv_q}{r_pc_q}\le n^2\cdot\frac1n\cdot\frac1n=1.\) 对任意 \(u,v\) 都成立，故 \(B(S)\le1\)。
接下来证明下界：\(B(S)\ge1\)。
取\(u_i=\dfrac{r_i}{n}, v_j=\dfrac{c_j}{n}.\)则对任意 \((p,q)\in S\)，\(\dfrac{n^2u_pv_q}{r_pc_q}=\dfrac{n^2\cdot(r_p/n)\cdot(c_q/n)}{r_pc_q}=1.\) 因此 \((5)\) 的最小值恰为 1，故 \(B(S)\ge1\)。
上下界合并：\(B(S)=1\)。归纳完成。于是 \[ A(S)=G(S)=\frac{\Big(\prod_{i=1}^a r_i(S)!\Big)\Big(\prod_{j=1}^b c_j(S)!\Big)}{|S|!^2}. \tag{6} \]
初始 \(S_0=R\times C\)，故\(r_i(S_0)=b(1\le i\le a), c_j(S_0)=a(1\le j\le b), |S_0|=ab.\)代入 \((6)\)，得到：
\[ S(a,b)=A(S_0)=\frac{(b!)^a(a!)^b}{((ab)!)^2}. \tag{7} \]
代码
1 | from tools import Factorizer |