181

** 有关两种不同颜色的物体如何分组的研究 **

三个黑色物体 B 和一个白色物体 W 进行分组，有以下 7 种方式：

   (BBBW)(B,BBW)(B,B,BW)(B,B,B,W)(B,BB,W)(BBB,W)(BB,BW)

六十个黑色物体 B 和四十个白色物体 W 进行分组有多少种方式？

182

**RSA 加密 **

RSA 加密基于以下流程：

生成两个不同的素数 p 和 q。计算 n=pq 以及φ=(p-1)(q-1)。 找到整数 e，满足 1<e<φ，且 gcd(e,φ)=1。

RSA 系统能加密的信息是区间 [0,n-1] 中的整数。 因此，需要加密的文本首先需要转换成可加密的信息（即区间 [0,n-1] 内的某个整数）。 加密文本时，如果文本转换成的信息是 m，则加密为 c=me mod n。

解密文本时，需要以下流程：计算 d 满足 ed=1 mod φ，如果加密的信息是 c，则解密为 m=cd mod n。

存在某些 e 和 m 使得 me mod n=m。 我们称满足 me mod n=m 的这些 m 为未加密信息。

在选择 e 时，很重要的一点就是不应该有太多未加密信息。 例如，令 p=19，q=37。 然后 n=1937=703，φ=1836=648。 如果我们选择 e=181，那么尽管 gcd(181,648)=1，但是所有可能的信息 m (0⩽m⩽n-1) 都是未加密信息，只要我们计算一下 me mod n 就能发现。 对于任意的 e，总是存在一些未加密信息。 使得未加密信息的数目为最小值是很重要的。

现在我们选择 p=1009，q=3643。 找出所有 e，满足 1<e<φ(1009,3643) 且 gcd(e,φ)=1，并且此时未加密信息的数目为最小值。求出所有这些 e 的和。

183

** 最大拆分乘积 **

N 是一个正整数，将 N 拆分成 k 个相等的部分，记 r = N/k，也即 N = r + r + … + r。 记 P 是这些拆分的乘积，也即 P = r × r × … × r = rk。

例如，将 11 拆分成 5 个相等的部分，11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2，那么 P = 2.25 = 51.53632。

对于给定的 N，记 M(N) = Pmax。

计算可得，N = 11 时，这个最大值是在将其拆分成四等份时得到的，此时 Pmax = (11/4)4，也就是说 M(11) = 14641/256 = 57.19140625，这是一个有限小数。

然而，对于 N = 8，这个最大值是在将其拆分成三等份时得到的，此时 M(8) = 512/27，不是有限小数。

若 M(N) 不是有限小数，记 D(N) = N，反之记 D(N) = -N。

例如，对于 5 ⩽ N ⩽ 100，ΣD(N) 为 2438。

对于 5 ⩽ N ⩽ 10000，求ΣD(N)。

184

** 包含原点的三角形 **

集合 Ir 包含了以原点为圆心，半径为 r 的圆内的所有格点 (x,y)，也即满足 x2 + y2 < r2 的点。

若半径为 2，I2 中包含了 9 个点 (0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1) 和 (1,-1)。有八个三角形，其顶点都在 I2 中，且原点在三角形内部。下图所示是其中的两个，另外那些可以通过旋转这两个三角形得到。 若半径为 3，有 360 个三角形包含原点在其内部且顶点在 I3 中；对于 I5 这个数字是 10600。

有多少个三角形包含原点在其内部且顶点在 I105 中？

185

** 数字头脑 **

“数字头脑” 游戏是著名的游戏 “大师头脑” 的一个变种。

在 “数字头脑” 中，你需要猜测一个数字序列，而不是 “大师头脑” 中的彩色方块。每次猜测之后，你会被告知你猜对了多少个位置上的数字。因此，如果正确的序列是 1234，而你猜的是 2036，那么你会被告知你猜对了一个位置上的数字。然而，你并 ** 不会 ** 知道你是否猜对了数字但不在其正确位置上。

例如，根据你对一个五位的数字序列作的如下猜测：

90342；2 个数字正确 70794；0 个数字正确 39458；2 个数字正确 34109；1 个数字正确 51545；2 个数字正确 12531；1 个数字正确

