|
奎伯的杯子问题
! I. c/ j7 p* \' z. V' V, R% E' D! `/ T# P3 X- U9 c
9 G: A0 L# t4 G. _" v% I
" f0 j# ?$ b0 \6 c+ O3 F# ]# c5 e" T |# Y
9 X$ h. B, k+ F. b
| 5 C, J, ?% o0 i8 c: J' k7 I
- v4 j \6 V, O$ T' J+ N
 MSITStore:C:\My%20Documents\数学电子书籍\B01-《啊哈!灵机一动》---妙想奇思——趣味数学谜题60例.chm::/image/1-12.JPG">
| # @' x( R4 ~; D9 _( J! c) ?: f1 f
a．巴尼在饮店工作，他给他的两位顾客表演10个杯子游戏。 |
- M" }0 F t9 O: x& b* b l
' h8 A0 n" O$ k3 G" A6 N2 Z| 9 t$ ^& J& l0 J; C) ~; }" @
: J# q" c; V& W8 X2 h4 r' g) E
MSITStore:C:\My%20Documents\数学电子书籍\B01-《啊哈!灵机一动》---妙想奇思——趣味数学谜题60例.chm::/image/1-13.JPG"> | 9 d% O1 b. f, `! P, i
b．巴尼：这有一排10个杯子，前5个杯子装着可乐，后5个杯子空着，你能挪4个杯子，使满杯和空杯间隔排列吗? | 1 P+ V3 C/ g) a4 _
# l) ~. P0 x- b" f( e. n
| 4 c1 x" V) M) p0 W5 P: f
# N- Q' Y. J+ s7 }3 ^. H
MSITStore:C:\My%20Documents\数学电子书籍\B01-《啊哈!灵机一动》---妙想奇思——趣味数学谜题60例.chm::/image/1-14.JPG"> | . A# O: L! M4 m
c．巴尼：好，只需第2个杯子和第7个杯子交换位置，第4个杯子和第9个杯子交换位置。 | + |/ a8 ~4 B9 z7 m- t
# } K4 g9 p5 e l) Z+ Y
| 7 K, R# C, O3 Q$ d% O1 d+ b
" O/ [% C/ m2 B6 m+ M
MSITStore:C:\My%20Documents\数学电子书籍\B01-《啊哈!灵机一动》---妙想奇思——趣味数学谜题60例.chm::/image/1-15.JPG"> |
3 R V! {$ X- Id．奎伯教授总想一些奇特的方法，碰巧听到了这个问题。
% z# E; Q* R; B奎伯教授：为什么要挪4个杯子，我们能否只动2个杯子? |
, \. e% _; J( u* H% I3 p; U6 Q- Y/ F+ A; s r' E
| # }- c8 X" X) b, s7 L: u+ A1 X
, p' U" X4 f C: H5 k4 u# L" E
MSITStore:C:\My%20Documents\数学电子书籍\B01-《啊哈!灵机一动》---妙想奇思——趣味数学谜题60例.chm::/image/1-16.JPG"> | 5 W4 n0 C+ J8 H
e．奎伯教授：很简单，把第2个杯中的可乐倒进第7个杯中，把第4个杯中的可乐倒进第9个杯中。 |
, Y, U# T8 Z. m$ q7 s+ \* q1 m
; k! _- D' Y" M6 Y/ V) ^, S9 T. \不寻常的奎伯 0 Q% q# N4 E5 D: [( W
* E' M: s' D) v, f尽管奎伯教授通过巧辩解决了这个问题，但普遍问题并不像这个问题这么平常。例如，同样的问题，如果是100个满杯和100个空杯需要对调多少次才能使满杯和空杯间隔排列?
+ V9 ~4 G d, Q8 W) I7 p- C% z3 T
0 @" b' U: y1 A1 V! k' b& _用200个杯子做实验不很实际，我们首先分析较小的n值的解决方法，这里n是满杯或空杯数。你可以用两种颜色的记号来解题(或者牌的正反面、硬币的正反面、不同面值的硬币等等)当n=1时无解。n=2时显然只对调一次。n=3时也对调一次。进一步努力，你可以发现简单的公式，n是偶数时，对调数为n/2。n是奇数时，为(n—1)/2。所以，如果是100个满杯和100个空杯，需要对调50次。 " b- E9 q; t7 n- j1 u) I3 }' L
1 G+ Z/ r; x+ H4 b2 r& \
这需要移动100个杯子，奎伯的幽默作法把移动杯数减少了一半。
' K, q4 L* n* x$ Y * I% |! m0 l' }' J p1 g/ } D: s& K
又有一个类似的分隔同题，但比较难解。在同一排中有n个一类物体，相邻的是n个另一类物体(如上面用玻璃杯、记号、牌等来表示)你还是要把这一排列变为互相间隔状态，但我们移动原则不同了。我们必须移动一对记号放到队列中任何空白处，移动中不能改变这两个记号的顺序。例如，这是n=3时的做法：
# ]- F# L3 \2 v0 s0 z
; \% S: l9 `8 O5 V2 d% `7 nXXXOOO5 K2 N1 s) [! K7 O- c
XOOOXX+ Q0 B( e d( f) W2 z' z! m6 E6 m
X00 XOX! T# Z7 V: u* z. t, V! k
OXOXOX 0 U: e! m4 s. |
! U3 `2 Q& w* B: O* ]
一般的解法是什么呢?n=1时无解。你很快也发现，n=2时也无解。对所有大于2的n，最小的移动次数是n。 7 I: `0 Z4 \; t7 ]& z' k
9 T$ ?$ T+ u G1 u6 O当n=4时，解决这个同题就很不易，或许你已经解决了，或许当n大于等于3时你能用公式来表示这个问题的解。 7 |+ ]" i) o1 s* A
) U" f" C9 Q' E4 b) [' B
这些问题变化一下，可以产生一些其它的难题： + ^) I4 O" C% k; x& `0 @- m0 q0 }
(1)规则同前，只是当你移动一对记号时，如果是不同颜色的，在移动前交换它们的位置。也就是黑红对在移动前变为红黑对，8个记号移动5次可以完成，10个记号移动5次也可以完成。我们还不知道一般的解决方法，或许你能找到。 ! T9 ~' U* a6 [) g$ a# c
7 s2 C( s+ L9 o, a/ M5 l# O9 d(2)规则和原题一样，只是一种颜色的记号有n个，另一种颜色的记号有n+1个，并且只有颜色不同的一对才能移动。可以证明：无论n为何值，都需移动n2次，且这是最小的移动次数。 2 y; j0 O5 ]4 t3 i. f$ t* O
- r5 x) n9 G& s/ T6 T0 Z(3)三种不同颜色的记号，移动每对相邻的记号使三种颜色相互间隔，如果n=3(即总共9个记号)需移5次。在以上的变化中，我们都设变化为最后排列时排列中没有空隙，如果允许空隙存住，移动4次就能得到结果。 : _& G: k$ {: J4 @8 x- c- y
5 a- Z2 o# t+ T& M$ m一些变化的假设迄今还没有提出来，更不必说解决了。比如，在以上的变化中，一次移动3个或更多相邻记号。 ' ~3 X* t9 g T! T! Q' q8 d6 L
% p# ~+ l/ i. n# V! p* y
还有，如果先移动1个记号，再移动2个相邻的记号，接下来是3个以至4个等等。已知各有n个两种颜色的记号，移动n次能解决问题吗? | 
IP卡
狗仔卡
发表于 2005-4-25 10:28
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
