# P161: 三联骨牌
三联骨牌是由三个正方形方块拼接而成的骨牌, 它一共有两种基本形状:
如果计入旋转, 则一共有六种可能的形状:
任何 n × m 的方阵, 只要 nxm 能够被 3 整除, 就能用三联骨牌拼出来.
如果我们认为翻转或旋转是不同的拼法, 那一个 2 × 9 的方阵有一共有 41 种拼法:
一个 9 × 12 的方阵有多少种拼法?
# P162: 十六进制数
十六进制数系统使用 16 个不同的数字:
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
十六进制数 AF 在十进制下等于 10x16+15=175.
三位十六进制数 10A, 1A0, A10 和 A01 都包含数字 0, 1 和 A. 和十进制下一样, 在十六进制中没有前导零.
有多少至多十六位的十六进制数同时包含 0, 1 和 A? 用十六进制数表示你的答案.
(A,B,C,D,E 和 F 均为大写字母, 没有前导零或末尾标识符来表明该数字为十六进制, 例如, 1A3F 不能写成: 1a3f 或 0x1a3f 或 $1A3F 或 #1A3F 或 0000001A3F)
# P163: 纵横交错的三角形
考虑一个等边三角形, 从三角形的每个顶点向对边的中点引一条线段, 构成如下图所示的 1 级三角形.
我们可以从这个三角形中数出 16 个不同形状, 不同大小, 不同方向, 不同位置的三角形.
使用 1 级三角形作为材料, 我们可以构成更大的三角形, 比如右边的 2 级三角形.
在 2 级三角形中可以输出一百零四个不同形状, 不同大小, 不同方向, 不同位置的三角形.
可以看出一个 2 级三角形包含有 4 个 1 级三角形.一个 3 级三角形包含有 9 个 1 级三角形, 而一个 n 级三角形包含有
如果我们用
T(1) = 16 T(2) = 104
求 T(36).
# P164: 没有连续三位数字的和超过给定值的数
有多少个 20 位数字 n(不包括前导 0)满足, 不存在连续三位数字的和超过 9?
# P165: 交点
一条线段由其两个端点唯一决定.考虑平面几何中的两条线段, 一共有如下三种可能性: 两条线段没有, 有一个或者有无数个交点.
进一步地, 当两条线段恰好有一个交点时, 可能这个交点是其中一条或两条的端点.如果这个交点不是任一条线段的端点, 那它一定是这两条线段的内点. 当两条线段 L_1 和 L_2 的交点 T 是这两条线段唯一的交点且是这两条线段的内点时, 我们称 T 为这两条线段的真交点.
考虑以下三条线段 L_1, L_2 和 L_3:
L_1: (27, 44) to (12, 32) L_2: (46, 53) to (17, 62) L_3: (46, 70) to (22, 40)
可以验证, 线段 L_2 和 L_3 有一个真交点.注意到 L_3 的一个端点 (22,40) 恰好在 L_1 上, 因此这不是一个真交点.L_1 和 L_2 则没有交点.因此在这三条线段中, 一共有一个真交点.
现在我们来对 5000 条线段求真交点数.首先, 我们用 "布鲁姆 - 布鲁姆 - 舒布" 伪随机数生成算法生成 2000 个数.
s_ = 290797 s_n+1 = s_n×s_n (modulo 50515093) t_n = s_n (modulo 500)
为了生成每一条线段, 我们使用 t_n 的连续四项, 也就是说, 第一条线段是:
(t_1, t_2) 至 (t_3, t_4)
由上述算法生成的前四个数是:27, 144, 12 和 232, 因此第一条线段是 (27,144) 至(12,232).
在这 5000 条线段中, 有多少个真交点?
# P166: 纵横交错
Criss cross
一个4×4方阵填满了0≤d≤9的数字。
可以看出，在如下方阵中
\begin{matrix} 6 & 3 & 3 & 0 \\ 5 & 0 & 4 & 3 \\ 0 & 7 & 1 & 4 \\ 1 & 2 & 4 & 5 \\ \end{matrix}
每一行和每一列的和都是12，而且对角线上的数字和也都是12。
在4×4方阵中填入0≤d≤9的数字，要使得每一行、每一列和对角线上的和都是相同的数，有多少种填法？
# P167: 乌拉姆序列研究
任取两个正整数 a 和 b, 乌拉姆序列 U(a,b) 按如下方式定义:U(a,b)_1 = a, U(a,b)_2 = b, 对于 k > 2, U(a,b)k 是比 U(a,b)(k-1) 更大, 且存在用 U(a,b) 之前的这些项中的不同两项之和唯一表示的最小整数.
例如, 序列 U(1,2) 的开头部分如下所示 1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8; 5 不在这个序列是, 因为 5 = 1 + 4 = 2 + 3, 有两种表示方法, 同样地 7 也是如此因为 7 = 1 + 6 = 3 + 4.
对于 2 ⩽ n ⩽10, 求∑U(2,2n+1)_k, 其中 k = 10^11.
P168:** 数字轮换
考虑数 142857, 我们可以将它的数字右移一位并把最后一个数字 7 放到最前面, 得到 714285. 可以验证 714285=5×142857. 这表明了 142857 的一个特殊性质:它右移一位并把末位数字移至最前得到的数是它的倍数.
找出所有
P169:** 探索将数表达为 2 的幂之和的方式数目
记 f(0)=1, f(n) 是将 n 表达为 2 的幂之和, 且不同的幂至多使用两次的方式数目.
例如, f(10)=5, 即有五种不同的方式表示 10:
1 + 1 + 8 1 + 1 + 4 + 41 + 1 + 2 + 2 + 4 2 + 4 + 4 2 + 8
求
# P170: 求用乘积拼接而成的最大 0 至 9 全数字数
将 6 分别乘以 1273 和 9854:
6 × 1273 = 7638 6 × 9854 = 59124
连接这两个乘积我们得到 1 至 9 全数字数 763859124. 我们称 763859124 为 "6 和(1273,9854) 乘积的连接".注意到, 被乘的这些数的连接 612739854, 同样也是 1 至 9 全数字数.
对于 0 至 9 全数字数也存在同样的可能.
在所有由一个整数和另外至少两个整数的乘积连接而成且被乘的整数连接起来也是 0 至 9 全数字数的 0 至 9 全数字数中, 求其中最大的一个.