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

#### 万精油

• Administrator
• Hero Member
• Posts: 1831
##### 每周一题：巧克力阵 (7/26/04--8/1/04)
« on: 七月 26, 2004, 12:32:11 am »

（Ｎ－１）。如果Ａ（Ｎ）与Ａ（Ｎ－１）都是必输数。那么，当你遇到Ａ（Ｎ＋
１）时，如果你不是一次拿到Ａ（Ｎ），则由於Ａ（Ｎ－１）是必输数，你的对家

Ａ（Ｎ－１）／Ａ（Ｎ）大於０．５，（实际上这个比例趋近于黄金分割数０．６１８），你的

５０分的都是一些还没有解决的公开问题（比如费尔马定理就是其中的一道５０分

１５颗）。每堆摆成一列，然后从左到右把这些列排起来。如果你把它分成四堆，

(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)

#### 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.