UyHiP 趣题:几个特殊的强正则图

下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 8 月的题目,稍有改动。

屋子里有若干个人,任意两个人都有恰好 1 个共同的朋友。这有可能吗?有可能。比方说,屋子里有 9 个人,其中 8 个人正好组成 4 对朋友,第 9 个人则和前面 8 个人都是朋友。容易验证,任意两个人都有恰好 1 个共同的朋友。我们可以用下面这个图表示此时这 9 个人之间的朋友关系,其中每个点代表一个人,如果两个人是朋友,就在他们之间连一条线。

除了上图展示的情况之外,我们还能构造出很多别的同样满足要求的情况。事实上,上述方案可以扩展到一切奇数个人的情况,比如下面这样:

Read more…

趣题:为什么偏偏是 6 格?

无穷多个相同大小的正方形格子排成一排,向左右两边无限地延伸。每个格子里都有 0 个、 1 个或多个原子。每一次,你可以对它们做下面两种操作之一:

  • 选择某个格子,保证该格子内至少含有 1 个原子。将该格子内的其中 1 个原子分裂为 2 个,从而使得该格子内的原子数量减 1 ,两边的邻格里的原子数量分别加 1。
  • 选择某个格子,保证两边的邻格里均至少含有 1 个原子。从两边的邻格里各取 1 个原子聚合起来,从而使得两边的邻格里的原子数量分别减 1 ,该格子内的原子数量加 1。

初始时,某个格子里有 1 个原子。现在,你需要在若干次操作之后,让它右移 6 格。也就是说,你需要用若干次操作把下面的第一个图变成第二个图(其中,数字 1 表示该格内的原子数为 1 )。继续阅读下去之前,你不妨自己先试一试。你可以在纸上画好格子,用硬币、大米、巧克力豆等物体代替原子。

Read more…

IMO2016 趣题:Geoff 的青蛙

2016 年 IMO 的第 6 题(也就是第二天比赛的第 3 题)非常有趣,这恐怕算得上是近十年来 IMO 的所有题目中最有趣的题目之一。平面上有 n ≥ 2 条线段,每两条线段都有一个交点,并且任意三条线段都不交于同一点。 Geoff 打算在每条线段的其中一个端点处放置一只青蛙,并让每只青蛙都朝向它所在线段的另一个端点。然后, Geoff 将会拍 n – 1 次手。每次拍手时,每只青蛙都立即向前跳到它所在线段的下一个交点处(青蛙们在跳跃过程中始终不会改变方向)。 Geoff 希望巧妙地安排初始时放置青蛙的方法,使得在整个过程中,任意两只青蛙都不会同时到达某个相同的交点。这个题目有两个小问。

  1. 证明:当 n 为奇数时, Geoff 一定有办法实现他的要求。
  2. 证明:当 n 为偶数时, Geoff 永远无法实现他的要求。

Read more…

捡石子游戏、 Wythoff 数表和一切的 Fibonacci 数列

让我们来玩一个游戏。把某个国际象棋棋子放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。如果把棋子放在如图所示的位置,那么你愿意先走还是后走?显然,答案与我们放的是什么棋子有关。

这个游戏对于兵来说是没有意义的。在如图所示的地方放马或者放象,不管怎样都无法把它移动到棋盘的最左下角,所以我们也就不分析了。因此,我们只需要研究王、后、车三种情况。

Read more…

如果把 3 · n + 1 问题改为 3x · n + 1 问题

Collatz 猜想也叫做 3 · n + 1 问题。这可能是数学中最为世人所知的未解之谜。它是如此初等,连小学生都能听懂它的内容;但解决它却如此之难,以至于 Paul Erdős 曾说:“或许现在的数学还没准备好去解决这样的问题。”这究竟是一个什么样的问题呢?让我们来看一下 Collatz 猜想的叙述:

任意取一个正整数 n 。如果 n 是奇数,则把 n 变为 3 · n + 1 ;如果 n 是偶数,则把 n 变为 n/2 。不断重复操作,则最终一定会得到 1 。

举个例子,如果 n = 26 ,那么经过下面 10 步之后,它最终变为了 1 :

26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Collatz 猜想说的就是,这个规律对于所有正整数 n 均是如此。这个问题看起来是如此简单,以至于无数的数学家都掉进了这个坑里。光从这个问题的众多别名,便能看出这个问题害人不浅: Collatz 猜想又叫做 Ulam 猜想、 Kakutani 问题、 Thwaites 猜想、 Hasse 算法、 Syracuse 问题……研究这个问题的人很多,解决这个问题的人却一个没有。后来,人们干脆把它叫做 3 · n + 1 问题,让哪个数学家也不沾光。

这个问题有多难呢?我们可以从下面的这个例子中略见一斑。虽然从 26 出发只消 10 步就能变成 1 ,但若换一个数,比如 27 ,情况就大不一样了:

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可见,当 n 的值不同时,从 n 变到 1 的路子是很没规律的。

有趣的是,如果我们把 Collatz 猜想中的乘以 3 改为乘以任意一个 3x (其中 x 的值可由你自由选择),那么 Collatz 猜想就是正确的了。下面我们就来证明这一点。

Read more…