位换记号、排列测试与状态图:杂耍中的数学

2016 年 7 月 30 日至 8 月 7 日,第 39 届欧洲杂耍大会(European Juggling Convention)在荷兰的阿尔梅勒举行, 8 月 3 日凌晨的搏击之夜(Fight Night)自然再度成为了众人关注的焦点——它是杂耍斗(combat juggling)这项运动最大的赛事。在杂耍斗的圈子里,有两个响当当的大名你必须要知道:德国选手 Jochen Pfeiffer 目前世界排名第二,之前拿过 6 次搏击之夜的冠军;英国选手 Luke Burrage 目前世界排名第一,之前拿过 8 次搏击之夜的冠军。这一年的比赛中,两位老将均以完胜的成绩轻松进入 32 强,并在淘汰赛阶段过关斩将,最终成功在决赛场上相遇。最终,世界排名第二的 Jochen 以 5 比 4 的成绩击败了世界排名第一的 Luke ,夺得了又一个搏击之夜的冠军。

杂耍斗是一种两人对战类的体育运动。比赛规则非常简单。每局比赛开始时,两名选手各自抛耍 3 个杂耍棒。任何一方都可以故意上前干扰另一方(但只能针对对方手中的或者空中的杂耍棒,不能针对对方的手臂和身体)。谁站到最后,谁就赢得该局。先赢 5 局者获得比赛的胜利。

典型的一局比赛大致就像下面这样。这是 Jochen 和 Luke 的第 6 局比赛。

Read more…

用生命游戏来模拟生命游戏

    这是我前几天看到的一个视频。毫无疑问,它是我所见过的各种生命游戏构造中最神奇的一个:

      

    在 LifeWiki 中有一个词条详细介绍了这个构造:它叫做 OTCA metapixel ,是由 Brice Due 在 2005 至 2006 年间构造的。其中,每一个 metapixel 的大小为 2048 × 2048 ,周期为 35328 。

 
视频出处:http://www.youtube.com/watch?v=QtJ77qsLrpw
查看更多:http://www.reddit.com/r/math/comments/lutec/l_i_f_e_c_e_p_t_i_o_n_or_how_to_simulate_the/
如果你喜欢生命游戏,不要错过之前我们介绍过的史上最大的生命游戏构造—— Caterpillar 飞船

视频:Steiner问题的肥皂膜解法

    给定 n 个村庄的位置,要想把他们全部连通,最少需要修建多长的公路?这个问题被称为 Steiner 问题,是由数学家 Jakob Steiner 提出来的。注意,和最小生成树不同的是,公路是可以在中间汇合、分岔的。目前已经知道,Steiner 问题是 NP-hard 的,在规模很大的情况下,不能有效地得出最优解来。

     

    然而,大自然却是无敌的,它可以迅速秒杀这样的难题。由于肥皂膜总会试图让自己的表面积最小,利用肥皂膜实验,我们可以轻易获得 Steiner 问题的解。我在很多书上都看到过肥皂膜实验的方法,不过却从没见过真正的实验视频。今天我终于看到了这样的视频,把它搬进墙来,和大家分享。这个视频也很好地解释了一个普遍存在的误区:说肥皂膜实验一举解决了 NP 问题是不恰当的,因为这个实验只能找到极小值,并不能找到最小值,运气不好的话,实验结果会是失败的。

Read more…