（1）整数

2019-07-11 本文已影响0人古剑诛仙

主要内容参考自初等数论及其应用第六版

1 数和序列

良序性质：每个非空的正整数的集合都有一个最小的元素

有理数与无理数：如果存在整数 $p和q\neq 0$ ，使得 $r=p/q$

最大整数：将实数 $x$ 中的最大整数记作 $[x]$ ，是小于或等于x的最大整数，即一个整数满足
$[x]\leq x<[x]+1$

最大整数的一个性质就是：当 $n$ 为整数，对任意实数 $x$ ，有 $[x+n]=[x]+n$

实数 $x$ 的分数部分记作{ $x$ }，等于 $x-[x]$ ，相应的 $[x]$ 也叫作 $x$ 的整数部分

狄利克雷逼近定理：如果 $x$ 是一个实数， $n$ 是一个正整数，则存在整数 $a，b，1\leq a\leq n$ ，使得 $|ax-b|\leq1/(n+1)$

集合可数：一个集合可数，如果它是有限或者是无穷但与正整数集合之间存在一一映射。如果都不满足则集合不可数。有理数集合是可数集，无理数集合是不可数集，实数集也是不可数集。

2 和与积

$\sum_{j=m}^{n}ca_{j}=c\sum_{j=m}^{n}a_{j}$
$\sum_{j=m}^{n}(a_{j}+b_{j})=\sum_{j=m}^{n}a_{j}+\sum_{j=m}^{n}b_{j}$
$\sum_{i=m}^{n}\sum_{j=p}^{q}a_{i}b_{j}=(\sum_{i=m}^{n}a_{i})(\sum_{j=p}^{q}b_{j})=\sum_{j=p}^{q}\sum_{i=m}^{n}a_{i}b_{j}$

3 数学归纳法

稍微说一下，归纳法分为两种，第一种是完全归纳法，是将一类事物的全部对象都考虑进去而做出可靠推理的方式，；第二种是不完全归纳法，是将一类事物的多个对象考虑进去而做出的不可靠推理的方式，其结论是可能会错的。在数学推理中，由于经常要面临无穷的情况，很难做到完全归纳，所以我们采用本质上是演绎法的数学归纳法来完成证明。

下面是一些不完全归纳法的例子：

image.png

第一数学归纳定理：一个包含整数1的正整数集合如果具有以下性质，即若其也包含整数k，则一定包含k+1，则这个集合一定是所有正整数的集合

通常而言，使用第一数学归纳法都可以遵循下面这个模版：

声明接下来的证明会采用归纳法。
定义正确的谓词P，P(n)通常被称作“归纳假设”。归纳最后得到的结论就是对于所有非负整数p(n)均成立。一个清晰的归纳假设通常是归纳法中最重要的一步，所以不要简写！简单的情况下P就是你要证明的东西，但有些时候P可能会包含一些变量，这个时候就要说明清楚哪一个是n。
证明P(0)成立。
证明对于所有非负整数n，P(n) -> P(n + 1)。即假设P(n)成立，然后利用P(n)成立这个假设推出p(n + 1)也是成立的。要注意的是，我们必须保证P(n) -> P(n + 1)对于所有非负整数都是能够成立的，即“推理链条”不能被中断（本文最后会有一个反面例子）。
由归纳法得出结论。

下面以一个具体的例子说明：

施塔特中心的地板砖问题

几年前MIT打算建一座名叫施塔特中心的建筑物，但是在建筑过程中发生了资金不足的情况。校董事会商议后决定邀请社会人士捐款，并为捐款最多的一位做一座雕像B立在大厅。这个建筑的设计师设计的大厅形状是一个由瓷砖铺成的长宽为2^n的正方形，而且采用的瓷砖也很特别，是一个由三个1 * 1正方形组成的L形瓷砖，如下图所示：

image.png

设计师的方案对于n的取值又要求吗？还是说对于任意非负整数n都能满足呢？

下面利用第一数学归纳法对其进行证明：

本次证明采用数学第一归纳法
设谓词P(n)为对于非负整数n，设计师的要求能够满足。
P(0)成立因为B雕像占据了整个大厅（不需要铺瓷砖）。
假设P(n)成立，即对于一个2^n长宽的正方形，我们可以把B雕像放在中心位置，其余的部分铺上L形瓷砖。

这个时候问题发生了，我们不能由P(n)推出P(n + 1)，因为我们只能得到可以在2^(n + 1)的正方形中心的四个对角方向的“中心”可以放置B雕像。

当这种情况发生时，首先的想法应该是找一个更加普遍或者说强壮的归纳假设，也就是之前归纳假设的超集。例如在这题中，我们可以把P(n)变为对于一个2^n长宽的正方形，我们可以把B雕像放在其中的任意位置，其余的部分铺上L形瓷砖。

这看起来有些奇怪——“如果你证明不了A，那就证明比A更普遍的B”——但是在归纳法中确实是这样的，因为我们在推P(n + 1)的时候也可以获得更好的条件。当然，增强后的P(n)首先要是（至少感觉上）是正确的。下面就采用增强后的P来证明：

