趣题：竞技场里的狮子能否保证抓住最高速度相同的小明？

/ 60 条评论

小明和狮子同被关在一个半径为 10 米的竞技场里，狮子位于竞技场的圆心处，小明则在距离圆心 1 米的地方。两者的最大运动速度都是每秒 1 米。狮子有没有什么必胜策略，使得不管小明怎么跑，它总能在有限的时间里抓住小明？

根据 MathWorld 相关词条的描述，这个问题是由 R. Rado 在 1925 年时提出的。一个经典的“答案”是，狮子只需要始终保持自己与小明在圆盘的同一半径上即可。直觉上看，由于狮子总是处在“内圈”上，因而不管小明跑到了哪里，狮子总能轻松地与小明继续保持在同一半径上；并且，狮子总有足够的余力向小明靠近，严格减小它与小明之间的距离，除非小明是沿着半径方向径直向外跑。由于竞技场的大小是有限的，小明不可能无限地向外跑，因而狮子最终总会追上小明。但是，后来人们发现，这个解法其实是错误的，原因很简单：能不断靠近小明，不一定就能在有限的时间里抓住小明，正如 1/2 + 1/4 + 1/8 + 1/16 + … 永远不会超过 1 一样。最终， A. S. Besicovitch 为小明构造出了一个极其巧妙的策略，使得狮子无论如何都抓不到小明，从而完美地解决了这个问题。不过， MathWorld 的词条里并没有提到这个解法。你能想到这个解法吗？

Read more…

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

/ 33 条评论

大家或许知道 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…

用三段 140 字符以内的代码生成一张 1024×1024 的图片

/ 75 条评论

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛，参赛者需要用三条推这么长的代码来生成一张图片。具体地说，参赛者需要用 C++ 语言编写 RD 、 GR 、 BL 三个函数，每个函数都不能超过 140 个字符。每个函数都会接到 i 和 j 两个整型参数（0 ≤ i, j ≤ 1023），然后需要返回一个 0 到 255 之间的整数，表示位于 (i, j) 的像素点的颜色值。举个例子，如果 RD(0, 0) 和 GR(0, 0) 返回的都是 0 ，但 BL(0, 0) 返回的是 255 ，那么图像的最左上角那个像素就是蓝色。参赛者编写的代码会被插进下面这段程序当中（我做了一些细微的改动），最终会生成一个大小为 1024×1024 的图片。

// NOTE: compile with g++ filename.cpp -std=c++11
 
#include <iostream>
#include <cmath>
#include <cstdlib>
#define DIM 1024
#define DM1 (DIM-1)
#define _sq(x) ((x)*(x)) // square
#define _cb(x) abs((x)*(x)*(x)) // absolute value of cube
#define _cr(x) (unsigned char)(pow((x),1.0/3.0)) // cube root
 
unsigned char GR(int,int);
unsigned char BL(int,int);
 
unsigned char RD(int i,int j){
   // YOUR CODE HERE
}
unsigned char GR(int i,int j){
   // YOUR CODE HERE
}
unsigned char BL(int i,int j){
   // YOUR CODE HERE
}
 
void pixel_write(int,int);
FILE *fp;
int main(){
    fp = fopen("MathPic.ppm","wb");
    fprintf(fp, "P6\n%d %d\n255\n", DIM, DIM);
    for(int j=0;j<DIM;j++)
        for(int i=0;i<DIM;i++)
            pixel_write(i,j);
    fclose(fp);
    return 0;
}
void pixel_write(int i, int j){
    static unsigned char color[3];
    color[0] = RD(i,j)&255;
    color[1] = GR(i,j)&255;
    color[2] = BL(i,j)&255;
    fwrite(color, 1, 3, fp);
}

Read more…

趣题：寻找四个共圆的点

/ 14 条评论

5 张矩形的纸片和 6 张圆形的纸片散落在桌面上，如下图所示（其中一张矩形纸片被撕掉了一个角）。考虑所有露在外面的矩形顶点以及纸张边缘处的交点，你能否从中找出四个保证共圆的点？很简单，右下角那个绿色矩形的四个顶点就满足要求，因为矩形的四个顶点显然是共圆的。其实，在这个图里，还有另外三组满足要求的点，你能找到吗？

Read more…

Penney 的游戏：正所谓后发制人，先发制于人

/ 56 条评论

让我们来玩一个游戏。连续抛掷硬币，直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者，那么我获胜，你需要给我 1 元钱；如果是后者，那么你获胜，我会给你 1 元钱。你愿意跟我玩这样的游戏吗？换句话说，这个游戏是公平的吗？

乍看上去，你似乎没有什么不同意这种玩法的理由，毕竟“正反反”和“反反正”的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果，上述两种各占其中的 1/8 。况且，序列“正反反”和“反反正”看上去又是如此对称，获胜概率怎么看怎么一样。

实际情况究竟如何呢？实际情况是，这个游戏并不是公平的——我的获胜概率是你的 3 倍！虽然“正反反”和“反反正”在一串随机硬币正反序列中出现的频率理论上是相同的，但别忘了这两个序列之间有一个竞争的关系，它们要比赛看谁先出现。一旦抛掷硬币产生出了其中一种序列，游戏即宣告结束。这样一来，你就会处于一个非常窘迫的位置：不管什么时候，只要掷出了一个正面，如果你还没赢的话，你就赢不了了——在出现“反反正”之前，我的“正反反”必然会先出现。

事实上，整个游戏的前两次硬币抛掷结果就已经决定了两人最终的命运。只要前两次抛掷结果是“正正”、“正反”、“反正”中的一个，我都必胜无疑，你完全没有翻身的机会；只有前两次掷出的是“反反”的结果，你才会赢得游戏的胜利。因此，我们两人的获胜概率是 3:1 ，我的优势绝不止是一点。

你或许想问，如果已知我的硬币序列是“正反反”，那么你应该选择一个怎样的硬币序列，就能保证获胜概率超过我呢？研究表明，你可以选择“正正反”，这样一来，我们两人的获胜概率将会变为 1:2 ，换句话说你将会有 2/3 的概率获胜。 Using your Head is Permitted 趣题站 2014 年 5 月的趣题对此进行了更深一步的探究。

A 、 B 两人打算玩这么一个游戏。首先， A 选择一个长度为 n 的正反序列，然后 B 再选择另一个长度为 n 的正反序列。之后，不断抛掷硬币，哪名玩家所选的正反序列最先出现，哪名玩家就获胜。我们的问题是，假如两名玩家都采取最优策略的话，对于哪些 n ，游戏对玩家 A 更有利一些（换句话说，玩家 A 拥有超过 50% 的胜率），对于哪些 n ，游戏对玩家 B 更有利一些（换句话说，玩家 B 拥有超过 50% 的胜率）。今后，为了方便起见，我们用数字 1 代表“正面”，用数字 0 代表“反面”。

Read more…