寻找相邻两项之比不趋于 1.618 的广义 Fibonacci 数列

大家或许知道 Fibonacci 数列 1, 1, 2, 3, 5, 8, … 有一个非常漂亮的性质:数列中的相邻两项之比将会越来越接近黄金比例 (1 + √5) / 2 ≈ 1.618 。事实上,如果我们用 F(n) 来表示第 n 个 Fibonacci 数的话,那么当 n → ∞ 时,我们有 F(n + 1) / F(n) → (1 + √5) / 2 。

不过,可能有人并不知道,如果把 Fibonacci 数列的前两项换成两个其他的正整数(但保持 Fibonacci 数列的递推关系不变),由此所得的广义 Fibonacci 数列当中,相邻两项之比仍然会趋近于 (1 + √5) / 2 。比方说,如果数列的前两项为 7, 2 ,那么整个数列的前 15 项以及相邻两项之比的情况如下:

7, 2, 9, 11, 20, 31, 51, 82, 133, 215, 348, 563, 911, 1474, 2385, …
 
2 / 7 = 0.28571429…
9 / 2 = 4.5
11 / 9 = 1.2222222…
20 / 11 = 1.8181818…
31 / 20 = 1.55
51 / 31 = 1.6451613…
82 / 51 = 1.6078431…
133 / 82 = 1.6219512…
215 / 133 = 1.6165414…
348 / 215 = 1.6186047…
563 / 348 = 1.6178161…
911 / 563 = 1.6181172…
1474 / 911 = 1.6180022…
2385 / 1474 = 1.6180461…

更神奇的是,即使最前面这两个数当中有一个负数或者都是负数,相邻两项之比的趋势依旧不变!举个例子,若数列的开头两项是 20 和 -13 ,则有:

20, -13, 7, -6, 1, -5, -4, -9, -13, -22, -35, -57, -92, -149, -241, …
 
(-13) / 20 = -0.65
7 / (-13) = -0.53846154
(-6) / 7 = -0.85714286
1 / (-6) = -0.16666667
(-5) / 1 = -5
(-4) / (-5) = 0.8
(-9) / (-4) = 2.25
(-13) / (-9) = 1.4444444
(-22) / (-13) = 1.6923077
(-35) / (-22) = 1.5909091
(-57) / (-35) = 1.6285714
(-92) / (-57) = 1.6140351
(-149) / (-92) = 1.6195652
(-241) / (-149) = 1.6174497

事实上,不管数列的开头两项是多么奇怪的两个实数(比如 -7/2, √2, … 或者 π/10, -√e, … 等等),按照 Fibonacci 式的递推关系算出后面各项,相邻两项之比几乎总会趋于 (1 + √5) / 2 !注意,刚才我们使用了“几乎”一词,因为这个结论其实并不总是成立。今天的题目就是:请你找出至少一个反例。也就是说,你需要找出至少一个由递推关系 a(i) = a(i – 1) + a(i – 2) 生成的数列,使得当 n 趋于无穷大时 a(n + 1) / a(n) 并不趋于 (1 + √5) / 2 。

对了, 0, 0, 0, 0, 0, … 这种情况自然不算。

Read more…

线性代数的妙用:怎样在Windows画图软件中实现28度旋转?

    在早期的小型图像编辑软件中,考虑到时间空间的限制,再加上算法本身的难度,很多看似非常简单的功能都无法实现。比如说,很多图像编辑软件只允许用户把所选的内容旋转 90 度、 180 度或者 270 度,不支持任意度数的旋转。毕竟,如果我们只是旋转 90 度的整数倍,那么所有像素仅仅是在做某些有规律的轮换,这甚至不需要额外的内存空间就能完成。但是,如果旋转别的度数,那么在采样和反锯齿等方面都将会有不小的挑战。

    不过, Windows 自带的画图软件聪明地用 skew 功能(中文版翻译成“扭曲”)部分地填补了无法自由变形的缺陷。随便选中图中的一块区域,再在菜单栏上选择“图像”→“拉伸/扭曲”,然后在“水平扭曲”那儿填写一个 -89 到 89 之间的整数(表示一个角度值),再按一下确定,于是整个图形就会像下图所示的那样被拉斜,其中 θ 就是你刚才填的度数。如果你填入的 θ 是负数值,则倾斜的方向会与下图方向相反。类似地,“垂直扭曲”功能会在竖直方向上对图形进行拉扯,如果角度值为正数,则整个图形会变得左低右高,如果角度值为负数,则整个图形会变得左高右低。

      

    不过,这玩意儿对于我们来说似乎完全没用。估计 99% 的人在使用画图软件的时候就从来没用过这个功能吧。如果真是这样,那么今天的问题恐怕将会是大家最近一段时间见过的最有趣的问题了:想办法利用 Windows 画图中的扭曲功能(近似地)实现 28 度旋转。

Read more…

趣题:选出最多的大小为奇数的子集,使得两两的交集大小都是偶数

    在集合 {1, 2, …, n} 中选出尽可能多的子集,使得每个子集所含的元素个数都是奇数,但是任意两个子集的交集都含有偶数个元素。那么,我们最多能够选出多少个这样的子集来?

    容易看出,我们至少可以选出 n 个子集。例如,当 n = 4 时, {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗?简单地尝试后,你会觉得似乎不行。不过,这却并不是显然的,因为存在一些不那么平凡的方案,也能让子集的数量达到 n ,例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4} 这 4 个子集也是满足要求的。看来,证明最多只能选出 n 个子集,好像并不那么容易。

Read more…

UyHiP趣题:按照盒子的三边长之和来计费有没有漏洞?

    今天的趣题来自 UyHiP 今年十月的趣题

    许多快递公司都依据物件的长、宽、高三边之和来收费,一些航空公司也要求托运行李的三边长相加不能超过某个限制。那么是否有人想过,有没有可能把一个三边之和较大的盒子装进一个三边之和较小的盒子里,从而骗取更低的费用呢?有人会说,恐怕不行吧,长宽高之和更大的盒子体积不也应该更大一些吗?不见得。比方说,盒子 A 的长宽高分别是 10 、 10 、 10 ,盒子 B 的长宽高分别是 9 、 9 、 12.1 。盒子 B 的三边长之和显然比盒子 A 要大,但体积只有 980.1 ,比前者要小近 20 个单位。那么,为什么就不能把盒子 B 沿斜线方向塞进盒子 A 呢?有人会敏锐地发现,在上面的例子中,盒子 A 的体对角线长为 17.3205 ,但盒子B的对角线长度达到 17.5616 ,显然无法完全放进盒子 A 里。不过且慢,我也能举出这样的例子,三边和更大的盒子其体积和对角线都比小的盒子的要小。盒子 A 的长宽高分别为 10 、 10 、 20 ,盒子 B 的长宽高分别为 7.1 、 16.5 、 16.5 。盒子 B 的长宽高之和比盒子 A 大,体积为 1932.98 ,对角线长度比前者小大约 0.1 。看来,为了解决这个问题,我们还需要从一些更巧妙的方面入手。

Read more…