[数学]具体数学第一章习题

Head Pic: 【ジブリ】"Ghibli sky" / Illustration by "Say HANa" [pixiv]

热身题

一、所有的马都有同样的颜色,我们可以对给定集合中的马匹数量运用归纳法来证明之。理由就是:“如果恰有一匹马,那么它与它自身有相同的颜色,故而基础是显然的。根据归纳法的步骤,假设有$n$匹马,标号从$1$到$n$。根据归纳假设,标号从$1$直到$n-1$的马都有同样的颜色,类似地,标号从$2$直到$n$的马也有同样的颜色。但是,处于中间位置标号从$2$直到$n-1$的马,当它们在不同的马群中时不可能改变颜色,因为这些是马,而不是变色龙。故而依据传递性可知,标号从$1$直到$n$马也必定有同样的颜色,于是全部$n$匹马都有同样的颜色。证毕。”如果这一推理有误,那么错在哪儿?

并未解决$n=2$时的情况。

二、把有$n$个圆盘的塔从左边的桩柱$A$移动到右边的桩柱$B$,不允许在$A$和$B$之间直接移动,求最短的移动序列。(每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出。像通常一样,较大的圆盘永远不能放在较小圆盘的上面。)

不妨假设$D_n$为$n$个盘按题示规则从$A$到$B$移动的最小次数,则
先从$A$到$B$移动$n-1$盘,需$D_{n-1}$;
底盘$A$到$C$,需$1$次;
先从$B$到$A$移动$n-1$盘,需$D_{n-1}$;
底盘$C$到$B$,需$1$次;
先从$A$到$B$移动$n-1$盘,需$D_{n-1}$;
总$D_n=3D_{n-1}+2$,易知$D_1=2$,解出封闭形式:$D_n=3^n-1$

三、证明,在上一题限制下的移动过程中,实际上,我们会在$3$根桩柱上都遇到$n$个圆盘的每一种正确的叠放。

每一个圆盘都可任意出现在三根柱上,即每个圆盘都有$3$种选择,由分步乘法原理有总共$3^n$种可能。

而由上题可知,最快的解法需要$3^n-1$种,再加上原本的摆放,得证。

四、是否存在$n$个圆盘在$3$根桩柱上的某种开始叠放或结束叠放,使得按照卢卡斯原来的规则,需要多于$2^n-1$次的移动?

当底盘在正确位置时,这个问题等价于移动$n-1$盘,即$T_{n-1}=2^{n-1}<2^n-1$;

否则,底盘在$A$时,有$T_n=2^n-1$;

当底盘在$B$时,有$T_{n-1}+1=2^{n-1}\leq 2^n-1$

五、由$3$个重叠的圆做成的维恩图常用来描述与$3$个给定集合有关的$8$个可能的子集:由$4$个给定集合给出的16种可能的子集能否用$4$个重叠的圆来描述?

13子集和一个全集,总共14个。

六、平面上由$n$条直线定义的某些区域是无界的,而另一些区域则是有界的。有界区域的最大个数是多少?

由图可知,减去无界区域即损失$2n$个。
记$E_n$为平面$n$条直线定义有界区域。
则$E_n=L_n-2n=\frac{n(n+1)}{2}+1-2n$

七、设$H(n)=J(n+1)-J(n)$。方程(1.8)告诉我们有$H(2n)=2$,而对$n\geq1$有

