妙想奇思奎伯的杯子问题_第1页
妙想奇思奎伯的杯子问题_第2页
妙想奇思奎伯的杯子问题_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、妙想奇思奎伯的杯子问题a.巴尼在饮店工作，他给他的两位顾客表演10个杯子游戏。b.巴尼：这有一排10个杯子，前5个杯子装着可乐，后 5个杯子空着，你能挪4 个杯子，使满杯和空杯间隔排列吗 ?c 巴尼：好，只需第2 个杯子和第 7 个杯子交换位置，第4个杯子和第9个杯子交换位置。d.奎伯教授总想一些奇特的方法，碰巧听到了这个问题。奎伯教授：为什么要挪4 个杯子，我们能否只动2 个杯子 ?e.奎伯教授：很简单，把第 2个杯中的可乐倒进第 7个杯中，把第 4 个杯中的可乐倒进第 9 个杯中。不寻常的奎伯尽管奎伯教授通过巧辩解决了这个问题，但普遍问题并不像这个问题这么平常。例如，同样的问题，如果是 1

2、00 个满杯和 100 个空杯需要对调多少次才能使满杯和空杯间隔排列 ?用 200 个杯子做实验不很实际，我们首先分析较小的 n 值的解决方法，这里n 是满杯或空杯数。你可以用两种颜色的记号来解题 ( 或者牌的正反面、硬币的正反面、不同面值的硬币等等 ) 当 n=1 时无解。 n=2 时显然只对调一次。 n=3 时也对调一次。进一步努力，你可以发现简单的公式， n 是偶数时，对调数为 n/2 。 n 是奇数时，为 (n 1)/2 。所以，如果是100个满杯和 100 个空杯，需要对调 50 次。这需要移动 100 个杯子，奎伯的幽默作法把移动杯数减少了 一半。又有一个类似的分隔同题，但比较难解

3、。在同一排中有 n 个一类物体，相邻的是 n 个另一类物体( 如上面用玻璃杯、记号、牌等来表示) 你还是要把这一排列变为互相间隔状态，但我们移动原则不同了。我们必须移动一对记号放到队列中任何空白处，移动中不能改变这两个记号的顺序。例如，这是 n=3 时的做法：XXXOOOXOOOXXX00 XOXOXOXOX一般的解法是什么呢 ?n=1 时无解。你很快也发现， n=2 时也无解。对所有大于2的n,最小的移动次数是no当 n=4 时，解决这个同题就很不易，或许你已经解决了，或许当 n 大于等于 3 时你能用公式来表示这个问题的解。这些问题变化一下，可以产生一些其它的难题：(1) 规则同前，只是当

4、你移动一对记号时，如果是不同颜色的，在移动前交换它们的位置。也就是黑红对在移动前变为红黑对， 8 个记号移动5 次可以完成， 10 个记号移动 5 次也可以完成。我们还不知道一般的解决方法，或许你能找到。(2) 规则和原题一样，只是一种颜色的记号有n 个，另一种颜色的记号有n+1 个，并且只有颜色不同的一对才能移动。可以证明：无论n 为何值，都需移动n2 次，且这是最小的移动次数。(3) 三种不同颜色的记号，移动每对相邻的记号使三种颜色相互间隔，如果n=3(即总共9个记号)需移5次。在以上的变化中，我们都设变化为最后排列时排列中没有空隙，如果允许空隙存住，移动 4 次就能得到结果。一些变化的假设迄今还没有提出来， 更不必说解决了。 比如，在以上的变化中，一次移动 3 个或更多相邻记号。还有，如果先移动 1 个记

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论