IBM Ponder This #284 · 2021 年 12 月

传统高尔顿板用逐层分叉的钉子将球随机导向底部格子。九格示例有八层钉子：

落入中间格需要八次左右选择各四次，共 $(\genfrac{}{}{0ex}{}{8}{4})=70$ 种，而全部选择有 $2^8=256$ 种，所以概率约为 $0.272$。

现在把钉子改为确定性：L 把球导向左后变成 R，R 导向右后变成 L；还可使用永久向左的 < 与永久向右的 >：

有 $n$ 个底格，依次投入 $m$ 个球，最后得到数量分布 $a_1,a_2,\dots ,a_n$，满足 $a_1+\cdots +a_n=m$。给定 $n$ 元置换 $\sigma \in S_n$，依赖于 $\sigma$ 的得分定义为 $\prod _{k=1}^n(\frac{n\cdot a_{\sigma (k)}}{m}{)}^k$。

已知格数 $n$ 及置换 $\sigma$，可选择初始钉子状态以最大化得分。状态用长为 $\frac{n(n-1)}{2}$ 的 L、R、<、> 字符串表示，从顶端一颗开始，逐行至底层 $n-1$ 颗；置换 $\sigma$ 写为 $[\sigma (1),\sigma (2),\dots ,\sigma (n)]$。

例如 $n=5$、$m=15$ 时，RRRRRLLRLR 产生 [1,3,6,4,1]，置换 [1,2,5,4,3] 下得分约为 1.25。

任务：$n=9$、m=150、置换 [5,6,4,7,3,8,2,9,1] 时，构造得分至少为 5 的初态。

附加问题：n=10、m=150、置换 [4,8,2,7,10,6,3,9,1,5] 时，达到至少 20 分。

解答

认真尝试后再打开

待补充。