具体数学第二版第一章习题（1）

1、当$n=2$时，区间$[2,n-1]$为空，所以当$n=2$时不能证明2匹马颜色相同。

2、三根柱子ABC。假设$n$个盘子的答案为$f(n)$.最后一个盘子一定是A->C->B，所以整个过程分为5步：（1）将上面$n-1$个盘子从A->C->B,即$f(n-1)$;（2）将第$n$个盘子放到C上； （3）将B上的$n-1$个盘子通过C移动到A,即$f(n-1)$;（4）将C上的第$n$个盘子移动到B；（5）最后将A上的$n-1$个盘子移动到B，即$f(n-1)$。所以$f(n)=3f(n-1)+2, f(1)=2$,所以$f(n)=3^{n}-1$.

3、三根柱子的证明是类似的。下面只证明第一根柱子。数学归纳法：

（1）当$n=1$时，很明显，第一个柱子上出现过$2^1=2$种一个盘子的排列。

（2）假设$[1,n-1]$时，都满足情况；

（3）对于$n$ 个盘子的情况，在第二题的第一步开始到第一步结束过程中，第一根柱子上出现过$n-1$个盘子的所有排列，此时有第$n$个盘子；在第二题的第五步开始到结束，第一根柱子上仍然出现过$n-1$个盘子的所有排列，此时没有第$n$个盘子。所以所有$n$个盘子的排列都出现过。

4、数学归纳法：

（1）$n=1$时显然有$g(1) \le 2^{1}-1=1$

（2）假设$[1,n-1]$个都满足

（3）对于$n$个盘子，假设它在第三根上，那么$g(n)=g(n-1)$;否则假设它在第二根柱子上，那么可以将其他的$n-1$个先移动到第一根柱子上，需要$g(n-1)$，然后将第$n$个盘子移动到第三根上，然后再把第一根柱子上的$n-1$个盘子移动到第三根上，需要$2^{n-1}-1$步，所以$g(n)=g(n-1)+1+2^{n-1}-1 \le 2^{n-1}-1+1+2^{n-1}-1=2^{n}-1$

5、不能。因为两个圆最多两个交点，所以第四个圆最多跟前面的三个圆有6个交点，每个交点增加一个区域，所以最多有14个区域。

6、三条直线组成三角形，有一个封闭区域。后面第$i$条直线与前面$i-1$条有$i-1$个交点，增加$i-2$个区域，所以答案为$\sum_{i=3}^{n}(i-2)=\frac{(n-1)(n-2)}{2}$

7、$H(1)=J(2)-J(1)=0 \ne 2$

8、$Q_{2}=\frac{1+\beta }{\alpha }$,$Q_{3}=\frac{1+\alpha +\beta }{\alpha \beta }$,$Q_{4}=\frac{1+\alpha }{\beta }$,$Q_{5}=\alpha $,$Q_{6}=\beta $

9、（1）将$x_{n}$带入，明显等式成立。

（2）由于$P(n)$成立，即$\prod_{i=1}^{n}x_{i}\leqslant (\frac{\sum_{i=1}^{n}x_{i}}{n})^{n}$，所以有$\prod_{i=n+1}^{2n}x_{i}\leqslant (\frac{\sum_{i=n+1}^{2n}x_{i}}{n})^{n}$。将两个式子相乘得到：

$\prod_{i=1}^{2n}x_{i}\leqslant (\frac{\sum_{i=1}^{2n}x_{i}}{n}\frac{\sum_{i=n+1}^{2n}x_{i}}{n})^{n}$

而$xy\leq (\frac{x+y}{2})^2$,所以$ \frac{\sum_{i=1}^{2n}x_{i}}{n}\frac{\sum_{i=n+1}^{2n}x_{i}}{n}\leq \left (\frac{\sum_{i=1}^{2n}x_{i}}{2n}  \right )^{2}$, 从而得到$P(2n)$成立

（３）$P(2)$->$P(4)$->$P(3)$->$P(6)$->…

最后关于这个不等式的证明。

设$f(x)=e^{x-1}-x$,通过求导可以看出$f(x)$在$x=1$时取得最小值０，所以$f(x)\geq 0$，即$x \leq e^{x-1}$