唯一正确的序列是 39542。

根据下面的猜测，

5616185650518293；2 个数字正确 3847439647293047；1 个数字正确 5855462940810587；3 个数字正确 9742855507068353；3 个数字正确 4296849643607543；3 个数字正确 3174248439465858；1 个数字正确 4513559094146117；2 个数字正确 7890971548908067；3 个数字正确 8157356344118483；1 个数字正确 2615250744386899；2 个数字正确 8690095851526254；3 个数字正确 6375711915077050；1 个数字正确 6913859173121360；1 个数字正确 6442889055042768；2 个数字正确 2321386104303845；0 个数字正确 2326509471271448；2 个数字正确 5251583379644322；2 个数字正确 1748270476758276；3 个数字正确 4895722652190306；1 个数字正确 3041631117224635；3 个数字正确 1841236454324589；3 个数字正确 2659862637316867；2 个数字正确

求出唯一正确的 16 位序列。

186

** 网络连通性 **

以下是一个有着一百万用户的忙碌电话系统的部分记录：

编号呼叫接听 120000710005326001835004393600863701497………

编号为 n 的记录中，呼叫者的电话号码是 Caller(n) = S2n-1，接听者的电话号码是 Called(n) = S2n，其中 S1,2,3,… 来自于所谓 “延迟斐波那契随机数生成器”：

对于 1 ⩽ k ⩽ 55，Sk = [100003 - 200003k + 300007k3] (modulo 1000000) 对于 56 ⩽ k，Sk = [Sk-24 + Sk-55] (modulo 1000000)

如果 Caller(n) = Called(n)，那么我们认为呼叫者拨错了号码，呼叫失败；否则我们认为呼叫成功。

根据这份记录，如果 X 曾经呼叫过 Y 或者 Y 呼叫过 X，则我们认为这两个电话用户 X 和 Y 是朋友。同样的，如果 X 是 Y 的朋友，Y 是 Z 的朋友，那么我们说 X 是 Z 的朋友的朋友；我们可以同理组成更长的 “朋友” 链。

首相的电话号码是 524287。在多少次呼叫成功（不计呼叫失败）之后，99% 的用户（包括首相）将会成为首相的朋友，或是朋友的朋友，或是朋友的朋友的朋友……？

187

** 半素数 **

合数是指包含至少两个质因数的整数。例如，15 = 3 × 5；9 = 3 × 3；12 = 2 × 2 × 3。

在小于 30 的合数中，有十个合数包含恰好两个不一定不同的质因数：4, 6, 9, 10, 14, 15, 21, 22, 25, 26。

有多少个合数 n < 108 包含恰好两个不一定不同的质因数？

188

** 数的超幂 **

数 a 的正整数 b 次超幂或迭代幂次，记作 a↑↑b 或 ba，按照如下方式递归定义：

a↑↑1 = a, a↑↑(k+1) = a(a↑↑k).

举例来说，3↑↑2 = 33 = 27，因此 3↑↑3 = 327 = 7625597484987，而 3↑↑4 约为 103.6383346400240996*10^12。

求 1777↑↑1855 的最后 8 位数字。

189

** 三角形阵的三染色 **

考虑按如下方式摆放的 64 个三角形： 我们想要给每个三角形的内部染上红、绿、蓝这三种颜色之一，而且任意两个相邻的三角形所染颜色不同，这样的染色方案我们视为有效。在这里，两个相邻的三角形是指它们共用一条边。 注意：共用一个顶点的三角形并不视为相邻三角形。

例如，下图是一个上述三角形阵的有效染色方案： 我们认为可以由染色方案 C 旋转而成的染色方案 C’与 C 是不同的，除非 C 旋转后得到的染色方案与其完全一致。

对于上述三角形阵，有多少种不同的有效染色方案？

190

** 加权乘积最大化 **

记 Sm = (x1, x2, … , xm) 是 m 元正实数组，其中 x1 + x2 + … + xm = m，且 Pm = x1 * x22 * … * xmm 取得其最大值。

例如，可以验证，[P10] = 4112（[ ] 是截尾函数）。

对于 2 ⩽ m ⩽ 15，求Σ[Pm]。