本次证明采用数学第一归纳法
设谓词P(n)为对于非负整数n，可以把B雕像放2^n正方形的任意位置，其余的部分铺上L形瓷砖。。
P(0)成立因为B雕像占据了整个大厅（不需要铺瓷砖）。
假设P(n)成立，即对于一个2^n长宽的正方形，我们可以把B雕像放在其中的任意位置，其余的部分铺上L形瓷砖。那么对于P(n + 1)，即一个2^(n+1)长宽的正方形，我们可以将其分为四个2^n的正方形，而对于其中的每个正方形，由于P(n)成立，我们将其中的任意三个正方形的对角的那个1*1正方形空出来，在2^(n+1)的正方形中心形成一个L形，并铺上一块瓷砖，这个时候我们就可以在剩下的那个2^n的正方形中任意放置B雕像了，如下图所示：

image.png

5.由归纳法得出对于非负整数n，我们可以把B雕像放在一个2^n长宽的正方形中的任意位置，其余的部分铺上L形瓷砖。

所以我们当然也可以把雕像放在中心位置了。可以看到，我们不仅证明了一个更强的结论，还找到了实现这种结论的算法。

如前面所说，在进行p(n) -> p(n + 1)这步时，我们必须保证P(n) -> P(n + 1)对于所有非负整数都是能够成立的，即“推理链条”不能被中断。这里举出一个有名的反面教材，证明所有的马都是一种颜色：

1.本次证明使用第一数学归纳法。

2.设命题P(n)为对于任意n匹马（n>=1)，它们的颜色一样。

3.这个命题对n=1时成立，即，只有1匹马时，马的颜色只有一种。

4.假设这个命题对n成立，即假设任何n匹马都是一种颜色。那么当我们有n+1匹马时，不妨把它们编好号：

1, 2, 3……n, n+1 ，对其中（1、2……n）这些马，由我们的假设可以得到，它们都是同一种颜色；对（2、3……n、n+1）这些马，我们也可以得到它们是一种颜色；由于这两组中都有（2、3、……n）这些马，所以可以得到，这n+1种马都是同一种颜色。即P(n) -> p(n + 1)

得到所有的马颜色相同。

这个证明的错误来于推理的第二步：当n=1时，n+1=2，此时马的编号只有1、2，那么分的两组是（1）和（2）——它们没有交集，所以第二步的推论是错误的。数学归纳法第二步要求n→n+1过程对n=1，2，3……的数都成立，而上面的证明就好比多米诺骨牌的第一块和第二块之间间隔太大，推倒了第一块，但它不会推倒第二块。即使我们知道第二块倒下会推倒第三块等等，但这个过程早已在第一和第二块之间就中断了。在本例中P(0)的条件应该是n=1。

强归纳形式的第二数学归纳定理：第二数学归纳法证明的结论和第一数学归纳法是一样的，都是证明（局部）非负数元素都具有某些性质。但是第二数学归纳法中P(n)的推理是基于P(0~n)而非仅仅是P(n)。

第二数学归纳法（Strong Induction），设P是作用在非负整数的谓词：

P(0)成立
对于所有的n，P(0), P(1), P(2) ... P(n)共同推出P(n + 1)
则对于所有的非负整数m，P(m)成立

可以看到，在使用第一数学归纳法的时候我们只用了P(n)，而第二数学归纳法相比于第一数学归纳法在推P(n + 1)的时候使用更多的假设P(0), P(1), P(2) ... P(n)

第二数学归纳法使用的模版和第一数学归纳法很像，除了两个地方：

声明证明使用的是第二数学归纳法
推理部分要假设P(0), P(1), P(2) ... P(n) 都是正确的。

下面是两个示例:

硬币问题

在太平洋上有一个叫做Inductia的国家，他们使用一种叫做Strong的硬币（简称Sg）。当年在印刷这种硬币的时候由于经费问题就只印刷了面值为3Sg和5Sg的硬币。虽然当地居民在找小额零钱（例如4Sg或者7Sg）的时候会有一些麻烦，但是他们发现任何大于等于8Sg的面额都能使用这两种硬币找开，例如26Sg可以用下面这种方案：

image.png

请给出证明。

下面使用第二数学归纳法证明。

设P(n)为对于8+n面额的钱，居民们可以用3Sg和5Sg的硬币找开。
当n=0，8Sg = 5Sg + 3Sg，所以P(0)成立。
设p(0)，p(1)，p(2) ... p(n)均成立(n > 2)，证明p(n + 1)成立：对于8 + n + 1的面额，可以前将其变为(8 + n + 1 - 3) + 3即(8 + n - 2) + 3这样的面额，由于我们已经假设了P(n - 2)的成立，所以(8 + n - 2) + 3可以由P(n - 2)的方案加上一个3Sg的硬币组合而成，所以P(n + 1)成立。对于n <=2：n = 2时，10 = 5 + 5；n = 1时，9 = 3*3。（这里要注意将n小于等于2的情况分开讨论，因为P(n-2)在n<2的时候没有定义，即归纳推理的“链条”不能断）
由归纳法，所有大于等于8Sg的面额居民都能用这两种硬币找开。

