Author Topic: 每周一题:巧克力阵 (7/26/04--8/1/04)  (Read 12971 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题:巧克力阵 (7/26/04--8/1/04)
« on: 七月 26, 2004, 12:32:11 am »
上周的题目有好几个人做出来,我再来总结一下。

仔细想想就很容易发现开始的几个必输数,2,3,5,8,...。
对数学比较熟悉的人大约就会想到斐波纳契数。想到以后再来证明就比较容易了。
斐波纳契数的定义是下面一项等於前面两项之和。A(N+1)=A(N)+A
(N-1)。如果A(N)与A(N-1)都是必输数。那么,当你遇到A(N+
1)时,如果你不是一次拿到A(N),则由於A(N-1)是必输数,你的对家
总可以把你逼到A(N)。如果你第一次一下拿到A(N),则由於
A(N-1)/A(N)大於0.5,(实际上这个比例趋近于黄金分割数0.618),你的
对家就可以一下把剩下的全部拿完。所以,A(N+1)也是必输数。

这道题我是二十多年前读KNUTH的名著(The Art of Computer Science)时见
到的。这本书里有很多有趣的题目。他把这些题目按难度打分。10分的比较容易,
50分的都是一些还没有解决的公开问题(比如费尔马定理就是其中的一道50分
的题)。30分的题相当于一个本科生的project.我们这道题好像是一个25分的
题。

看来这个论坛对巧克力情有独衷,我们这周的题目还是拿M&M说事。

本周题目

桌上有15颗巧克力豆。把它们随意分成几堆,每堆的数量也随意(只不过总数是
15颗)。每堆摆成一列,然后从左到右把这些列排起来。如果你把它分成四堆,
那么你现在就有一个参差不齐的四列巧克力阵。好了,现在开始移动这些巧克力。
每次把每列最上面的一颗拿起来组成新的一列,再把这一列放在最左面。如果有一
列完全没有了,则把它右面的列往左靠,占掉那个空位置。如此一直拿下去(把每列
最上面的一颗拿起来组成新的一列放到最左面),你会发现用不了多久你的
巧克力阵就会形成(54321)的三角阵。显然,这个三角阵是一个不动点,无
论你再拿多少次,再也不会变了。我们的题目是:请证明无论开始的状况如何(堆
数以及每堆的个数),这个三角阵是必然结果。

比如:
(3,5,3,4)->(4,2,4,2,3)->(5,3,1,3,1,2)->(6,4,2,2,1)->(5,5,3,1,1)->(5,4,4,2)
->(4,4,3,3,1)->(5,3,3,2,2)->(5,4,2,2,1,1)->(6,4,3,1,1)->(5,5,3,2)->(4,4,4,2,1)
->(5,3,3,3,1)->(5,4,2,2,2)->(5,4,3,1,1,1)->(6,4,3,2)->(4,5,3,2,1)->(5,3,4,2,1)
->(5,4,2,3,1)->(5,4,3,1,2)->(5,4,3,2,1)

这个题目还可以推广到更大的数,21,28,任何等於N*(N+1)/2的数。

idiot94

  • Sr. Member
  • ****
  • Posts: 484
每周一题:巧克力阵 (7/26/04--8/1/04)
« Reply #1 on: 七月 27, 2004, 09:59:42 am »
A silly proof... not nice at all:

Let us define S={s1, s2, .., s_w| s_i is positive integer} as a Valid State of the MM's if the sum of s_i = N. N is the total number of MMs.
Let us assume N=1+2+..+m.  (m is a positive integer)
Let us call the described operation in the problem as a Transform.
Let us define a valid state S is Reachable, if there is a valid state S', such that from S', after one transform S' will become S.
We call state A is Reachable from state B, if after a finite number of transforms, from state B, you will get state A.
We call state A is equivalent to state B if A is reachable from B AND B is reachable from A. Apparently, this equivalency is an "equivalent relation" in general sense.
If state S has an equivalent state S' (S' does not necessarily differ from S), then define S_hat = {valid states that are equivalent to S} as a Kernel of the N M&M's.
For example, the state S0={m, m-1, ..., 1} has S0_hat ={S0}. And therefore, it is a kernel of N.

