2022年5月

有趣的搬空银行游戏:一个巧妙的展示不变量思想的好案例

 

本文编译自Alex Bellos于2019年10月7日发表于英国《卫报》网站的文章

编译:Math001

 

 

关注 哆嗒数学网 每天获得更多数学趣文

 

今天,我们来玩一个游戏。玩这个游戏需要一个无限行无限列的表格,以及三枚硬币。三枚硬币放在表格的左上角。就像下面图中表示的那样。


游戏只有一种操作。你可以拿掉任何一枚硬币,但是需要马上在这枚硬币的右边和下边的格子里补上两枚硬币。比如,如果你拿掉了上方第二个硬币,你需要按下图中的方式,马上补上两枚。


再补充一个规则吧。只有一枚硬币右边和下边的格子全都是空格子的时候,你可以拿掉硬币,并补上两枚。哪怕有一个格子不是空的,这枚硬币都不能拿掉。你就只能拿别的按规则可以拿掉的硬币。

 

我们把左上方2×2的格子圈出来,把它叫做银行,如下图红框部分。


你会直观地感受到,整个游戏过程中,硬币逐渐增多,总体是向右下方流动的。

 

我们的问题是,你有什么策略,可以让银行中的硬币全部流出银行。就是说左上2×2的格子中,不再有任何一枚硬币。或者,你会觉得总会有硬币留在银行中,但你需要清晰精准地说明这一点。

 

这个问题其实有点难的, 你可以做做实验,多想一会儿。待会儿我们解谜的时候,你会感受到数学的神奇。(在一串长空格后,我们开始解密)

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

解密开始:

 

在具体说明这个问题之前,你可能做了很多次实验了。是不是开始怀疑,如果严格按照游戏规则,是不可能把银行清空的。

 

对的!如果你有这个想法,那恭喜你,这就是这个问题的正确答案。那么,剩下的事情就是严谨地证明你的猜想。

 

证明的方法也许不唯一,这里讲述一个本人认为非常巧妙的一个办法。

 

我们的证明过程会去设计一个不变量,利用这个不变量来说明按照游戏规则,我们无法搬空银行。不变量是一个数学概念,简单的说,它表达的是无论局面如何变化,那些在万变之中永远不变的东西。不变量的思想几乎贯穿数学这门学科的所有分支,甚至有观点认为,数学本身就是研究各种不变量的学科。

 

为了说明问题,我们做一些准备工作。我们用如下的方式给每个格子标记一个数。

 

 

标记的规则是这样的:

 

第一排,从左边第一个开始分别标记1,1/2,1/4,...,总之右边的那个数是之前数的一半。

 

第二排,从左边第一个开始分别标记1/2,1/4,1/8,...,就是起始的数是上一排的一半,但总是保证右边的那个数是之前数的一半。

 

第三排,继续1/4,1/8,1/16,...

 

以此类推……

 

表格标记完后,你会发现,你任意取一个格子和它右边以及下边相邻格子标记的数都是这个格子的一半。

 

准备工作完毕,我们来设计我们的不变量了。

 

首先,我们来看看,所有格子的数加起来会等于多少。这里有无穷个数求和,我们的策略是先求出每一行的和,再把这些和加起来。

 

第一行就是,1 + 1/2 + 1/4 + ... ,结果是2 ;

 

第二行,1/2 + 1/4 + 1/8 + ... , 结果是 1 ;

 

第三行,1/4 + 1/8 + 1/16... , 结果是 1/2 ;

 

……

 

最后再来 2 + 1 + 1/2 + ... , 加起来等于4 。

 

就是说所有数字加起来的和是4。

 

我们再来看看规则。每次操作,我们都会把原本的硬币去掉,并在右侧和下侧添加上两枚新的硬币。虽然,表格中的硬币会增加一个,但是替换上的硬币覆盖格子中标记数的总和之前那枚硬币覆盖标记数是相等的。这意味着,无论多少此操作,所有硬币覆盖格子中标记数的总和不变。

 

那么,按照初始的三个硬币摆放的位置。三枚硬币覆盖的标记数之和是1 + 1/2 + 1/2 = 2。银行中,标记数之和是2 + 1/4 = 9 . 要把所有硬币在银行内清空,意味着银行内没有硬币,所有硬币都在银行外。根据之前的分析,就是说要达到一种状态,银行外硬币覆盖的标记数之和保持初始的2不变。但是,银行外标记数之和为 4 - 9/4 = 7/4 ,比2小。

 

所以不能清空银行。 

 

另外,实际上通过之前的讨论,你可以证明:哪怕把硬币完全清理出初始的三个位置,都是不可能的。因为,剩余的标记数之和是2,需要无限个硬币才能达到。而有限次操作,最多生成有限枚货币。

 

 

关注 哆嗒数学网 每天获得更多数学趣文

苦行说:我的数学专业学习之旅

作者,MathRoc,哆嗒数学网群友

 

关注 哆嗒数学网 每天获得更多数学趣文

 

 

