201

** 拥有唯一出现的元素和的子集 **

对于任意数集 A，记 A 中所有元素的和为 sum(A)。 考虑集合 B = {1,3,6,8,10,11}。 B 有 20 个子集包含恰好三个元素，而这些子集的元素和分别是：

sum({1,3,6}) = 10, sum({1,3,8}) = 12, sum({1,3,10}) = 14, sum({1,3,11}) = 15, sum({1,6,8}) = 15, sum({1,6,10}) = 17, sum({1,6,11}) = 18, sum({1,8,10}) = 19, sum({1,8,11}) = 20, sum({1,10,11}) = 22, sum({3,6,8}) = 17, sum({3,6,10}) = 19, sum({3,6,11}) = 20, sum({3,8,10}) = 21, sum({3,8,11}) = 22, sum({3,10,11}) = 24, sum({6,8,10}) = 24, sum({6,8,11}) = 25, sum({6,10,11}) = 27, sum({8,10,11}) = 29.

这其中的有些元素和出现了不止一次，其它元素和则是唯一出现的。 对于任意集合 A，先求 A 所有恰好包含 k 个元素的子集的元素和，其中唯一出现的元素和构成集合 U(A,k)。在我们的例子中，我们发现 U(B,3) = {10,12,14,18,21,25,27,29}，因而 sum(U(B,3)) = 156。

现在考虑有 100 个元素的集合 S = {12, 22, … , 1002}。 S 有 100891344545564193334812497256 个子集恰好包含 50 个元素。

在这些子集的元素和中，找出那些唯一出现的元素和并求和，也即求 sum(U(S,50))。

202

** 激光束 **

三面镜子摆成了正三角形的形状，其反射面朝内放置。在三角形的顶点处有一个无穷小的间隙可容一束激光束通过。

记三个顶点分别为 A、B 和 C。从顶点 C 射入的激光束，经过 11 次反射后再从同一个顶点射出，这样的路径一共有两条：其中一条如下所示，另一条即是将其反向。 从顶点 C 射入的激光束，经过 1000001 次反射后再从同一个顶点射出，这样的路径一共有 80840 条。

从顶点 C 射入的激光束，经过 12017639147 次反射后再从同一个顶点射出，这样的路径一共有多少条？

203

** 无平方因子二项式系数 **

二项式系数 nCk 可以如下排成一个三角形，称为帕斯卡三角形：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

.........

可以看出帕斯卡三角形的前八行包含了十二个不同的数：1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35。

如果正整数不被任何素数的平方整除，n 就被称为无平方因子数。 在帕斯卡三角形前八行的十二个不同的数中，除了 4 和 20 之外都是无平方因子数。 这些不同的无平方因子数之和为 105。

求帕斯卡三角形前 51 行所有不同的无平方因子数之和。

204

** 广义汉明数 **

若一个正整数的所有质因数均不超过 5，则被称为汉明数。 前几个汉明数分别是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15。 在不超过 108 的正整数中，一共有 1105 个汉明数。

若一个正整数的所有质因数均不超过 n，则被称为 n 型广义汉明数。 因此本来的汉明数就是 5 型广义汉明数。

在不超过 109 的整整书中，一共有多少个 100 型广义汉明数？

205

** 骰子游戏 **

彼得有九个四面的（金字塔型）骰子，每个面上分别标有 1，2，3，4。 科林有六个六面的（立方体型）骰子，每个面上分别标有 1，2，3，4，5，6。

彼得和科林分别掷出他们的所有骰子，并比较点数和：点数和更大者获胜。如果点数和相同，双方打成平手。

金字塔彼得击败立方体科林的概率是多少？你的答案应当四舍五入至七位小数，即格式为 0.abcdefg。

206

** 被遮挡的平方数 **

找出唯一一个其平方形如 1_2_3_4_5_6_7_8_9_0 的正整数， 其中每个 “_” 表示一位数字。

207

** 整数分拆等式 **

对于某些正整数 k，存在形如 4t = 2t + k 的整数分拆， 其中 4t，2t 和 k 均为正整数，而 t 为实数。

前两个这样的分拆分别是 41 = 21 + 2 和 41.5849625… = 21.5849625… + 6。

如果 t 也是整数，这样的分拆称为完美的。 对于任意 m ≥ 1，记 P(m) 是所有 k ≤ m 的分拆中完美分拆的比例。 因此 P(6) = 1/2。

下面的表格列出了 P(m) 的部分取值：

P(5) = 1/1 P(10) = 1/2 P(15) = 2/3 P(20) = 1/2 P(25) = 1/2 P(30) = 2/5 … P(180) = 1/4 P(185) = 3/13

求出使得 P(m) < 1/12345 的最小 m 值。

208

** 机器人走路 **

一个机器人每步走五分之一个圆弧（72°），它每步都可以选择顺时针走或是逆时针走，但在走的途中不能改变方向。

机器人从面向正北方开始，连续走 25 步所构成的闭合路径共有 70932 条，以下是其中一条： 假定机器人仍然从面向正北方开始，连续走 70 步之后，能够回到出发位置的路径有多少条？ （所有圆弧都可以经过多次。）

209

** 圆环之理 **

k 元真值表是从 k 比特位（即二进制位的简称，其中 0 代表假，1 代表真）输入到 1 比特位输出的映射。例如，逻辑运算符 AND（和）和 XOR（异或）的 2 元真值表如下所示：

xyx AND yxyx XOR y000000010011100101111110

有多少个 6 元真值表τ，对于所有的 6 比特位输入 (a, b, c, d, e, f) 始终满足下述等式？ τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0

210

** 锐角三角形 **

点集 S(r) 包含了所有坐标为整数且 | x| + |y| ≤ r 的点 (x,y)。 记 O 为原点 (0,0)，C 为点 (r/4,r/4)。 在 S(r) 中取一点 B，使得三角形 OBC 有一个钝角，也即这个三角形的最大角α满足 90°<α<180°，记所有这样的点 B 的数目为 N(r)。 例如，N(4)=24 以及 N(8)=100。

求问 N(1,000,000,000) 是多少？