Step A. A few observations:

Notice that there are only finite number of valid combinations of the MMs, thus no matter which state you start with, you will have to fall into one of the kernels of N. (proof is trivial and omitted.)

State S_e={1, 1, 1, ...., 1} (N 1's) is apparently not reachable (by anything). And hence, S_e is not in any kernel.

For any reachable state S ={ r1, r2, ..., rk }, we notice that r1 >= k-1. Since r2, .., rk must have been there one transform earlier and they all contributed 1 to r1.

For any kernel member S, it is, of course,  reachable from another kernel member S', let us call this S': ex(S). (BTW, this relation "ex" is actually a function, since S' is unique --- because if S" also directly lead to S, yet different from S', then we will see from S, the unique transforms will lead to two distinct states S' and S", which is impossible. Yet this property is not critical to our analysis below.)
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

idiot94

  • Sr. Member
  • ****
  • Posts: 484
每周一题:巧克力阵 (7/26/04--8/1/04)
« Reply #2 on: 七月 28, 2004, 08:30:47 am »
I am sorry to post this message so late:

1) I was busy yesterday and after I though I figured it out, I only had time to post the above part.
2) Yet, when I got home, I found out that I thought I proved "for any k, rk >= r1 - k" --- yet, I was wrong. I did not prove this result. So the entire "proof" in my mind was wrong. I apologize for this silly mistake.
3) I will still be busy for the rest of this week and then will be out for next whole week. So I won't have time to think about this problem any more.
4) I wanted to delete my previous post not to waste reader's time. However, I would appreciate it if Prof. Wan could decide it for me ---- if you think it is better to keep it, then we keep it, otherwise, would you please delete it for me? Thank you, sir.

And again, I am terribly sorry for the mistake.
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题:巧克力阵 (7/26/04--8/1/04)
« Reply #3 on: 七月 28, 2004, 09:01:52 am »
I think we should keep it there.  People can (and do) learn from mistakes (most importantly learn from other people's mistakes). There are two meanings of learning from other people's mistakes, one is obviously not to go that approach again, another is to pick out good stuff from that approach.  Your post services both purposes.

testpost

  • Newbie
  • *
  • Posts: 23
每周一题:巧克力阵 (7/26/04--8/1/04)
« Reply #4 on: 七月 28, 2004, 01:02:06 pm »
1. Align columns bottom up

6   x
5   xx     x
4  xxxxx   x
3  xxxx*  xxx
2  xxxxxx xxx
1  xxxxxxxxxxx
0  xxxxxxxxxxxx
   0123456789...->

2. Then define postion in (X,Y)for each ball.
Assuming the bottom left one is (0,0). For
example, the star(*) above is (4,3)

3. Define height of the ball as X+Y. for example,
the star(*) above is 4+3=7.

4. Seperate the transform into 2 phase: phase 1 -
remove bottom line (Y=0), shift down and right all
left by 1, turn removed bottom line up and form a
column at left (X=0). Apprantly, the height of any
ball remains the same.

5. phase 2 only happens if empty column in middle.
If there is no such column, transform is complete.
Otherwise, shift all right side balls of this column
left by 1. Balls moved in this phase decrease their
height by 1. If there is more empty columns in middle,
continue phase until transform complete. In phase 2,
some balls decrease their height while no one increase.

6. In one word, height of a ball will never increase during
transform. Define a steable state: any consequence
transform keep all ball's height the same. You may also
notice that all transforms afterwards can only contain
phase 1 - due to phase 2 decrease some ball's height.

7. After certain number of transform, all initial state
will enter into a steable state. Otherwise, at least 1
ball will decrease its height and there is a limit for
culmulation of all ball's height.

8. At steable state, monitor a height n ball from left most
position (0,n). It is easily to prove it moves step by step
towards (n,0). For ex, a ball at (m, n-m)'s next postion
is definately (m+1, n-m-1) given (0<=m<n). (No empty column
should appear in middle - due to no phase 2 transform.) And
next postion for (n,0) is (0,n). Speed of this move is 1/n

9. Define a height n is "filled" means all height n positions
have a ball. and "unfilled" height is at least 1 ball at this
height but not filled.

10. If there is a unfilled height, say m, and if there is a
ball at higher than m, there is a ball at m+1. (easy to prove)
Let's call the ball at m+1 the ball A, and a unfilled position
(any seleted one) at postion m the slot B.

11. Speed of the ball A moves at 1/m+1 and the slot B moves at
1/m. within m times of transform, there must be a state that the
ball A sits on top of slot m. This against the rule - balls are
aligned bottom up.

12. So no ball is higher than unfilled height.

13. in case of 15, if any layer lower then 5 (height 4) is not
filled, the extra ball must sit layer 5 or higher - then
contradict with statement 12.
testposttestposttestpost

idiot94

  • Sr. Member
  • ****
  • Posts: 484
每周一题:巧克力阵 (7/26/04--8/1/04)
« Reply #5 on: 七月 29, 2004, 04:01:14 pm »
wow... tough tough... did not finish reading your proof yet... maybe when I come back... looks very complex :)
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

