#import "../../lib.typ": *

= 课后习题

== 第1章：鸽巢原理<ch1>

=== $P_22,6.$ 

#showybox(
  title: [
证明：从1,2,…,200 中任取100 个整数，其中之一小于16,那么必有两个数，一个能被另一个整除。
])[
首先，将整数1至200按照$1*2^n，3*2^n，5*2^n，…，197，199$的形式分成100个抽屉，从1到200中任取100个，其中有一数a小于16，假设没有两个构成整除关系，首先按抽屉原理，这100个数必须为每个抽屉中仅取且必取1个数，否则假设不成立，所以：

- 当a为小于16的奇数时（比如15），显然有数与其构成整数关系（比如抽屉15*11=165）结论成立；
- 当此数为$1*2^n$时，显然$n≤3$,考虑抽屉$3*2^(n_1)，9*2^(n_2)，27*2^(n_3)，81*2^(n_4)$，显然若不存在整除关系，则$n_4 <n_3<n_2<n_1<3$，即四个数只能在0、1、2三个数中选择，此时产生矛盾，必存在两数整除关系;
- 更一般的，当此数为非2的幂的偶数时，可写成$b*2^n$，b为奇数，且$1<b≤7，n≤2$，考虑抽屉$3b*2^(n_1),9b*2^(n_2),27b*2^(n_3)$(因$b≤7,27b<200$), $n_3<n_2<n_1<2$，即三个数只能在0、1两个数中选择，此时产生矛盾。

综上，假设不成立，必存在两数整除关系。
]

=== $P_23,15.$ 

#showybox(
  breakable: true,
  title: [
证明：从1,2,… ,2n 中任选n +1个整数，则其中必有两个数，它们的最大公因子 为 1
  ]
)[
1. 构造配对

   将集合${1,2,3,#sym.dots.h,2n}$中的数两两配对，形成n对：
   $ (1,2),(3,4),#sym.dots.h,(2n-1,2n) $
   每一对中的两个数都是连续的奇数和偶数。

2. 应用鸽巢原理

   - 我们有 n 对，每对包含两个数。
   - 任取n + 1个数，根据鸽巢原理，至少有一对中的两个数被选中。

3. 分析被选中的两数

   - 设这对被选中的数为  $(2k - 1, 2k)$ ，其中  k  为正整数， $1 ≤ k ≤ n$ 。
   - 这两个数是连续的奇数和偶数，即  2k - 1  和  2k 。
   - 由于  2k - 1  是奇数， 2k  是偶数，它们的最大公因子为：
     
     $ gcd(2k - 1, 2k) = gcd(2k - 1, 2k - (2k - 1)) = gcd(2k - 1, 1) = 1 $
     
    因此，这两个数互质。


根据上述分析，无论从  $1, 2, ……, 2n$  中选取哪  $n + 1$  个数，必定存在至少一对连续的奇数和偶数，这对数的最大公因子为 1。因此，在所选的  $n + 1$  个数中，必有两个数互质。

综上所述， 从集合  $1, 2, ……, 2n$  中任取  n + 1  个整数，必存在两个数的最大公因子为 1。
]

=== $P_23,26.$ 

#showybox(
  title: [
    证明：在任意给出的n+1(n≥2)个正整数中必有两个数，它们的差能被 n 整除.
  ]
)[
1. 考虑数的模  n  余数

   任何一个正整数  a  都可以表示为：
   
   $a = q * n + r$
   
   其中， q  是商， r  是余数，且  $0 ≤ r < n$ 。

   因此，每个正整数在除以  n  后，其余数  r  只能取  $0, 1, 2, ……, n-1$  这  n  个可能的值。

2. 应用鸽巢原理

   - 我们有  n + 1  个正整数，每个数在除以  n  后有  n  种可能的余数。
   - 根据鸽巢原理，当我们有  n + 1  个“鸽子”放入  n  个“鸽巢”中时，至少有一个“鸽巢”中有至少两只“鸽子”。

   在这里，“鸽子”代表  n + 1  个正整数，“鸽巢”代表余数  $0, 1, 2, ……, n-1$ 。

3. 得出结论

   根据鸽巢原理，至少存在两个不同的正整数  a  和  b ，使得它们在除以  n  后的余数相同。即：$a #sym.eq.triple b (mod n)$
   
   这意味着：$a-b #sym.eq.triple 0 (mod n)$ $#sym.arrow.r.double$ n 整除 （a-b）
   
   
   因此，这两个数的差  a - b  能被  n  整除。

综上所述， 该命题得证。  
]

== 第2章：排列组合<ch2>

=== $P_48,3.$

