2016年2月18日星期四

三角游戏:三壶和河内塔

提示我拉 Coxeter和Greitzer的“ Geometry Revisited”(GR)现成的阅读之后 约翰·康威和亚历克斯·里巴的 “ Stiener-Lehmus定理”(摘自 2015年最佳数学写作,由Mircea Pitici编辑)。 

GR包含一个关于“三线性坐标”的非常短的部分,用于草拟 三角形三角形。正如Coxeter和Grietzer解释的那样,

作为对用于在给定直角坐标下绘制点的普通方格纸的一种放心的救济,人们有时可以购买“三角”纸,该纸由三个平行线系统统治,将平面划分为一个 tessellation 等边三角形的集合。这样 纸可以方便地绘制已给定的点 三线性坐标 相对于(大)等边三角形。...这些坐标非常适合表示任何三个可变量具有恒定和的情况。

代表三角形的形状非常适合作为“三个可变量具有恒定总和的情况”,“三水罐问题”也是如此,Coxeter和Grietzer用来展示三线性的趣味性和实用性。

三壶问题

假设您有三个未分级的水罐,分别容纳8品脱,5品脱和3品脱的液体。您知道每个水罐可以容纳的总体积,但是由于上面没有写任何其他尺寸的信息,因此您不能使用单个水罐来量取全部数量以外的数量。现在假设8品脱的水罐已满,其他的水罐已空。在不丢失任何液体的情况下,如何测量出4品脱啤酒?

因此,此问题很好地适合了三线性坐标的情况:三个壶之间共享的液体总量保持不变(8品脱),并且每个点(a, b, c),分别代表8品脱,5品脱和3品脱的水罐中的量。但是,由于壶的大小不同,并非所有三线性点都可访问:点(0,0,8)表示3品脱壶中的所有8品脱,因此我们在(a, 5, c)和(a, b,3)切断了5品脱壶和3品脱壶。在三角形内留下一个平行四边形,代表壶的所有可能状态。

我们的目标是让其中一只水罐只有4品脱。有三种解决方案:(4,1,3),其中8品脱壶中有4品脱,5品脱壶中有1品脱,3品脱壶中有3品脱; (4,4,0),其中8品脱壶中有4品脱,而5品脱壶中有4品脱; (1,4,3),其中8品脱壶中有1品脱,5品脱壶中有4品脱,3品脱壶中有3品脱。


从一个水罐到另一个水罐的浇注是通过从平行四边形的一个边缘行进到另一边缘而显示的。因此,例如,从大酒壶(8,0,0)中的8品脱开始,我们可以将3品脱倒入最小的酒壶中,最后达到(5,0,3)。


继续,从平行四边形的一侧弹跳到另一侧,我们得到第一个解决方案:(8,0,0),(5,0,3),(5,3,0),(2,3,3) ,(2,5,1),(7,0,1),(7,1,0),(4,1,3)。


从另一个方向出发,从8品脱的水罐倒入5品脱的水罐会导致另一种解决方案:(8,0,0),(3,5,0),(3,2,3),(6, 2,0),(6,0,2),(1,5,2),(1,4,3)。



河内的塔

三壶问题让我想起了 河内塔 难题,其中在三个杆之间交换磁盘。

河内塔由三根杆组成,可在上面滑动磁盘。第一根杆上有一堆不同大小的磁盘,从最大到最小堆叠在一起,从而形成一个圆锥体。您的目标是将所有磁盘移到另一根杆上,以使磁盘永远不会位于较小磁盘的顶部,并且磁盘一次只能移动一个。

就像壶之间共享的液体量一样,我们可以认为圆盘的总重量在圆杆之间移动时保持恒定。壶之间的运动仅限于壶的完全填充或完全清空,这使三角形上的解决方案具有从一侧弹跳到另一侧的效果。这与河内问题的情况不同,在河内问题中,鱼竿之间的运动受到堆积规则的限制-但该规则也可能导致有趣的模式。

解决河内塔楼的方法有很多种,但我喜欢以下方法:如果标有鱼竿 a, b, c,从中移动磁盘塔 ac,先将没有最后一个磁盘的塔移动到 b,将最后一个磁盘移到 c,然后将塔架移回已存在的最后一个磁盘的顶部 c。如果您不熟悉 递归,您可能不会相信这是一个解决方案。放心,通过改变搬家问题 n 磁盘进入移动问题 n-1个磁盘(两次),问题得到解决:您只需要继续将解决方案应用于每个较小的磁盘集,直到问题完全消失。

让我们想象一下 n 磁盘版本,我们有重量为1,2,3,...的磁盘 对于 n= 3,我们有重量分别为1、2和3的磁盘,因此我们可以在长度为6(所有磁盘的总重量)的三角形上玩游戏。


假设对于棒 a, b, c 我们使用坐标(a,b,c),其中字母的值代表该杆上的圆盘重量。可以说我们正在尝试将磁盘从 ac,这将要求我们从(6,0,0)移至(0,0,6)。如果遵循上面的递归解决方案,我们将获得如下所示的模式:



如果我们只使用两个磁盘,那我们将有一个较小的三角形和一个更简单的解决方案,您会看到两个磁盘解决方案在三个磁盘解决方案中出现两次,但是旋转了,并且这两个较小解决方案的副本通过移动最大的磁盘链接在一起。这正是您对我们的算法所期望的(将 n将-1堆栈放到“备用”杆上, n 磁盘到目标杆上,然后移动 n-1堆叠到目标杆上)。


这是直到 n = 6.

取而代之的是测量三角形上磁盘的重量,我们可以只使用每个轴来计数磁盘的数量-因此对于3个磁盘问题,我们将只有一个边长为3的三角形。这意味着每次移动都会具有相同的长度(长度1),并且在上面的三角形中不同的一些点现在将相同。

模式看起来有所不同,但它们仍具有相同的递归结构-每个解决方案都包含前一个解决方案的两个副本,并通过最后一个磁盘的移动来加入。

所以。三线性坐标提供了一种有趣的显示方式 三角家庭,这是表示经典3罐问题的有用方法,并且提供了一种查看河内塔解决方案的“递归”的方法。顺便说一句,当我手动尝试为水罐和河内问题制定解决方案时,我发现了三角形方格纸 这里 helpful.

注意:三线性坐标有时称为三角坐标,有时又称为重心坐标-有时区分这些坐标系统的各种类型:请参阅 这个笔记 from the math forum.