testpost

  • Newbie
  • *
  • Posts: 23
每周一题:巧克力阵 (7/26/04--8/1/04)
« Reply #6 on: 七月 30, 2004, 09:41:51 am »
Hopefully, this looks simpler:

1. Align columns bottom

6   x
5   xx     x
4  xxxxx   x
3  xxxx*  xxx
2  xxxxxx xxx
1  xxxxxxxxxxx
0  xxxxxxxxxxxx
   0123456789...->

2. Then define postion in (X,Y)for each ball.
Assuming the bottom left one is (0,0). For
example, the star(*) above is (4,3)
We have assumption:
2.1 for any x>0, if (x,0) have a ball or filled,
(x-1,y) have a ball or filled. (no empty column)
2.2 for any y>0, if (x,y) have a ball or filled,
(x,y-1) have a ball or filled. (bottom up align)

3. Seperate the transform into 2 phase, phase 1:
if y==0, (x,0) ==> (0,x)
if y!=0, (x,y) ==> (x+1, y-1)
(This equilvalence to get 1 from each column and
put form a column at left)

4. phase 2: if any column (x=n) in middle is empty:
if x<n: (x,y) ==> (x,y) unchange
if x>n: (x,y) ==> (x-1, y)
Do it until all column in middle is not empty.
(This equilvalence the re-arrange by remove the empty
columns)

5. Notice x+y for each ball is constant in part 1 of
the transform and not increase in part 2 of the
transform.

6. Define a steable state: every ball's x+y remains
const in any consequence transform. After certain number
of transform, all initial state will enter into a steable
state. (easy to prove)

7. Define layer n filled: n balls filled all n positions
satisfy x+y=n-1. and "unfilled" means at least 1 ball at
x+y=n-1, but not filled. Define a "pit" at layer n is a
postion (x,y) at x+y=n-1 have no ball.

8. At a steable state, consequence transforms have only
part1. Assume the lowest unfilled layer is n, there is a
pit at layer n. Say it is (i, n-i-1). If there is also a
ball at layer n+1, say (j, n-j). After n-i moves, the ball
is at (m,n-m) and the pit is at (0,n-1), where 0<m<n.
After another n*m moves, the pit is at (0, n-1) and the
ball is at (0, n). then it is against the assumption 2.2.

9. So, we have conclution: there is no ball beyond any
unfilled layer.

10. n(n+1)/2 balls make out-most layer filled. other number
of balls steable at the situation: out-most layer unfilled
and all rest layer are filled.
testposttestposttestpost

超级菜鸟

  • Newbie
  • *
  • Posts: 3
Should you move n*(n-m) times in the No. 8th step?
« Reply #7 on: 八月 02, 2004, 09:25:47 am »
At a stable state, consequent transformations have only part1. Assume the lowest unfilled layer is n, there is a pit at layer n. Say it is (i, n-i-1). If there is also a ball at layer n+1, say (j, n-j). After n-i moves, the ball is at (m,n-m) and the pit is at (0,n-1), where 0<m<n. After another n*(n-m) moves, the pit is at (0, n-1) and the ball is at (0, n). then it is against the assumption 2.2.

万教授能否贴一下最标准的解法? 个人认为testpost的解法还可以简化. 是否只要证明高度只能递减就可以?