# P151: 标准大小的纸张: 有关期望的问题
一家打印店每周有 16 份打印工作, 每份打印工作需要一张 A5 大小的特殊彩色打样纸.
每周一早晨, 领班会打开一个新信封, 其中有一张 A1 大小的特殊彩色打样纸.
他将这张纸一裁为二, 得到两张 A2 大小的纸. 再将其中一张一裁为二, 得到 A3 大小的纸, 如此直到他裁出一张用于第一份打印工作的 A5 大小的彩色打样纸.
所有剩下的纸张将会重新放回信封里.
接下来的每次打印工作前, 领班会从信封里拿出随机拿出一张纸, 如果恰好是 A5 大小的, 他会直接拿去使用, 否则他会重复一裁为二的过程直到他得到一张 A5 大小的纸, 并将剩下的纸重新放回信封里.
除了每周的第一次和最后一次打印工作外, 求在这周当中领班在拿纸时发现信封里只有一张纸的次数的期望值.
你的答案应当保留六位小数, 即以如下的形式 x.xxxxxx.
# P152: 将 1/2 写成平方数的倒数和
有许多种方式将 1/2 写成一系列_不同_整数的平方的倒数和.
例如, 可以用这些数 {2,3,4,5,7,12,15,20,28,35}:
\begin{aligned} \dfrac{1}{2} &= \dfrac{1}{2^2} + \dfrac{1}{3^2} + \dfrac{1}{4^2} + \dfrac{1}{5^2}\\ &+ \dfrac{1}{7^2} + \dfrac{1}{12^2} + \dfrac{1}{15^2} + \dfrac{1}{20^2}\\ &+ \dfrac{1}{28^2} + \dfrac{1}{35^2} \end{aligned}
事实上, 只用 2 至 45 之间的数的方式一共有三种, 另两种分别是:{2,3,4,6,7,9,10,20,28,35,36,45} 和 {2,3,4,6,7,9,12,15,28,30,35,36,45}.
如果只用 2 至 80 之间的数, 将 1/2 写成不同整数的平方的倒数和共有多少种方式?
# P153: 高斯整数的研究
我们都知道方程 x^2=-1 在实数范围内无解. 但如果我们引入虚数 i, 这个方程将会有两个解 x=i 和 x=-i. 进一步地, 方程 (x-3)^2=-4 有两个复数解: x=3+2i 和 x=3-2i. x=3+2i 和 x=3-2i 互称为共轭复数. 形如 a+bi 的数被称为复数. 概括地说, a+bi 和 a−bi 互称为共轭复数.
概括地说，a+bi和a−bi互称为共轭复数。
高斯整数是形如a+bi且a和b均为整数的复数。 一般意义上的整数也是高斯整数（取b=0）。 为了把它们和b ≠ 0的高斯整数区分开来，称它们为“有理整数”。 如果一个高斯整数除有理整数n的结果仍然是高斯整数，则称它为该有理整数的约数。 例如，我们用1+2i除5，按如下方式简化
：分子和分母同时乘以1+2i的共轭：1−2i。 结果是：
。所以1+2i是5的约数。 注意1+i不是5的约数，因为
。同时注意如果高斯整数(a+bi)是有理整数n的约数，那么它的共轭复数(a−bi)也是n的约数。
事实上, 5 一共有六个实数部分是正数的约数:{1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5}. 如下表格列出了前五个正有理整数的所有约数:
| n | 实数部分是正数的高斯整数约数 | 约数的和 s(n) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1, 1+i, 1-i, 2 | 5 |
| 3 | 1, 3 | 4 |
| 4 | 1, 1+i, 1-i, 2, 2+2i, 2-2i,4 | 13 |
| 5 | 1, 1+2i, 1-2i, 2+i, 2-i, 5 | 12 |
对于实数部分为正数的约数，我们有： 。
对于1 ⩽ n ⩽ 105，∑ s(n)=17924657155。
对于1 ⩽ n ⩽ 108，求∑ s(n)。
对于 1 ⩽ n ⩽ 10^5, ∑ s(n)=17924657155.
对于 1 ⩽ n ⩽ 10^8, 求∑ s(n).
# P154: 探索帕斯卡四面体
我们用球构建一个三角形四面体, 每一个球的下一层都由恰好三个球支撑.
然后, 我们计算从顶端到每一个位置的路径数:
每一条路径从顶端出发, 然后每次都走向下一层支撑当前位置的球的三个球之一.
最终, 到达每个位置的路径数是它上方的球的路径数之和 (根据位置的不同, 每个位置的上方最多可能有三个球).
最终的结果被称为_帕斯卡四面体_, 这个四面体第 n 层的结果将是三项式 (x + y + z)^n 的系数.
在三项式 (x + y + z)^200000 的展开式中, 有多少个系数是 10^12 的倍数?
# P155: 电容电路计算
考虑如下电路, 其中使用的电容都是完全相同的值 C. 电容之间互相串联构成次级单元, 然后次级单元之间互相串联或和其它次级单元或电容并联构成更大的次级单元, 最终组成整个电路.
使用 n 个电容并重复这个简单的过程, 我们可以构建出一系列总电容不同的电路. 例如, 使用最多 n=3 个值为 60μF 的电容, 我们可以得到 7 种不同的总电容:
我们用 D(n) 表示当我们使用最多 n 个相同的电容并重复上述简单过程后, 我们能够得到的总电容的种数, 我们有: D(1)=1, D(2)=3, D(3)=7 …
求 D(18).
提醒：当电容C1，C2等等并联时，总电容为CT = C1 + C2 +…， 而当它们串联时，总电容为：。
# P156: 数字计数
从零开始的自然数在十进制中如下表示: 0 1 2 3 4 5 6 7 8 9 10 11 12….
考虑数字 d=1. 当我们写下数 n 之后, 我们计算一下到目前为止数字 1 出现的次数, 并记为 f(n,1).f(n,1) 的前面一部分值如下所示:
| n | f(n,1) |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
| 10 | 2 |
| 11 | 4 |
| 12 | 5 |
注意到 f(n,1) 从不等于 3. 等式 f(n,1)=n 的前两个解是 n=0 和 n=1, 下一个解是 n=199981.
同样地我们记 f(n,d) 表示在写下 n 之后 d 出现的次数. 事实上, 对于任意一个数字 d ≠ 0, 0 都是方程 f(n,d)=n 的第一个解.
记 s(d) 是所有 f(n,d)=n 的解的和. 已知 s(1)=22786974071.
对于 1 ⩽ d ⩽ 9, 求∑ s(d).
注意: 如果对于某些 n, 对于多于一个的 d 均满足 f(n,d)=n, 这个数 n 对于每个 d 都要计算一遍.
# P157: 解不定方程 ^1/_a+^1/_b= ^p/_10^n
考虑不定方程 ^1/_a+^1/_b= ^p/_10^n, 其中 a, b, p, n 均为正整数, 且 a ⩽ b. 对于 n=1, 这个方程有 20 个解, 如下所示:
| ^1/_1+^1/_1=^20/_10 | ^1/_1+^1/_2=^15/_10 | ^1/_1+^1/_5=^12/_10 | ^1/_1+^1/_10=^11/_10 | ^1/_2+^1/_2=^10/_10 |
| ^1/_2+^1/_5=^7/_10 | ^1/_2+^1/_10=^6/_10 | ^1/_3+^1/_6=^5/_10 | ^1/_3+^1/_15=^4/_10 | ^1/_4+^1/_4=^5/_10 |
| ^1/_4+^1/_20=^3/_10 | ^1/_5+^1/_5=^4/_10 | ^1/_5+^1/_10=^3/_10 | ^1/_6+^1/_30=^2/_10 | ^1/_10+^1/_10=^2/_10 |
| ^1/_11+^1/_110=^1/_10 | ^1/_12+^1/_60=^1/_10 | ^1/_14+^1/_35=^1/_10 | ^1/_15+^1/_30=^1/_10 | ^1/_20+^1/_20=^1/_10 |
对于 1 ⩽ n ⩽ 9, 方程一共有多少个解?
# P158: 按字典序升序排列的字符串研究
从字母表的 26 个字母中取出三个不同的字母, 可以组成一个长度为 3 的字符串. 这样的例子包括’abc’, ’hat’和’zyx’. 可以发现, 对于字符串’abc’, 有两个字符与其左侧字符是按照字典序升序排列的. 对于字符串’hat’, 只有一个字符与其左侧字符是按照字典序升序排列的, 而对于字符串’zyx’则不存在这样的字符. 总共有 10400 个长度为 3 的字符串, 其中恰好有一个字符与其左侧字符是按照字典序升序排列的.
现在考虑由字母表中的 n ⩽ 26 个不同字符组成的字符串. 对于任意 n, 我们用 p(n) 表示长度为 n 且恰好有一个字符与其左侧字符是按照字典序升序排列的字符串数目.
p(n) 的最大值是多少?
# P159: 分解约数数字根之和
每个合数都有很多种分解约数的方式. 例如, 如果不允许多次乘 1, 有 7 种不同的方式分解 24 的约数:
24 = 2x2x2x3 24 = 2x3x4 24 = 2x2x6 24 = 4x6 24 = 3x8 24 = 2x12 24 = 24
在十进制下, 一个数的数字根是不断重复将其各位数字相加, 直到得到的结果小于 10 为止. 因此 467 的数字根是 8.
我们记数字根和 (DRS) 是所有分解出的约数的数字根之和. 下表是 24 的所有约数分解的 DRS 值.
| 约数分解 | 数字根和 |
|---|---|
| 2x2x2x3 | 9 |
| 2x3x4 | 9 |
| 2x2x6 | 10 |
| 4x6 | 10 |
| 3x8 | 11 |
| 2x12 | 5 |
| 24 | 6 |
对于 24 的所有分解, 最大的数字根和是 11. 函数 mdrs(n) 表示对于 n 的不同分解最大的数字根和. 因此 mdrs(24)=11. 对于 1 <n < 1,000,000, 求∑mdrs(n).
# P160: 阶乘的尾数
对于任意 N, 记 f(N) 为 N! 除去末尾零后的最后五位数字. 例如,
9! = 362880, 所以 f(9)=36288 10! = 3628800, 所以 f(10)=36288 20! = 2432902008176640000, 所以 f(20)=17664
求 f(1,000,000,000,000)