堆垛游戏

在你的面前是一个由n个木块堆起来的堆垛，你每次可以将一个堆拆成两个堆，除非这个堆只剩下了一个木块。在每次分拆一个堆的时候你可以获得一些分数，例如，你将一个a+b块木块的堆拆成了a块的堆和b块的堆，你就可以得到a*b分。直到所有的堆都只含一个木块，游戏结束。例如，下图显示了一个拆一个由10个木块组成的堆的一种方案，其得分为45分 :

image.png

设请问你该采取什么策略能获得最高的分数？

我的第一想法是每次都把堆拆成两个相同高度的堆或者相差为1，例如5*5 = 25 > 1 * 9，但随后我意识到虽然第一次可能会大，但是随后可能会比较小，例如2 * 3 < 1 * 8。联想到这个题是要用归纳法的，自然觉得可能和策略无关，即不管什么策略都会得到相同的分数。试一下上面这个例子，每次都只拿走一个木块：9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45，果然是这样，其中1+2+3 ... +n = (n+1)*n/2，下面证明：

以下证明使用第二数学归纳法。

设P(n)为对于木块数为n的堆垛，其得分为n*(n+1)/2，和策略无关。
P(0) = 0，即0*(0+1)/2 = 0，成立。
设P(1), P(2), P(3) ... P(n)成立。对于P(n + 1)，假设我们拆的第一步将其分为了木块数分别为a和b的两个堆，第一次得分为a*b，由于a和b都小于n+1，由P(a)和P(b)成立，我们可以知道最终的总得分为第一次的得分ab加上拆剩下两个堆的分数之和：ab + a*(a+1)/2 + b*(b+1)/2 = (a^2 + b^2 + ab + a + b)/2 = (a^2 + b^2 +2ab + n + 1)/2 = ( (a+b)^2 + (n+1) )/2 = ((n+1)^2 + (n+1))/2 = (n+1 + 1)(n+1)/2。所以推得P(n+1)成立。
由归纳法得到对于任意非负整数n，这个游戏的最终得分都是n*(n+1)/2，和策略无关。

在此之上数学归纳法还有很多变形，下面对其详细介绍：

image.png

数学归纳法的可靠性

image.png

递归定义：函数 $f$ 是递归的，如果指定了 $f$ 在1处的值，并且对于任意正整数 $n$ ，都有确定的规则来根据 $f(n)$ 确定 $f(n+1)$

4 斐波那契数列

这里只给出一些重要的性质，具体的证明和解答过程参考离散数学及其应用第七版内容。

斐波那契数列的定义：满足以下性质的序列—— $f_{1}=1,f_{2}=1,且对n\geq3,f_{n}=f_{n-1}+f_{n-2}$

重要性质1： $\sum_{k=1}^{n}f_{k}=f_{n+2}-1$

重要性质2：斐波那契数列比公比为 $q=(1+\sqrt{5})/2$ 的等比数列增长得快

斐波那契数列的通项公式：
$\alpha =\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2},f_{n}=\frac{1}{\sqrt{5}}(\alpha^n-\beta^n)$
可以通过线性其次递推关系和母函数两种方式得出，详细见组合数学第七章内容

5 整除性

整除定义：如果 $a,b$ 为整数且 $a\neq0$ ，则 $a整除b$ 意味着存在整数 $c$ ，使得 $b=ac$ ，记作 $a|b$ ，同时称 $a$ 是 $b$ 的一个因子， $b$ 是 $a$ 的倍数。

以下是一些常见的性质：

$如果a|b，则对所有整数c，有a|bc$
$如果a|b，b|c，则a|c$
$如果a,b,c是整数，且a|b,a|c，那么当m,n为整数时，有a|mb+nc$

带余除法定义：当 $整数a,正整数d,整数q和r(0\leq r<q)$ 满足 $a=dq+r$ ， $q,r$ 的值唯一，且称 $d$ 为除数， $a$ 为被除数， $q$ 是商， $r$ 是余数，分别用 $q=a\ div\ d，r=a\ mod\ d$ 表示

同余定义：当 $a,b(a\geq b)$ 为整数， $m$ 为正整数，而 $m|a-b$ ，则称 $a模m同余b$ ，记作 $a\equiv b(mod\ m)$ ，等价于 $a\ mod\ m=b\ mod\ m$ ，如果 $a,b$ 不是模 $m$ 同余的，则记作 $a\not\equiv b(mod\ m)$

同余的性质：

当 $a,b(a\geq b)$ 为整数， $m$ 为正整数，当 $a,b$ 模 $m$ 同余，则有 $a=b+km(k为整数)$
当 $a\equiv b(mod\ m)$ ， $c\equiv d(mod\ m)$ ，则 $a+c\equiv b+d(mod\ m)$ 且 $ac\equiv bd(mod\ m)$

（1）整数

1 数和序列

2 和与积

3 数学归纳法

4 斐波那契数列

5 整除性

猜你喜欢

热点阅读