组合数学引论 许胤龙 第二版答案 中国科学技术大学
需积分: 48 63 浏览量
2022-09-07
11:19:01
上传
评论 23
收藏 665KB PDF 举报
3. 任意一个整数除以 n 的余数最多只可能有 n 种情况：0，1，2…n - 1。所
以 n + 1 个整数除以 n，必有至少两个数的余数相同，那么它们的差是 n 的倍数。
4. (1)令 b
1
，b
2
，…，b
77
分别为这 11 周期间他每天下棋的次数，并作部分和
=
,
=
+
,
⋯,
=
+
+ ⋯+
.
依题意，
≥ 1
(
1 ≤ ≤ 77
)
，且
+
+ ⋯+
≤ 12
(
1 ≤ ≤ 71
)
，故有1 ≤
≤
≤ ⋯ ≤
≤ 12 × 11 = 132。
当1 ≤ ≤ 21时，考虑数列
,
,⋯,
,
+ ,
+ ,⋯,
+ ，它们都在
1 与132 +
(
133 ≤ 132 + ≤ 153
)
之间，共有 154 项。由鸽巢原理，其中必有
两项相等。由于
,
,⋯,
这 77 项互不相等，所以
+ ,
+ ,⋯,
+ 这
77 项也互不相等，所以一定存在1 ≤ < ≤ 77，使得
=
+ 。所以 =
−
。即存在连续的一些天，棋手恰好下了
(
= 1,2,⋯21
)
盘棋。
(2)考虑数列
,
,⋯,
,
+ 22,
+ 22,⋯,
+ 22，
(i)如果这 154 项中有两项相等，则存在1 ≤ < ≤ 77，使得
=
+ 22，
则从第 i 天到第 j 天棋手恰好下了 22 盘棋。
(ii)如果这 154 项中任意两项都不相等，则数列
,
,⋯,
,
+ 22,
+
22,⋯,
+ 22是 1 到 154 的一个全排列。然而这种全排列其实是不存在的，数
列中最小的数为
，所以
= 1，
+ 22 = 23；除去
，最小的数为
，所以
= 2，
+ 22 = 24等等，具体结果如下：
= 1,
= 2,⋯,
= 22,
+ 22 = 23,
+ 22 = 24,⋯,
+ 22 = 44,
= 45,
= 46,⋯,
= 66,
+ 22 = 67,
+ 22 = 68,⋯,
+ 22 = 88,
= 89,
= 90,⋯,
= 110,
+ 22 = 111,
+ 22 = 112,⋯,
+ 22 = 132,
此时
最小，
= 133，而
+ 22 = 155，所以这种全排列是不存在的。
综上所述，这 154 项中存在连续的一些天，棋手恰好下了 22 盘棋。
6. 任意一个整数可以表示为2
⋅
，
为非负整数,
为奇数，按照
将 1 到
200 这 200 个数划分成 100 个集合：
=
{
2
⋅ 1,2
⋅ 1,…,2
⋅ 1
}
;
=
{
2
⋅ 3,2
⋅ 3,…,2
⋅ 3
}
;
…
剩余29页未读，继续阅读
评论0
最新资源