0%

具体数学(Concrete Math)笔记(1)

暑假看了一些书,因此随手记录一下所学所想。

先从具体数学开始吧,由于博主只是个大一的本科生,数学基础并不扎实,欢迎指正错误。

本篇主要涉及具体数学第一章的内容,以及我对其中一些内容的拓展。

汉诺塔问题

开篇引入的就是很多人都熟知的问题,问题的介绍就不再赘述了。

设三根柱子分别为A,B,C,目标是将n个圆盘从柱子A移动到柱子C上,并记有n个圆盘的汉诺塔问题的最优解为Tn​,先考虑构造一个可行的方案:

将前n1个小的圆盘移动至B,再将最大的圆盘移动至C,最后将n1个圆盘移动至C

这是一个可行的方案,因此对最优解Tn,有Tn2Tn1+1,nN+

书中随后证明了所有可行解的次数都大于等于2Tn1+1,因此可以断言这是一个最优解​。

由此受到启发,可以抽象出一个证明某个解是最优解的思路:先证明该解是可行解,再证明所有的可行解都不会比该解更优。

直线分割平面问题

这个问题是高中数学的经典问题,但还可以从不同角度去探讨这个问题的解。

记最优解为Ln,先引入平面图欧拉公式:VE+F=2,其中V,E,F分别为顶点数,边数,区域数。注意欧拉公式中的边数不是直线数。

n​条直线可以至多形成n​个交点,考虑在平面上构造一个充分大的圆,使得所有的交点都在圆内,并与每条直线都有两个交点,共形成2n个交点。

将新形成的交点中在圆上相邻的点对用线段连接,形成2n条边,得到一个凸多边形。再删去圆和所有直线在凸多边形外的部分,此时这个凸多边形内部的区域数即Ln

从而,平面上的点数V=n(n1)2+2n=n2+3n2​​。原先的每条直线被n+1个点分割为n条边,则边数E=nn+2n=n2+2n

又由凸多边形外也是一个区域,代入平面图欧拉公式得VE+Ln+1=2,即Ln=n(n+1)2+1

下图是n=3​时的一个例子,其中绿色的点和红色的边分别为新形成的点和新形成的边。

Figure 1

约瑟夫问题

这个问题引申出来的内容就多一些了,并且我用线性空间对递推式的封闭形式进行了讨论。先规定n​​为人数,数到第m​​个人被选中,J(n)​为幸存者的编号,%为取模运算。

m=2的情形

书中先讨论的是m=2的情形,求解的方法是先选到只剩下n2个人,将问题转换成n2个人的情形。

由此受到启发,可以抽象出一些求递归式的问题的解法:先对问题进行有限步的处理,构造一个到n​更小的情形的单射,从而得到递归式。

例如在该问题中,先进行报数,剩下n2个人以 f(x)={x12,n is oddx+12,n is even 的方式进行重新编号,很显然这是一个单射,因此有逆映射 f1(x)={2x+1,n is odd2x1,n is even 此时即可转换为人数为n2​时的情形,幸存者编号为x=J(n2)​​​。则人数为nJ(n)=f1(x)​,整理一下即为书上的形式。

事实上,这个思路运用的非常广泛,并且通常来说最开始有限步的处理会影响到用递推式求解的复杂度。例如考虑m​为任意正整数的情况:

为方便讨论,将每个人的标号记成0,1,2,...,n1​​​​​,先进行一轮报数,编号为k=(m1)%n​​​​​的人被选中。构造一个映射f​​​​​将编号序列k,k+1,...,n1,0,1,2,...,k2​​​​​​映射为0,1,2,...,n2​​​​​,转换为n1的情形。很显然f是一个双射,并且有f1(x)=(x+k)%n​​​​​​​​​,从而有 (1)J(n)=(J(n1)+(m1)%n)%n 利用(1)​计算J(n)​的时间复杂度为O(N)​,而利用书中的公式计算的时间复杂度为O(logN)​​,在最开始有限步的处理确实影响到了利用递推式求解的复杂度。

利用线性空间求递推式的封闭形式

书中给出m=2时的封闭形式和二进制下的形式,这里不再赘述。

而书中提到了利用独立的特解求形如 (2)f(j)=aj,1j<df(dn+j)=cf(n)+bj,0j<d,n1 的递归式的封闭形式的方法,称为成套方法(repertoire method),并且提到有多少个独立的参数就需要多少个独立的特解,却并没有剖析其背后的原因。事实上,可以从线性空间的角度来看待这个问题。

给定c,d​,所有以(2)​形式定义的函数 f​构成的集合V不是空集。易验证V在函数的加法和函数与实数域R的纯量乘法下构成域R上的线性空间。

考虑实数域上2d+1​维向量构成的线性空间W,构造一个映射 σ:WV(a1,...,aj1,b0,...,bj1)f 其中f(2)定义,易验证σ是一个线性映射。

W​中的一组基α1=(1,0,...,0),α2=(0,1,...,0),...,α2d+1=(0,0,...,1)​,经σ​映射成f1,...,f2d+1​。

g(x)=i=12d+1kifi​为零函数,即g(x)=0,xN+​。

注意到 fi(j)={1,i=j0,ij ,i,j{1,2,...,2d+1}i{1,2,...,2d+1},g(i)=kifi(i)=ki=0​​,即f1,...,f2d+1线性无关。

又对任意按(2)定义的f,有f=a1f1+...+aj1fj1+b0fj+...+bj1f2d+1​​。

由此,f1,...,f2d+1​为V​的一组基,则σ​是一个双射,即σ​​是一个可逆线性映射。

f=σ1((a1,...,aj1,b0,...,bj1))=σ1(i=1j1aiαi+i=0j1biαi+j)=i=1j1aiσ1(αi)+i=0j1biσ1(αi+j)=i=1j1aifi+i=0j1bifi+j 因此,成套方法的本质即取W的一组基,解出V的一组基f1,...,f2d+1,从而得到f的封闭形式。