求学是苦行之旅,需要去征服一座又一座崇山峻岭。幸运的是我征服了第一段矮坡,在此我想分享自己的学习历程。“学说”一题极为宏大,学浅才疏使我力有不逮,故此写下这篇不甚成熟的“苦行说”,望大家多指点。

 

诗人林珊在《山行》中写道:“我还是去得晚了一些‖满山的黄叶已经落尽了‖只有风,从山顶袭来‖枯草里的星辰是什么时候撒下的‖瓦楞上的残雪是什么时候落下的‖香山寺的钟声也无法给予我‖想要的答案”。或许这正是我本科四年的学习生活的真实写照。

 

当我初踏入大学校园时,草平雨新路无尘,一切都是可爱的模样。但入学后我发现自己与数学系的学生之间有很大的差距。他们或是在高中便已学完大一、大二的内容,或是在竞赛中取得了很好的成绩,少数则在初中时便学习了大学内容,一言以蔽之,有深厚的数学基础和非凡的学习能力。当时的我想迅速追赶,但竭尽所能也难以望其项背,从此便进入了漫长的迷茫期。

 

起初未接触数学系的同学,自然不知道需要在何阶段读何书,我便试图同时看多门课的入门书。尽管举步维艰,我仍在坚持,去教室的路上、吃饭时、睡前,无时不在看书。我仍以高中形成的观念来看待“怎样才算学会了”——题目可以不费力地独立解决,也曾四本书并进,正文能懂但对题目畏葸不,就此断定是因太笨没学会。于是换书来啃,一个月内如此往续,应有10本以上,比如数学分析、高等代数、解析几何、概率论、组合数学、图论、近世代数、实分析。现在看来,所选的书是最难的那一批,所做的皆为无用功。

 

经此一役,我向很厉害的学弟请教,他指出我应该先读大一内容——数分、高代,并分别推荐了史济怀、李炯生(号称亚洲最难)的教材。诚然,对已有基础或学习能力强的人来说,它们是非常不错的入门教材。但对当时基千疮百孔的我而言,这无疑是一剂虎狼猛药。

 

我再次被习题拦在了门外,但也开始主动寻找“没学明白”的症结所在。我发现,对教材难度预设太高,我应该选择更合适的书。自此,踏上了寻找适合自己的书籍的漫长历程。

 

迷茫时期持续了近两年,为此付出的代价也是不小的。此间我为转数学系辗转奔波过,比如咨询教务处老师、给校长信箱写信以期有一次转专业考核的机会。转专业政策是只看原专业的排名,或有省级以上的竞赛证书等的证明,因此所有努力是徒劳的。在朋友的劝慰下我走出了这段晦暗的时期,继续踏上那条前路似无光的寻书之旅。奇迹的是,我此后竟未被生活击倒过。

 

在大二、大三时专业基础课愈来愈多,留给自学的时间也日渐递减。我选择将更多的精力投入到自学中,自然而然挂了好几科。然而,与此同时我走出了迷茫期和寻书之旅,并确定了当时喜欢的方向——概率论。我用了几个月的时间初学了一些书籍,如王梓坤《概率论基础及其应用》、Durrett的概率论、JunShao的数理统计和Ross的随机过程。

 

后来在阅读了潘承洞先生的《阶的估计基础》后,我发现更喜欢的是一直在被偏废的渐近分析。我是足够幸运的,因为我能比一些朋友更早知道自己的兴趣爱好;我也应该省思,因为这一过程耗费了本应绽放的青春。

 

大三下、大四上开始为考研准备,但择校成为了最大的问题。我的兴趣尚算广泛,准确来说很偏(渐近分析、特殊函数、解析数论),含解析数论方向的学校大多考研难度大,而含前两者的学校几乎没有,所以备选的学校很少。在一番衡量后我选择解析数论方向,正当满心欢喜地备考时,专业课来了。在大一到大三上,我们都在学习专业基础课,大三下开始才学习真正的专业课。这对我来说,无疑是极大的考验。

 

当我全部通过以后,迷茫期的代价姗姗来迟——机械制图与机械设计是对我而言最难的两门课,它们需要重修,此时距考研初试只有一月余。经过一番思想斗争,我决定放弃考研,并竭我所能通过它们,最终如愿以偿。

 

如果用一个词概括大学生活,我选择“俯拾仰”,即一举一动都有收获。在社团活动中,我负责心理协会的公众号运营与青年报的评论撰写,这些活动让我明白了什么是“因热爱而坚持”;在网络平台上,我学会了写博客和运营自己的数学公众号,我从中体会到了什么是“因坚持而热爱”。我的大学生活是云层下的光,指引着我走向成熟,我将永志不忘这四年时光。

 

等毕业后,也就是去年,我全身心地投入考研,现在已被志愿高校拟录取。不太恰当地说,“细思皆幸矣,下此便翛然”。当然,不取“老”之意。

 

学习历程皆陈于此,接下来我想聊聊网络数学竞赛。

 

