暑假看了一些书,因此随手记录一下所学所想。
先从具体数学开始吧,由于博主只是个大一的本科生,数学基础并不扎实,欢迎指正错误。
本篇主要涉及具体数学第一章的内容,以及我对其中一些内容的拓展。
汉诺塔问题
开篇引入的就是很多人都熟知的问题,问题的介绍就不再赘述了。
设三根柱子分别为,目标是将个圆盘从柱子移动到柱子上,并记有个圆盘的汉诺塔问题的最优解为,先考虑构造一个可行的方案:
将前个小的圆盘移动至,再将最大的圆盘移动至,最后将个圆盘移动至。
这是一个可行的方案,因此对最优解,有。
书中随后证明了所有可行解的次数都大于等于,因此可以断言这是一个最优解。
由此受到启发,可以抽象出一个证明某个解是最优解的思路:先证明该解是可行解,再证明所有的可行解都不会比该解更优。
直线分割平面问题
这个问题是高中数学的经典问题,但还可以从不同角度去探讨这个问题的解。
记最优解为,先引入平面图欧拉公式:,其中分别为顶点数,边数,区域数。注意欧拉公式中的边数不是直线数。
第条直线可以至多形成个交点,考虑在平面上构造一个充分大的圆,使得所有的交点都在圆内,并与每条直线都有两个交点,共形成个交点。
将新形成的交点中在圆上相邻的点对用线段连接,形成条边,得到一个凸多边形。再删去圆和所有直线在凸多边形外的部分,此时这个凸多边形内部的区域数即。
从而,平面上的点数。原先的每条直线被个点分割为条边,则边数。
又由凸多边形外也是一个区域,代入平面图欧拉公式得,即。
下图是时的一个例子,其中绿色的点和红色的边分别为新形成的点和新形成的边。

约瑟夫问题
这个问题引申出来的内容就多一些了,并且我用线性空间对递推式的封闭形式进行了讨论。先规定为人数,数到第个人被选中,为幸存者的编号,为取模运算。
的情形
书中先讨论的是的情形,求解的方法是先选到只剩下个人,将问题转换成个人的情形。
由此受到启发,可以抽象出一些求递归式的问题的解法:先对问题进行有限步的处理,构造一个到更小的情形的单射,从而得到递归式。
例如在该问题中,先进行报数,剩下个人以 的方式进行重新编号,很显然这是一个单射,因此有逆映射 此时即可转换为人数为时的情形,幸存者编号为。则人数为时,整理一下即为书上的形式。
事实上,这个思路运用的非常广泛,并且通常来说最开始有限步的处理会影响到用递推式求解的复杂度。例如考虑为任意正整数的情况:
为方便讨论,将每个人的标号记成,先进行一轮报数,编号为的人被选中。构造一个映射将编号序列映射为,转换为的情形。很显然是一个双射,并且有,从而有 利用计算的时间复杂度为,而利用书中的公式计算的时间复杂度为,在最开始有限步的处理确实影响到了利用递推式求解的复杂度。
利用线性空间求递推式的封闭形式
书中给出时的封闭形式和二进制下的形式,这里不再赘述。
而书中提到了利用独立的特解求形如 的递归式的封闭形式的方法,称为成套方法(repertoire method),并且提到有多少个独立的参数就需要多少个独立的特解,却并没有剖析其背后的原因。事实上,可以从线性空间的角度来看待这个问题。
给定,所有以形式定义的函数 构成的集合不是空集。易验证在函数的加法和函数与实数域的纯量乘法下构成域上的线性空间。
考虑实数域上维向量构成的线性空间,构造一个映射 其中按定义,易验证是一个线性映射。
取中的一组基,经映射成。
设为零函数,即。
注意到 则,即线性无关。
又对任意按定义的,有。
由此,为的一组基,则是一个双射,即是一个可逆线性映射。
则 因此,成套方法的本质即取的一组基,解出的一组基,从而得到的封闭形式。