美文网首页
(1)整数

(1)整数

作者: 古剑诛仙 | 来源:发表于2019-07-11 19:29 被阅读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
image.png
image.png

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

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

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

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

施塔特中心的地板砖问题

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


image.png
image.png

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

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

  1. 本次证明采用数学第一归纳法
  2. 设谓词P(n)为对于非负整数n,设计师的要求能够满足。
  3. P(0)成立因为B雕像占据了整个大厅(不需要铺瓷砖)。
  4. 假设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来证明:

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

  2. 设谓词P(n)为对于非负整数n,可以把B雕像放2^n正方形的任意位置,其余的部分铺上L形瓷砖。。

  3. P(0)成立因为B雕像占据了整个大厅(不需要铺瓷砖)。

  4. 假设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)

  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)

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

  1. 声明证明使用的是第二数学归纳法
  2. 推理部分要假设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
image.png
image.png
image.png
image.png
image.png
image.png image.png
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,同时称ab的一个因子,ba的倍数。

以下是一些常见的性质:

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

带余除法定义:当整数a,正整数d,整数q和r(0\leq r<q)满足a=dq+rq,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)

同余的性质:

  1. a,b(a\geq b)为整数,m为正整数,当a,bm同余,则有a=b+km(k为整数)
  2. a\equiv b(mod\ m)c\equiv d(mod\ m),则a+c\equiv b+d(mod\ m)ac\equiv bd(mod\ m)

相关文章

  • (1)整数

    主要内容参考自初等数论及其应用第六版 1 数和序列 良序性质:每个非空的正整数的集合都有一个最小的元素 有理数与无...

  • 条件判断语句

    整数1 -eq 整数2:判断整数1和整数2是否相等 整数1 -ne 整数2:判断整数1是否不相等整数2...

  • 1 整数计算

    例如 a=10 ,我们需要给出十个数字给出名称,在加上10,100,1000这个三个 共13个 1.1 五个算数基...

  • 整数的秘密

    一.整数的分类: 1.自然数:正整数、0 2.负整数 二.整数的意义 正整数:大于零的整数。1是正整数的基本单位,...

  • 基本类型

    一、整型和浮点型 1、整数:int(其他语言有短整数、整数和长整数等,python没有区别) type(1) 输出...

  • 整除

    (1)1与0的特性:1是任何整数的约数,即对于任何整数a,总有1|a.0是任何非零整数的倍数,a≠0,a为整数,则...

  • 4-2/3整数类型

    整数类型用于表示整数。 整数类型分为两种: (1)有符号整数类型:可以表示正整数、0和负整数。 (2)无符号整数类...

  • swift 4.x 整数类型

    整数类型用于表示整数。 整数类型分为两种:(1)有符号整数类型:可以表示正整数、0和负整数。(2)无符号整数类型:...

  • Python基础(一)数据类型和变量

    1. 数据类型和变量 1. 整数 (Python的整数没有大小限制)a: 数学中的任意大小的整数,包括正负整数b:...

  • 【从小白开始学python系列六】类型/字符串/标识符/对象/逻

    1、四种类型 python中数有四种类型:整数、长整数、浮点数和复数。 整数, 如 1 长整数 是比较大的整数 浮...

网友评论

      本文标题:(1)整数

      本文链接:https://www.haomeiwen.com/subject/awelkctx.html