第一次接触它是在参加Xionger网络数学竞赛(下称:熊赛),值得一提的是熊赛自其诞生就广受关注与好评,但唯一的败笔是近几年的分数和最终排名未能公布。我参加的是第二届,当时高手如云,题目值得玩味,而后一届题目数量翻倍,加之熊哥平时很忙、供题人集不全,赛后题目便改不完了。我只参加了一届赛,此后没有参加网络竞赛与各种线下竞赛。但我举办过两届团子杯网络数学竞赛,也为熊赛和八一杯数学竞赛供过题。当然,Binger杯数学竞赛也没落下,但是举办者处于半退网状态,第二届也便没举办起来。

 

在我看来,网络数学竞赛应是一场盛筵,智者得以提升,慧者得以洞悉,而平庸者如我得以开阔眼界、培养文献检索能力以及与更多人交流。

 

谈谈我的经验吧!起初我在各种习题书中寻找偏难怪的题目,但转念一想,网络竞赛不是要选拔人才,也不是真正的竞赛,而是出题人与答题者互相学习交流的一次绝佳的机会。于是我转向寻找趣味性、普适性的问题。为熊赛和八一杯提供的是难题,自然无人答出,此后我多次反思,决定降低难度、仍保持普适趣味性但架构纸老虎——能用简单知识解决的难题,这一次又给八一杯献上两题,后来发现每题都有人给出正确解答,甚至给出了新解法。

 

我在大二时开始运营数学公众号。起初用AxMath来编写公式再生成图片上传平台,但这样会使排版很乱。接下来我学用LaTeX,将编译出的文件截图再上传,这一阶段收获颇丰。后来我发现之前的文章美观与简陋并存,一狠心便注销了公众号,然后重新注册,用mdnice网页的粘贴功能开始了美观之旅。

 

我编写过《阶的估计基础》习题解答,此过程可谓“大胆假设,小心求证”。想我所想,但也向诸多朋友、学长请教,以保证解答的严谨性。

 

网络上数学的小圈子里常称彼此为“数学人”。那么,究竟怎样才算一个合格的“数学人”呢?在我看来,这与“数学”和“人”密不可分。我们不仅仅需要“数学品位”和“数学钻研”,更需要向人请教和适当的人际交往。

 

 

请允许我讲一些关于学习的粗浅的见解:

 

  1. 不忘初心 或许忘掉了不少曾学过的理化生知识,但我时刻不敢忘初心。我是一个愚笨的人,没有数学天赋,对数学是喜欢但谈不上热爱。且听我言,一位好朋友的室友本科在北大医学系读书,后来拿到了医、数双学位,目前是基础数学的在读硕士。与他相比,我面前的高山只算缓坡。每个人的路应由自己走,学习也应是自己的事。论他人是如何渡过困厄的,就个人而言,走出迷茫和困厄的最好的办法便是不忘初心。

    <p style="margin: 0px; padding: 0px; clear: both; min-height: 1em;">&nbsp;</p>
    </li>
    

2. 保持热情 我也曾懈怠,但这只会使我胸无点墨。以我为例,我的热情之火被屡次碰壁的经历所磨灭,由是学习效率低下,只能用比别人更多的时间来弥补学习上的亏空,这也让曾经的我信心大减。即使面临窘境,也请务必保持热情,请相信我的诗中写的“我的肩上落有闪着青光的萤火,它能带来满天的星光,映衬着天上的云雨声、海上的风涛声”。

 

3. 广交诤友 我很幸运地交到了一群诤友,但为此也很惭愧,因为他们给予了太多的帮助而我帮不上他们。在我失落时,他们会安慰我;在我不知道如何进一步学习时,他们给予中肯而详尽的建议。人生之途漫漫,一定孤独,但有了诤友,未来不会再黯淡,至少它能开出苦涩的花,不是吗?

 

4. 莫羡他人 准确地说,不要只羡慕他人的成功,不要总攀比。这些年我见到了很多不良的学习风气,比如“膜”“卖弱”,意即不论别人如何都去膜拜、不论如何都说自己水平很低;再如“如何评价”,意即如下的现象:常问如何评价某人才大二就这么厉害,每年都问如何评价期末考试题目这么难等等。这些既不利于学习,也不利于生活。学习是一条崎岖蜿蜒的山路,你既需要攀登,也需要抵制崖间的花香诱惑。

 

苦行之旅,应旷达随性。席慕蓉在《诗的旷野》里写道:“文字并非全部‖生活也不是 我们其实‖不需要逼迫自己‖去证明这一生的意义和价值‖在诗的旷野里‖不求依附 不去投靠‖如一匹离群的野马独自行走‖其实 也并非一无所有‖有游荡的云 有玩耍的风‖有潺潺而过的溪流‖诗 就是来自旷野的呼唤‖是生命摆脱了一切束缚之后的‖自由和圆满”。

 

苦行之旅,应常省思。我现在能独立地发现学习中暴露出的一些问题,比如自卑、易懈怠。我为自己开了一剂良方“悟学知心,斩棘披荆”,要不断地了解自己,要有迎难而上的决心。当我上下求索时,收获或许很少但成长很快,我有勇气也有信心

 

 

关注 哆嗒数学网 每天获得更多数学趣文