P121: 碟子游戏奖金

# P121: 碟子游戏奖金

Disc game prize fund

一开始, 包里装有一个红色碟子和一个蓝色碟子.

在一场概率游戏中, 每一轮玩家从包中取出一个碟子, 记录下其颜色, 随后将碟子放回包中, 并在包中加入一个红色碟子, 再进行下一轮.

玩家需要付 $￡$ 来玩这个游戏, 如果他们在游戏结束时拿出的蓝色碟子数比红色碟子数更多, 则获得胜利.

如果游戏进行轮, 那么玩家获胜的概率是 , 因此游戏所设定的最高奖金为 $￡$ , 否则可能会造成亏损.

注意奖金必须是整数, 而且包含了玩家付出用于玩游戏的 $￡$ , 也就是说玩家实际上赢得的数额是 $￡$ .

如果游戏进行轮, 求游戏所设定的最高奖金.

首先, 抽了遍之后抽到蓝色碟子的概率为 ;

令表示抽了次后, 蓝色碟子的数量为的概率:

然后加上边界条件即可:

p[m_, 0] := 1;
p[m_, n_] := (p[m - 1, n - 1] + m p[m - 1, n])/(m + 1) /; m > n
p[n_, n_] := 1/Product[i, {i, n + 1}]
f[n_] := Floor[1/p[n, Quotient[n, 2] + 1]]
f[15]

当然这东西其实是可以解出来的, 实际上 , 其中是第一类斯特林数.

f[n_] := Floor[(n + 1)!/Tr@Abs@Table[StirlingS1[n + 1, k + 1], {k, Ceiling[(n + 1)/2], n}]];

21:26

# P122: 高效指数计算

Efficient exponentiation

计算最朴素的方式需要次乘法:

但使用一个 "二进制" 的算法, 你可以只用 6 次乘法:

然而, 实际上仅用 5 次乘法也是可以的:

记是计算所需要的最少次数, 例如 .

对于 , 求 .

哈哈, 著名坑题, 这个问题是无法 DP 求解的, 因为不满足最优子结构.

这种东西只能暴搜, 所以刷题的话不如查表.

Wiki: Addition Chain
OEIS: A003313

Tr@Import["https://oeis.org/A003313/b003313.txt", "Data"][[;; 200, 2]]

14:28

# P123: 素数平方余数

Prime square remainders

记是第个素数, 记是被除所得的余数.

例如, 当时, , 而 .

使余数首次超过的最小值是 .

求使余数首次超过的最小值.

数竞常规题.

直接对二项式展开:

显然:

当为奇数时，余数恒为，
当为偶数时，余数为

所以把奇数遍历一遍就行了:

NestWhile[# + 2 &, 1, Mod[2 # Prime[#], Prime[#]^2] < 10^10 &]

我第一遍提交了个偶数, 然后看见大叉还愣了一下, 好半天才回过神来这肯定是奇数.

12:53

# P124: 基排序

TIP

数 n 的基 rad(n), 是指 n 的不同质因数之积. 例如, 504 = 2^3 × 3^2 × 7, 所以 rad(504) = 2 × 3 × 7 = 42.

如果我们计算 1 ⩽ n ⩽ 10 的 rad(n), 并先按照 rad(n) 再按照 n 从小到大排序, 我们得到:

| | ** 排序前 ** | | | ** 排序后 ** | | | --- | ------------ || ----- | ---------- | ----- | | n | rad(n) | | n | rad(n) | k | | 1 | 1 | | 1 | 1 | 1 | | 2 | 2 | | 2 | 2 | 2 | | 3 | 3 | | 4 | 2 | 3 | | 4 | 2 | | 8 | 2 | 4 | | 5 | 5 | | 3 | 3 | 5 | | 6 | 6 | | 9 | 3 | 6 | | 7 | 7 | | 5 | 5 | 7 | | 8 | 2 | | 6 | 6 | 8 | | 9 | 3 | | 7 | 7 | 9 | | 10 | 10 | | 10 | 10 | 10 |

记 E(k) 是前 n 个数排序后的第 k 个数, 例如, E(4) = 8 以及 E(6) = 9.

对 1 ⩽ n ⩽ 100000 按照 rad(n) 排序后, 求 E(10000).

# P125: 回文和

TIP

回文数 595 很有趣, 因为它可以写成连续平方数的和: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

恰好有十一个小于一千的回文数可以写成连续平方数的和, 这些回文数的和是 4164. 注意 1 = 0^2+ 1^2 并没有算在内, 因为本题只考虑正整数的平方.

在小于 10^8 的数中, 找出所有可以写成连续平方数的和的回文数, 并求它们的和.

# P126: 立方体层

TIP

要完全包住一个的长方体的表面, 最少需要的立方体数目为 .

如果我们要再包一层, 需要个立方体才能挡住所有表面, 而第三层需要个立方体, 第层则需要个立方体.

同样地, 要完全包住一个的长方体的表面也需要个立方体.

而要包住或是或是的长方体表面, 第一层就需要个立方体.

记是在任意一层中需要个立方体的长方体数目.

所以 .

可以验证是第一个使得的 .

找出使得的最小的 .

找规律题.

顶视图:
正视图:
侧视图:

其中是三角形计数.

然后求和, 因为对称性还要乘 :

试下 Solve, 慢炸了

Solve[2(a b + b c + a c) + 4(a + b + c + n - 2)(n - 1) == 154 && c >= b >= a >= 1 && n > 0, Integers]

啊, 最讨厌减枝了:

counts[limit_] := Block[
    {data},
    data = Table[
        Module[{i = 1}, NestWhileList[(i++;# + 4(a + b + c + 2i - 4))&, 2 (a b + b c + c a), # < limit&]],
        {a, Floor[(limit - 2) / 4]},
        {b, Min[a, Floor[(limit - 2 a) / (2 + 2a)]]},
        {c, Min[b, Floor[(limit - 2 a b) / (2a + 2b)]]}
    ];
    SortBy[Tally@Flatten@data, {Last, First}]
];
Select[counts[2000], #[[2]] == 100 &][[1, 1]]

实在空间想象能力不行的话可以先 3D可视化一下:

cu[dim : {_, _, _}, n_] := Module[
    {a = ConstantArray[1, dim], p, q},
    p = {{1}} ~ ArrayPad ~ 1;
    q = {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}};
    Nest[# + Unitize@ListCorrelate[{p, q, p}, #] ~ ArrayPad ~ 1&, ArrayPad[a, n + 1], n]
];
Graphics3D[Cuboid /@ Position[cu[{3, 2, 1}, 4], 1]]

空间想象能力不错的话不如考虑一下加强命题, 在维空间中的结论.

\begin{aligned} L_{1} &= 2a + 2\\ L_{2} &=2(a+b) + 4(n-1)\\ L_{3} &=2(ab + ac + bc) \\ & + 4(n-1)(a + b + c) \\ & + 4(n-1)(n-2)\\ L_{4} &= 2^1(abc + abd + acd + bcd)/0! \\ & + 2^2(n-1)(ab + ac + ad + bc + bd + cd)/1!\\ & + 2^3(n-1)(n-2)(a + b + c + d)/2! \\ & + 2^4(n-1)(n-2)(n-3)/3! \end{aligned}

更高维的情况以此类推:

$$ L_N =\sum_{k=1}^N{\frac{2^k (n-1)}{B(k,n-1-k)}\sum_{\rm{sym}}(a_1,a_2,\dots,a_{N-k})} $$

其中是 Euler Beta 函数, 是对称和.

33:54

# P127: abc 匹配

TIP

数 n 的基 rad(n) 被定义为 n 的不同质因数之积. 例如 504 = 2^3 × 3^2 × 7, 所以 rad(504) = 2 × 3 × 7 = 42.

我们定义正整数三元组 (a, b, c) 为 abc 匹配, 当其满足如下条件:

GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
a < b
a + b = c
rad(abc) < c

例如, (5, 27, 32) 是一个 abc 匹配, 因为:

GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
5 < 27
5 + 27 = 32
rad(4320) = 30 < 32

实际上, abc 匹配是非常稀少的, 对于 c < 1000, 只有 31 组 abc 匹配, 在这些匹配中∑c = 12523.

对于 c < 120000, 求∑c.

# P128: 六边形地砖的差

TIP

标有数 1 的六边形地砖被一圈六个六边形地砖包围, 这些地砖从 12 点钟方向 (正上方) 开始沿逆时针顺序依次标记为 2 至 7.

在这个图形的外面, 继续加上新的六边形地砖, 接下来的几圈分别按照同样的规则标上 8 至 19, 20 至 37, 38 至 61, 依此类推. 下图显示了前三圈所构成的图形.

考虑标有 n 的地砖与其周围六块地砖的差, 我们定义 PD(n) 是这些差中素数的数目.

例如, 按顺时针顺序, 标有 8 的地砖与周围地砖的差是 12, 29, 11, 6, 1 和 13. 所以 PD(8) = 3.

同样的, 标有 17 的地砖与周围地砖的差是 1, 17, 16, 1, 11 和 10, 所以 PD(17) = 2.

可以验证, PD(n) 的最大值就是 3.

如果所有 PD(n) = 3 的地砖构成从小到大排列的序列, 那么第 10 块将是标有 271 的地砖.

找出这个序列中的第 2000 块地砖所标的数.

# P129: 循环单位数整除性

TIP

只包含数字 1 的数被称为循环单位数, 我们定义 R(k) 是长为 k 的循环单位数, 例如, R(6) = 111111.

如果 n 是一个整数, 且 GCD(n, 10) = 1, 可以验证总存在 k 使得 R(k) 能够被 n 整除, 并且记 A(n) 是这些 k 中最小的一个. 例如, A(7) = 6, 而 A(41) = 5.

使得 A(n) 第一次超过十的 n 是 17.

求使得 A(n) 第一次超过一千万的 n.

# P130: 满足素数循环单位数性质的合数

TIP

只包含数字 1 的数被称为循环单位数, 我们定义 R(k) 是长为 k 的循环单位数, 例如, R(6) = 111111.

如果 n 是一个整数, 且 GCD(n, 10) = 1, 可以验证总存在 k 使得 R(k) 能够被 n 整除, 并且记 A(n) 是这些 k 中最小的一个. 例如, A(7) = 6, 而 A(41) = 5.

已知对于素数 p > 5, p − 1 能够被 A(p) 整除. 例如, 当 p = 41 时, A(41) = 5, 而 40 能够被 5 整除.

然而, 有很少的一部分合数也满足这条性质, 前 5 个这样的数分别是 91, 259, 451, 481 以及 703.

找出前 25 个合数 n 满足 GCD(n, 10) = 1 且 n − 1 能够被 A(n) 整除, 并求它们的和.

← Level111-120 Level131-140 →