木头数学

约翰逊先生在户外有个炙肉架,正好能容纳2片炙肉.他的妻子和女儿贝特西都饥肠辘辘,急不可耐.问怎样才能在最短时间内炙完三片肉.

约翰逊先生:”瞧,炙一片肉的两面需要20分钟,因为每一面需要10分钟.我可以同时炙两片,所以花20分钟就可以炙完两片.再花20分钟炙第三片,全部炙完需要40分钟.”

贝特西:”你可以更快些,爸爸.我刚算出你可以节省10分钟.”

啊哈!贝特西小姐想出了什么妙主意?

为了说明贝特西的解法,设肉片为A,B,C.每片肉的两面记为1,2.第一个10分钟炙烤A1,和B1.把B肉片先放到一边.再花10分钟炙烤A2和C1.此时肉片A可以炙完.再花10分钟炙烤B2和C2,仅花30分钟就炙完了三片肉,对吗?

这个简单的组合问题,属于现代数学中称之为运筹学的分枝.这门学科奇妙地向我们揭示了一个事实:如果有一系列操作,并希望再最短时间内完成,统筹安排这些操作的最佳方法并非马上就能一眼看出.初看是最佳的方法,实际上大有改进的余地.在上述问题中,关键在于炙完肉片的第一面后并不一定马上去炙其反面.

提出诸如此类的简单问题,可以采用多种方式.例如,你可以改变炙肉架所能容纳肉片的数目,或改变待炙肉片的数目,或两者都加以改变.另一种生成问题的方式是考虑物体不止有两个面,并且需要以某种方式把所有的面都予以”完成”.例如,某人接到一个任务,把 n 个立方体的每一面都涂抹上红色油漆,但每个步骤只能够做到把 k 个立方体的顶面涂色.

今天,运筹学用于解决事物处理,工业,军事战略等等许多领域的实际问题.即使是像炙肉片这样简单的问题也是有意义的.为了说明这一点,请考虑下列一些变相问题:

琼斯先生和夫人有三件家务事要办.

1.用真空吸尘器清洁一层楼.只有一个真空吸尘器,需要时间30分钟.

2.用割草机修整草地.只用一台割草机,需要时间30分钟.

3.喂婴儿入睡,需要时间30分钟.

他们应该怎样安排这些家务,以求在最短时间内全部完成呢?你看出这个问题与炙肉片问题是同构的吗?假设琼斯先生和夫人同时进行操作,一般人开始往往以为做完这些家务需要60分钟.但是如果一件家务(譬如说用真空吸尘器做清洁工作)分为两个阶段,第二阶段延后进行(像炙肉片问题那样),那么三件家务可以在 3/4的时间内即45分钟内完成.

下面有一个关于准备三片热涂奶油的烤面包问题.这个运筹学问题比较困难.烤面包架是老式的,两边各有一扇翼门,可以同时容纳两片面包,但是只能单面烘烤.如果要烤双面,需要打开翼门,把面包片翻过身来.

将一片面包放入烤面包架需要时间3秒钟,取出来也需要3秒钟,将面包片在烤面包架内翻身又需要3秒钟.这些都需要双手操作,即不能同时进行放,取或把两片面包同时翻身,也不能在放入一片面包,将其翻身或取出的同时把另一片涂抹上奶油.单面烘烤一片面包需要30秒钟,把一片面包涂抹上奶油需要12秒钟.

每片面包仅限于单面涂抹上奶油.未经烘烤不得事先在任何一面涂抹上奶油.单面已经烤过的和涂抹上奶油的面包片可以重新放入烤面包加内继续烘烤其另一面.如果烤面包架一开始就是热的,试问双面烘烤三片面包丙涂抹上奶油最少需要多少时间?

在两分钟内完成上述工作并不太难.然而,如果你领悟到:一片面包在单面烘烤尚未结束的情况下,也可以取出,以后再放回烤面包架内继续烘烤这一面,那么全部烘烤时间就可以缩减至111秒钟.使你想到这一点,统筹安排这些操作使效率达到最高也远非是一件易事.在这方面,尚有无数比此更为复杂的实际问题,需要借助于与计算机和现代图论有关的高度复杂的数学手段.

今有1000枚硬币，其中可能有0，1或2枚假币。已知假币的重量彼此相同，但与真币不同。试问，能否使用一架没有砝码的天平称3次，即确定出来其中有无假币，以及他们与真币究竟谁轻谁重（不需确定出假币的个数）？

解 将硬币分为两组，每组500个，并比较他们的重量（作第一次称量）。可能有两种情况：

