191

** 出勤奖励 **

某所学校给有出勤和守时表现良好的孩子发放现金奖励。如果孩子连续三天缺席，或是有多于一次迟到，则拿不到这份奖励。

根据 n 天的实际出勤情况，我们可以生成 L（迟到）、O（准时）和 A（缺席）这三个字母组成的字符串。

根据 4 天的出勤情况，能够生成的字符串一共有 81 种可能，其中恰好有 43 个串可以获得奖励：

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA LAOO LAOA LAAO

根据 30 天的出勤情况生成的字符串中，有多少个是可以获得奖励的串？

192

** 最佳逼近 **

x 是一个实数。 对于 x，分母上限为 d 的最佳逼近，是一个最简分数形式的有理数 r/s，其中 s ⩽ d，使得所有比 r/s 更接近 x 的有理数其最简分数形式的分母都大于 d： |p/q-x| <|r/s-x| ⇒ q> d 例如，对于√13，分母上限为 20 的最佳逼近是 18/5，而分母上限为 30 的最佳逼近是 101/28。

对于所有满足 1 < n ⩽ 100000 的非平方数 n，找出其分母上限为 1012 的最佳逼近，并求出所有这些有理数的分母之和。

193

** 无平方因子数 **

若正整数 n 不能被任意素数的平方整除，则 n 被称为无平方因子数，因此 1, 2, 3, 5, 6, 7, 10, 11 是无平方因子的，而 4, 8, 9, 12 不是。

在小于 250 的数中，有多少个无平方因子数？

194

** 染色摆放方案 **

考虑由 A 单元： 和 B 单元 组成的图形，相邻单元相互重叠在一起如下图所示。

一个 (a,b,c) 类型的染色摆放方案，是一个由 a 个 A 单元和 b 个 B 单元摆放组成，并用至多 c 种颜色给每个顶点染色并保证相邻顶点所染颜色不同的图形. 上面这个复合图形就是 (2,2,6) 类型染色摆放方案的一个例子，事实上它也属于任意 (2,2,c) 类型，只要 c ⩾ 4 即可。

记 N(a,b,c) 是 (a,b,c) 类型的染色摆放方案总数。 例如，N(1,0,3) = 24，N(0,2,4) = 92928，以及 N(2,2,3) = 20736。

求 N(25,75,1984) 的最后 8 位小数。

195

** 有一角为 60 度的三角形的内切圆 **

我们称恰好有一个角为 60 度的整数边长三角形为 60 度三角形。 记 r 是这个 60 度三角形的内切圆的半径。

当 r ⩽ 100 时，一共有 1234 个 60 度三角形。 记 T(n) 是 r ⩽ n 时所有的 60 度三角形数目，因此 T(100) = 1234， T(1000) = 22767，以及 T(10000) = 359912.

求 T(1053779)。

196

** 素数三元组 **

将所有正整数按如下方式排列成三角形的样式：

       123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566......

每个正整数在三角形中有最多八个邻居。

如果三个素数中，有两个均为另一个的邻居，那么这一组三个素数被称为一个 * 素数三元组 *。

例如，在第二行，素数 2 和 3 都是一些素数三元组的元素。

如果我们看第 8 行，将有两个素数属于某些素数三元组，这两个素数是 29 和 31。 如果我们看第 9 行，只有一个素数属于某些素数三元组，这个素数是 37。

记 S(n) 是第 n 行中属于某些素数三元组的素数之和。 因此 S(8)=60，而 S(9)=37。

已知 S(10000)=950007619。

求 S(5678027) + S(7208785)。

197

** 关于一个递归定义序列的研究 **

已知函数 f(x) = ⌊230.403243784-x2⌋ × 10-9 （其中⌊ ⌋是下取整函数）， 序列 un 定义为 u0 = -1 且 un+1 = f(un)。

求 un + un+1，其中 n = 1012。 你的答案需要保留小数点后 9 位数字。

198

** 两可数 **

对于实数 x，分母上限为 d 的最佳逼近，是一个最简分数形式的有理数 r/s，其中 s ⩽ d，使得所有比 r/s 更接近 x 的有理数 p/q 其最简分数形式满足 q> d。

通常这样对某个实数带分母上限的最佳逼近是唯一的。然而，也有一些例外，比如对于 9/40，分母上限为 6 的最佳逼近有两个，分别是 1/4 和 1/5。如果对于实数 x 存在某个分母上限使得它有两个最佳逼近，我们就称 x 为 * 两可的 *。显然，一个两可数必须是有理数。

有多少个两可数 x = p/q，满足 0 < x < 1/100，而且其分母 q 不超过 108？

199

** 迭代放圆 **

在一个大圆内放入三个等大的圆，这三个圆以及大圆两两相切，而且相互不重叠。这样一来，大圆内就有四块未覆盖的 “空隙”，我们将迭代地在里面放入更多相切的圆以填补它们。 每一轮迭代，我们都在每个空隙中放入尽可能大的圆，如此一来下一轮迭代时将会有更多的空隙。经过三轮迭代（如上图），大圆中一共有 108 个空隙，大圆内未被其它圆覆盖的面积占大圆面积的比例为 0.06790342，四舍五入到八位小数。

经过 10 轮迭代后，未被覆盖的面积占大圆面积的比例是多少？ 你的答案应当四舍五入到八位小数，也即 x.xxxxxxxx 的格式。

200

** 找出第 200 个拥有连续子串 “200” 且不可变质数的平立方数 **

我们定义平立方数为可以写成 p2q3 形式的数，其中 p 和 q 为不同质数。 例如，200 = 5223，以及 120072949 = 232613。

前五个平立方数分别是 72, 108, 200, 392 和 500。

有趣的是，200 同样是第一个你无法只改变其一位数字就成为质数的数， 我们称这样的数为不可变质数的。下一个拥有连续子串 “200” 且不可变质数的平立方数是 1992008。

找出第 200 个拥有连续子串 “200” 且不可变质数的平立方数。