对于要证明的式子，如果$x_{i}=0$，那么显然成立。下面假设都大于０．令$a=\frac{\sum_{i=1}^{n}x_{i}}{n}>0$，那么对任意的$x_{i}$有$\frac{x_{i}}{a}\leq e^{\frac{x_{i}}{a}-1}$ .所有式子相乘得到：$\frac{\prod_{i=1}^{n}x_{i}}{a^n}\leq e^{\sum_{i=1}^{n}\frac{x_{i}}{a}-n}=e^{n-n}=1$,所以$\prod_{i=1}^{n}x_{i}\leq a^{n}=\left ( \frac{\sum_{i=1}^{n}x_{i}}{n} \right )^n$

10、对于一个环Ａ->B->C->A,$Q_{n}$表示A->B或者B->C或者C->A，而$R_{n}$表示A->B->C或者B->C->A或者C->A->B。

对于$Q_{n}$来说，分三步：（１）将上面$n-1$个从Ａ->B->C;（２）将第$n$个从A到B,（３）将剩下的$n-1$个从C->A->B。所以$Q_{n}=2R_{n-1}+1$

对于$R_{n}$来说，分五步：（１）将上面$n-1$个从Ｂ->C->A;（２）将第$n$个从B到C,（３）将A上的$n-1$个从Ａ->B,（４）将Ｃ上的第$n$个放到A;（５）将Ｂ上的$n-1$个从B->C->A.所以$R_{n}=R_{n-1}+1+Q_{n-1}+1+R_{n-1}=Q_{n}+Q_{n-1}+1$　

11、（1）令$P_{n}$表示$2n$个圆盘从A移动到C的解.分为三步：（1）将上面的$2(n-1)$个从A挪到B，需要$P_{n-1}$;（2）将A上剩下的两个移动到C,需要两步;（3）将B上的盘子移动到C,需要$P_{n-1}$。所以$P_{n}=2P_{n-1}+2,P_{1}=2$,所以$P_{n}=2^{n+1}-2$

（2）设$Q_{n}$表示$2n$个盘子的答案，分为7步：（1）将上面$2(n-1)$个盘子移动到C,需要$P_{n-1}$;(2)第大小为$n$的上面一个盘子移动到B;(3)将C上的$2(n-1)$个盘子移动到B，需要$P_{n-1}$;(4)将最后一个盘子移动到C;(5)将B的上面$2(n-1)$个盘子移动到A,需要$P_{n-1}$;（6）将B上的剩下的一个盘子移动到C;(7)将A的$2(n-1)$个盘子移动到C,需要$P_{n-1}$,所以$Q_{n}=4P_{n-1}+3=2^{n+2}-5$

12、令$F(m)$表示移动$m$类，第$i$类个数为$n_{i}$的方案数。那么有：（1）$F(1)=n_{1}$;(2)$F(m)=2F(m-1)+n_{m}$。所以$F(m)=\sum_{i=1}^{m}2^{m-i}n_{i}$

13、令$F(n)$表示$n$个Z型线的答案。$L(n)$表示$n$条直线的答案。$L(n)=\frac{n(n+1)}{2}+1$.首先将一个Z型线，看作三条直线，那么此时$F(n)=L(3n)$。但是一个Z型线比三条互不平行的直线少了5个区域，所以$F(n)=L(3n)-5n=\frac{9n^{2}-7n}{2}+1$

14、$L(n)$表示$n$条直线在二维平面划分的区域的答案。那么在三维空间中，第$n$次切割所增加的块的个数就是这一次切割处的面上的区域数，所以$P(n)=P(n-1)+L(n-1),P(1)=2$,所以$P(n)=\frac{1}{6}(n+1)(n^{2}-n+6)$

15、首先$I(2)=2,I(3)=1$.对于$n>=4$来说，（1）如果$n$是偶数，那么第一轮将删掉2,4,6,…,n。下面重新从1开始计数，所以此时$I(n)=2I(\frac{n}{2})-1$;（2）如果$n$是奇数，那么第一轮可以删掉 2,4,6,…,$n-1$,1,接下来从3开始计数，所以此时$I(n)=2I(\frac{n-1}{2})+1$。也可以这样写$I(2)=2,I(3)=1,I(2n)=2I(n)-1,I(2n+1)=2I(n)+1, n\geq 2$