$$H(2n+1)= J(2n+2)-J(2n-1)=(2J(n+1)-1)-(2J(n)+1_=2H(n)-2$$

于是,看起来有可能通过对$n$用归纳法,证明对所有$n$都有$H (n) = 2$。这里什么地方有错?

$H(1)=J(2)-J(1)=2J(1)-1-J(1)=0\neq 2$
归纳法基础便未成立。

作业题

八、解递归式
$$Q_0=\alpha; Q_1=\beta;$$

$$Q_n=\frac{1+Q_{n-1}}{Q{n-2}} , n>1$$

假设对所有$n\geq0$都有$Q_n\neq0$。提示:$Q_4=\frac{1+\alpha}{\beta}$

$Q_0=\alpha,Q_1=\beta,Q_2=\frac{1+\beta}{\alpha}$
$Q_3=\frac{\alpha+\beta+1}{\alpha\beta},Q_4=\frac{1+\alpha}{\beta}$
$Q_5=\alpha$
循环出现。

九、有时可以利用反向归纳法,它是从$n$到$n-1$来证明命题,而不是相反!例如,考虑命题

$$P(n):\prod_{k=1}^{n}x_k\leq(\frac{\sum_{k=1}^{n}x_k}{n})^n$$

这对$n=2$为真,因为$(x_1+x_2)^2-4x_1x_2=(x_1-x_2)^2\geq0$。

a 令$x_n=(x_1+…x_{n-1})/(n-1)$,证明只要$n>1$,$P(n)$就蕴涵$P(n-1)$。

b 证明$P(n)$和$P(2)$蕴涵$P(2n)$。
c 说明为什么这就蕴涵了$P(n)$对所有$n$为真。

a

由题有:其假设$P(n)$成立,即:
$$\prod_{k=1}^{n}x_k\leq\left(\frac{\sum_{k=1}^{n}x_k}{n}\right)^n$$
将$x_n=\frac{\sum_{k=1}^{n-1}x_k}{n-1}$,代入,有:
$$\left(\prod_{k=1}^{n-1}x_k\right)\times \frac{\sum_{k=1}^{n-1}x_k}{n-1}\leq\left(\frac{(\sum_{k=1}^{n-1}x_k)+\frac{\sum_{k=1}^{n-1}x_k}{n-1}}{n}\right)^n$$
$$\left(\prod_{k=1}^{n-1}x_k\right)\times \frac{\sum_{k=1}^{n-1}x_k}{n-1}\leq\left(\frac{\sum_{k=1}^{n-1}x_k}{n-1}\right)^n$$
即有$P(n-1)$:
$$\prod_{k=1}^{n-1}x_k\leq\left(\frac{\sum_{k=1}^{n-1}x_k}{n-1}\right)^{n-1}$$

b

由$P(n)$有:

$$\prod_{k=1}^{n}x_k\leq\left(\frac{\sum_{k=1}^{n}x_k}{n}\right)^n,\quad \prod_{k=n+1}^{2n}x_k\leq\left(\frac{\sum_{k=n+1}^{2n}x_k}{n}\right)^n$$

由同向不等式可乘性有:

$$\prod_{k=1}^{2n}x_k\leq\left(\frac{\sum_{k=1}^{n}x_k}{n}\times\frac{\sum_{k=n+1}^{2n}x_k}{n}\right)^n$$

由$P(2)$(基本不等式)有:

$$\frac{\sum_{k=1}^{n}x_k}{n}\times\frac{\sum_{k=n+1}^{2n}x_k}{n}\leq\left(\frac{\sum_{k=1}^{2n}x_k}{2n}\right)^2$$

即:

$$P(2n):\quad \prod_{k=1}^{2n}x_k\leq\left(\frac{\sum_{k=1}^{2n}x_k}{2n}\right)^{2n}$$

c

欲求$P(n)$,可求$P(2n)$,再求$P(2n-1)$如此往复直到$P(n)$

十、设$Q_n$是将一个有$n$个圆盘的塔从$A$移动到$B$所需要的最少移动次数,要求所有的移动都必须是顺时针方向的,也就是说,从$A$到$B$,从$B$到其他的桩柱,再从其他的桩柱到$A$。又设$R_n$是在这一限制下从$B$返回到$A$所需要移动的最少次数。证明

$$ Q_n=\left\{ \begin{aligned} 0 & ,n=0 \\ 2R_{n-1}+1 & ,n>0\\ \end{aligned} \right. $$

$$ R_n=\left\{\begin{aligned}0 & ,n=0 \\Q_{n}+Q_{n-1}+1 & ,n>0\\\end{aligned}\right. $$

(无需解这些递归式,我们将在第7章里介绍怎样做。)

移动到$C$等价于移动到另一柱。

对1⃣️:

先将$n-1$盘从$A$移动到$C$,需$R_{n-1}$次

再将底盘从$A$移动到$B$,需$1$次

再将$n-1$盘从$C$移动到$B$,需$R_{n-1}$次

共$2R_{n-1}+1$次

即$Q_n=2R_{n-1}+1$

对2⃣️:

同理有$R_n=2R_{n-1}+1+Q_{n-1}+1$

代入$Q_n$,有$R_n=Q_n+Q_{n-1}+1$

十一、双重河内塔包含$2n$个圆盘,它们有$n$个不同的尺寸,每一种尺寸的圆盘有两个。如通常那样,要求每次只能移动一个圆盘,且不能把较大的圆盘放在较小的圆盘上面。
a 如果相同尺寸的圆盘是相互不可区分的,要把一个双重塔从一根桩柱移动到另一根桩柱需要移动多少次?
b 如果在最后的排列中要把所有同样尺寸的圆盘恢复成原来的从上到下的次序,需要移动多少次?

提示:这是一个难题,实在应该是个“附加题”。

a

记$A_n$为$n$种尺寸圆盘按题设要求移动的最少次数。

不在意相同圆盘次序时,每一步只是多移动相同一步,故$A_n=2T_n$。

b

记$B_n$为$n$种尺寸圆盘按题设要求移动的最少次数。

$n-1$盘,$A\to B$,需$A_{n-1}$

上底盘,$A\to C$,需$1$

$n-1盘$,$B\to C$,需$A_{n-1}$

下底盘,$A\to B$,需$1$

$n-1盘$,$C\to A$,需$A_{n-1}$

上底盘,$C\to B$,需$1$

$n-1盘$,$A\to B$,需$A_{n-1}$

共$B_n=4A_{n-1}+3$

十二、我们进一步推广习题11a。假设有$n$个不同尺寸的圆盘,且恰好有$m_k$个圆盘的尺寸是$k$.当相同尺寸的圆盘被视为不可区分的时候,确定移动一个塔所需要的最少移动次数$A(m_1,..,m_n )$。

直接类比得到$A(m_1,…,m_n)=2A(m_1,…,m_n-1)+m_n$

十三、由$n$条$Z$形线所定义的区域的最大个数是多少?每条$Z$形线由两条平行的无限半直线和一条直线段组成。

![]()

一个$Z$形线,可以看成两平行线交一条线段,而这又可以从三条直线都相交的情况减去一个区域得到。

这样会失去$4$个区域,推广到$n$的情况,$ZZ_n=L_{3n}-n-4n=\frac{9}{2}n^2-\frac{7}{2}n+1$

十四、在一块厚奶酪上划出五道直的切痕,可以得到多少块奶酪?(在你划切痕时,奶酪必须保持在它原来的位置上,且每道切痕必定与三维空间中的一个平面相对应。)对$P_n$求一个递归关系,这里$P_n$表示$n$个不同的平面所能定义的三维区域的最大个数。

一维情况,即$x_n=n+1$

实际上二维情况就是原来的区域加上新产生的$n$个交点,即:$L_n=x_{n-1}+L_{n-1}$

同理,三位情况便是:$P_n=L_{n-1}+P_{n-1}$

更精妙的解法:

$x_n=\begin{pmatrix}n \\0\end{pmatrix}+\begin{pmatrix}n \\1\end{pmatrix}$

$L_n=\begin{pmatrix}n \\0\end{pmatrix}+\begin{pmatrix}n \\1\end{pmatrix}+\begin{pmatrix}n \\2\end{pmatrix}$

$P_n=\begin{pmatrix}n \\0\end{pmatrix}+\begin{pmatrix}n \\1\end{pmatrix}+\begin{pmatrix}n \\2\end{pmatrix}+\begin{pmatrix}n \\3\end{pmatrix}$

最后修改:2019 年 06 月 07 日 10 : 06 AM

1 条评论

  1. Cinema

    滴!访客卡!请上车的乘客系好安全带,现在是:Fri Aug 02 2019 20:11:23 GMT+0800 (China Standard Time) Test

发表评论