#showybox(
  title: [
    12个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？
  ]
)[
对于12个人围坐在圆桌上的排列，总的不同排列数为：$(12 - 1)! = 11!$

如果A和B必须相邻，可以将A和B视为一个整体（记为AB或BA），这样就有11个“单位”需要排列。这些排列数为：$(11 - 1)! × 2 = 10! × 2$

要得到A和B不相邻的排列数，只需从总排列数中减去A和B相邻的排列数：$11! - 2 × 10! = 10! × (11 - 2) = 9 × 10!$

所以，A和B不相邻的不同排列数为 $9 × 10!$ 种。
]

=== $P_48,4.$

#showybox(
  title: [
有颜色不同的四盏灯.
+ 把它们按不同的次序全部挂在灯竿上表示信号，共有多少种不同的信号？ 
+ 每次使用一盏、二盏、三盏或四盏灯按一定的次序挂在灯竿上表示信号,   共有多少种不同的信号？ 
+ 在(2)中，如果信号与灯的次序无关，共有多少种不同的信号？
  ]
)[
(1) 对于4盏不同颜色的灯，全部挂上灯竿的排列数为4的全排列数：$4! =4×3×2×1=24$
][
(2) 使用k盏灯的排列数为 $P^k_4 = 4!/(4-k)!$，其中 k = 1, 2, 3, 4。

- 当 k = 1 时，使用1盏灯的排列数为 $P^1_4 = 4!/(4-1)! = 4$；
- 当 k = 2 时，使用2盏灯的排列数为 $P^2_4 = 4!/(4-2)! = 12$；
- 当 k = 3 时，使用3盏灯的排列数为 $P^3_4 = 4!/(4-3)! = 24$；
- 当 k = 4 时，使用4盏灯的排列数为 $P^4_4 = 4!/(4-4)! = 24$。

共有4+12+24+24=64种不同的信号。
][
(3) 使用k盏灯的排列数为 $C^k_4 = 4!/((4-k)!k!)$，其中 k = 1, 2, 3, 4。

- 当 k = 1 时，使用1盏灯的排列数为 $C^1_4 = 4!/((4-1)!1!) = 4$；
- 当 k = 2 时，使用2盏灯的排列数为 $C^2_4 = 4!/((4-2)!2!) = 6$；
- 当 k = 3 时，使用3盏灯的排列数为 $C^3_4 = 4!/((4-3)!3!) = 4$；
- 当 k = 4 时，使用4盏灯的排列数为 $C^4_4 = 4!/((4-4)!4!) = 1$。

共有4+6+4+1=15种不同的信号。
]


=== $P_49,6.$

#showybox(
  title: [
    把q个负号和p个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有$vec(p+1,q)$种 
  ]
)[
1. 先排列  p  个正号，形成  p+1  个间隙

2. 从这  p+1  个间隙中选择  q  个放置负号，确保负号不相邻。

3. 不同的排法数为 $vec(p+1,q)$ 。
]

=== $P_49,13.$

#showybox(
  title: [
    计数从$(0,0)$点到$(n,n)$点的不穿过直线 $y = x$ 的非降路径数.
  ]
)[
从可以先从$(0,0)$到达$(0, 1)$或者$(1, 0)$，这两个点到$(n,n)$而不穿过$y=x$的非降落路径数是相等的。于是可以考虑从$(1,0)$到$(n，n)$不穿过直线$y=x$的非降落路径数，由于不穿过$y=x$，那么必定是要经过点$(n, n-1)$。

从$(1,0)$到$(n,n-1)$的非降落路径数为：$C_(2n-2)^(n-1)$。

从$(1, 0)$到$(n, n-1)$穿过直线$y=x$的非降落路径和从$(0, 1)$到$(n, n-1)$的非降落路径是对称的等于：$C_(2n-2)^(n)$

于是从点$(0, 0)$点到$(n, n)$点的不穿过直线$y=x$的非降落路径数为：

$ 2 times (C_(2n-2)^(n-1) - C_(2n-2)^(n)) = 2 times ((2n-2)!/(n!(n-1)!) - (2n-2)!/(n!(n-2)!)) = 2 times (2n-2)!/(n!(n-1)!) = 2/n C_(2n-2)^(n-1) $
]

=== $P_50,23.$

#showybox(
  title: [
    $5$ 封不同的信用通信通道传送，在两封信之间至少要放$3$个空格，一共要加入$15$个空格，问有多少种方法？
  ]
)[
$5$封信一共有$A_5^5=120$种排列，$5$封信之间有$4$个间隔，每个间隔至少要放$3$个空格，共$12$个空格，剩下$15-12=3$个空格可以放在$4$个间隔的任意位置，等价于$x_1+x_2+x_3+x_4=3$的整数解个数，即$C_(3+4-1)^(4-1)=C_6^3=20$种方法。所以一共有$120*20=2400$种方法。
]