情况A：其中一端较重，不妨设为左端。这表明有假币存在（他们可能有1个或2个），且所有假币都位于同一端（如果他们在两端各有1个，则天平仍应平衡）.此时再将重的一端的硬币分为两组，每组250个，并比较他们的质量（作第二次称量）。如果其中一端较重，则可知假币就在这500个硬币之中，且较真币为重，这次已不需再作第三次称量。如果两端平衡，则或者假币在另外500个硬币之中（且知较真币为轻），或者他们被分在两端，在两端250个硬币中各有 1个。为了弄清楚究竟是哪一种情况，就再把其中一组250个硬币平均分为两组，并比较他们的质量（作第三次称量）。如果两端平衡，则为前一种情况，否则即为后一种情况。

情况B：在第一次称量时，天平两端平衡，这意味着假币可能有0个或2个（两端各有1个）。再将其中一组分为两组，每组250个硬币（作第二次称量）。如果天平再度平衡，则表明在天平上共有偶数个假币，但事实上此时假币的数目不超过1个，因此表明根本没有假币。如果有一端较重，则表明假币共有两个，且其中1个就在天平的一端中。再将较重的一端分为两半，作第三次称量，即已容易再度假币究竟在那一个。

有一只聪明的蟑螂决定要去寻找真理，它的视野不超过1cm。真理位于一个同其距离Dcm的点上。蟑螂可以迈步，每步之长不大于1cm，每步之后，都会有人告诉它，究竟是离真理近了还是远了。蟑螂能够记住一切，包括自己所迈过的步子的方向。证明，它只需迈出不多于3D/2+7步，即可找到真理。

解：蟑螂可先试探性地向东、南、西、北迈出1步（每次迈出后回到原地再迈下1步），于是不超出7步，蟑螂就可以查明，“真理”位于四个正方形中的哪一个，然后，再沿着平行于这个正方形的方向走，所走的步子不超过D (2)^(1/2)<3D/2，即可找到真理。

尼基托夫城的道路均可双向行车，现决定在两年内全部翻修道路，为此在第一年中，有些道路线成为单行线；到了第二年，这些道路恢复双向行车，其余的道路则限制为单向行车线。现知，在翻修过程中任何时刻，都能从城市中的任何一个地点驱车前往另外任何地点。证明，可将基托夫城中的道路全部改为单行线，使得仍可由城中任一地点驱车前往另外任何地点。

证：首先将第一年修路时作为单行线的道路及其指定的单向行车方向确定下来；将这些道路染为红色，并标上原来的箭头。

我们再来分两个阶段解答问题。在第一阶段中，我们来增加红色道路的数目，并为它们标上箭头，使得在增加了它们以后，题目中的条件仍可满足，真到达到了如下程度时，我们就停止增加新的红色道路：即对任意两个用由A指向B的红色箭头直接连接的路口A和B，又都存在仅仅沿着红色箭头头即可由B到A的路径（即存在由红色箭头构成的环路）。在第二阶段中，我们来给出满足题目条件的道路走向，从而最终完成证明过程。具体作法如下：

第一阶段：设路口A和B已用红色箭头A→B连接，但由B至A却没有用红色道路。即在任何由B通向A的路径上，并不都具有红色箭头，亦即存在“空”路段。我们来任意取出一条由B至A的路段。在这条路径所包含的所有红色路段上，所标示的方向显然都与箭头A→B一致（因为由B至A有这条路径作为通道）；我们只要照此（即与箭头A→B一致的方向）将“空路段”标定方向并染为红色，就可使得由B能沿着红色箭头走到A了。由于城市道路的数量是有限的。所以在若干步以后，我们就得到了许多由红箭头构成的环路，亦即许多由红色环路围成的“小岛”。

第二阶段：我们再将未包含在红色环路中的路段都染上绿色；在这些路段上目前都还存在着两个方向。但由于它们都是第二年修路时的单行线，于是我们可为每一段绿色道路都标上一个箭头，使之与第二年修路时所标的方向一样，这样一来，全城的道路都已标定了行车方向。

下面就来证明，按着所引入的方向，都可以沿着道路由任意一个路口A到达任一另外一个路口B。事实上，如果取这样一条由A至B的路段，使它恰是第二年修路时所走过的，那么现在在它上面就可能会有红色箭头也有绿色箭头。沿着绿色箭头，我们总是去往应去的方向，但沿着红色箭头却未必总是如此。例如，在我们所取的路径A…XY…B中的路段XY上，所标的红色箭头是由Y指向X的（即不能沿着路段XY通行），那么我们就可以沿着那样一条补上箭头Y→X后就成为第一阶段所构造的的红色环路的路径由X走到Y，由此所得到的由A至B的路径即为所求。