Author Topic: 每周一题: 天平换边 (6/7/2004-6/13/2004)  (Read 17424 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 天平换边 (6/7/2004-6/13/2004)
« on: 六月 10, 2004, 06:46:51 pm »
一个老师坐在教室里。他面前放着一个天平秤。天平上两边都有一些砝码。这些砝码上都写有至少一个学生的名字。这些学生都在教室外。他把学生一个一个的叫进来。每个学生进来时,就把天平上有他(她)的名字的法砝对换(也就是原来在左面的放到右面,在右面的放到左面)。刚开始的时候,天平向左面倾斜(左面重)。试证明这个老师一定可以找到一组学生,把他们叫进来后,天平改向右面倾斜。

Anonymous

  • Guest
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #1 on: 六月 11, 2004, 03:10:24 pm »
If all the students are inside, all the weights have switched sides, and the scale must tilt the other way.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #2 on: 六月 14, 2004, 07:38:44 pm »
Not that simple. If it were that simple, I would not put it as the first question of this forum.

Think again? Some of the weights may be back to the original side after you call all students in.

On the other hand, it is not very hard.

Anyway, I am glad the reply function works now.

差不多

  • Newbie
  • *
  • Posts: 10
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #3 on: 六月 14, 2004, 10:26:34 pm »
呵呵呵,先给万教授问好。 :)

咳咳,这题一眼看去简直没头绪,不过不着急,慢慢来。

先想如果总共只有一个学生,那么很显然,把这学生叫进来就完了,不用多说了吧。

再想如果总共有俩学生,叫他们1,2。那么有些砝码只有1的名字,有些只有2的名字,有些12都有。

先规定一些符号:
W(1L)表示最初在左面的只有1的名字的砝码总和;
W(2L)表示最初在左面的只有2的名字的砝码总和;
W(12L)表示最初在左面的有12的名字的砝码总和;
W(1R),W(2R),W(12R)类似表示最初在右面的砝码。

那么,根据已知左面重,有下面的不等式成立:

W(1L)+W(2L)+W(12L) > W(1R)+W(2R)+W(12R) (这个纯大于号很重要哦,嘿嘿)

只有两个学生,那么只有三种可能的方案:只叫1进来,只叫2进来,12都叫进来。
如果用上面的符号表示执行各方案后天平左右的砝码分布情况,并且假设
问题无解(!),也就是说任何一种方案都未能使天平右倾(极左思潮严重啊 :( ),
那么可以得到三个新的不等式:

只叫1进来:W(1R)+W(2L)+W(12R) >= W(1L)+W(2R)+W(12L)
只叫2进来:W(1L)+W(2R)+W(12R) >= W(1R)+W(2L)+W(12L)
1,2都进来:W(1R)+W(2R)+W(12L) >= W(1L)+W(2L)+W(12R)

把上面三个不等式,还有头一个,统统加在一起,可得:
2(W(1L)+W(2L)+W(12L)+W(1R)+W(2R)+W(12R) )> 2(W(1L)+W(2L)+W(12L)+W(1R)+W(2R)+W(12R))

注意上式左右其实是同样的东东,得出显然的矛盾!由此反证无解的假设不成立,即上述三种方案
必有一个使天平右倾(TA-DA,邓小平出世! :lol: )。

呵呵呵,这题到这儿,差不多觉得就差不多了。对于n个学生的情况,只要你有耐心,把表示最初
情况的不等式列出来,再把所有可能方案全不成立得出的不等式也列出来,把它们全加一堆(总共
大概2^n个),就能得出一个矛盾的不等式(其两边都是2^(n-1) 倍的所有n中取m(m从1到n)的组合相加)。

嗯,最后这步有点马虎,真要做也太烦,不知万教授有没更简洁的解答。
就行了

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #4 on: 六月 17, 2004, 12:18:14 pm »
提示:随便抓一个学生,先考虑那些只有这个学生的名字的砝码(决定是否要叫这个学生),然后把这个学生和这些砝码都去掉,用数学归纳法。

没头脑

  • Newbie
  • *
  • Posts: 8
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #5 on: 六月 17, 2004, 03:07:59 pm »
万教授这么一提示,没头脑也能解题了。

用数学归纳法:

1、只有一个学生的情况。

两边的砝码都只能写着这个学生的名字,把这个学生叫进来,两边砝码全部
对换,左倾变右倾。

2、假设n个学生的情况下,老师一定可以找到一组学生,把他们叫进来后,
天平改左倾为右倾。

3、证明n+1个学生的情况下,老师也一定可以找到一组学生,把他们叫进来
后,天平改左倾为右倾。

在n+1个学生中任意抽出一个学生A,先在天平两边留下只写有学生A名字的
砝码,其它的砝码暂时拿开。这时有两种情况:

3a、天平右倾或平衡,就决定不叫学生A进来。把这些只写有学生A名字的砝
码拿开,原样放回其它砝码,天平只可能左倾。这时就成了n个学生的情况
(不必考虑有些砝码上有学生A的名字,因为已决定不叫学生A进来,所以那
些写有学生A名字的砝码不受其影响,等价于没有学生A名字的情况)。根据
2的假设,在这n个学生里总能找到一组学生,叫进来后天平改成右倾。此时
再原样放回那些只写有学生A名字的砝码,天平仍右倾。这组叫进来的学生
便也是n+1个学生的解;

3b、天平左倾,就决定叫学生A进来。学生A进来后,这些只写有学生A名字
的砝码对换,天平右倾。这时把这些砝码拿开,原样放回其它砝码。由于此
时学生A叫进来了,根据题意,那些写有学生A名字的砝码就都得换到另一边
去。换好后,有两种情况:

3b1、天平右倾或平衡,就决定不叫其他学生进来了,因为在此情况下放回
那些已换好位的只写有学生A名字的砝码,天平右倾。这个叫进来的学生A便
是n+1个学生的解;

3b2、天平左倾,这时就成了n个学生的情况(不必考虑有些砝码上有学生A
的名字,因为已把学生A叫进来,那些写有学生A名字的砝码都已换好位,所
以不再受学生A影响,等价于没有学生A名字的情况)。根据2的假设,在这n
个学生里总能找到一组学生,叫进来后天平改成右倾。此时再放回已换好位
的那些只写有学生A名字的砝码,天平仍右倾。这组叫进来的学生加上最先叫
进来的学生A,便是n+1个学生的解。

3得证。

由1、2、3,原题得证。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #6 on: 六月 17, 2004, 09:33:10 pm »
这个解法完全正确,不过叙述有点太烦,也许可以简单一点。

这个方法的好处是,它不但给出了存在性的证明,而且还构造了具体换法。先找出有单个名字的砝码,决定这个名字换不换。然后把这个名字从所有别的砝码上去掉,再如此进行。

这道题还有更简单的解法,但不是我想出来的。三个星期以前我到我大学同学家聚会。屋子里一大堆中国人(都是同学和家属),就一个美国人。说是我同学的女儿的男朋友,现在还在读高中。同学介绍说这个人是绝对天才,聪明的不得了。我想我这辈子见过的聪明人不少(当初在中科院数学所,没有什么笨人:),去跟它聊聊再说。后来发现他得过世界奥林匹克数学竞赛金牌,果然不是一般的聪明。想想他们这些人解难题一定有一套,於是就把这道题出给他了。心想大概这个聚会他都会想这个问题。没想到我刚转身到边上的桌子上拿了一罐饮料,他就说他解出来了。他的解法不用什么规纳法,而是考虑所有的学生子集。如果把这些子集一起考虑,那么每个砝码在左右天平上出现的次数相同。现在天平向左倾,那么要保持平衡,必然有子集使得天平向右倾。这个解法真是太美了。算是我从这高中生那里学了一招。后来整个聚会上我给他出了好几道题,都是我认为比较难的,他都在十来分钟的时间解出来了。平常都说美国中学教育没有中国好,但看看他们的尖子学生,还是相当厉害的。难怪丘成桐说美国的尖子生比中国的厉害。

Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #7 on: 六月 29, 2004, 01:40:57 am »
不得了,我也是当初去参加过奥林匹克竞赛的,惭愧得很,读了万教授
说的这位美国学生的解法,还是又想了十分钟才搞清他是怎么解的。美
国数学奥林匹克国家队的教练和领队冯祖鸣是我的大学同学,九六年带
队去香港,六名美国学生统统得了满分,在竞赛史上可谓空前绝后。

万教授的论坛办得好,大家鼓掌。我自己也有个网站,想干点类似的事
情,但是实在没有时间经营。今天来给万教授捧捧场。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #8 on: 六月 29, 2004, 08:54:38 pm »
谢谢谢谢. 象四月这样的ACT时代的老网友能来捧场,真是很高兴.

希望大家积极参与,把这个论坛搞得热闹起来.

idiot94

  • Sr. Member
  • ****
  • Posts: 484
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #9 on: 七月 23, 2004, 03:01:09 pm »
sigh... pei4 fu2 pei4 fu2 ...
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

超级菜鸟

  • Newbie
  • *
  • Posts: 3
请详细解释一下那个美国高中生的解答.
« Reply #10 on: 七月 26, 2004, 08:28:58 am »
万教授, 看了半天那个美国小天才的解答, 还是不明白, 您能否具体解释一下? :-) 谢谢.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 天平换边 (6/7/2004-6/13/2004)
« Reply #11 on: 七月 26, 2004, 09:01:36 am »
I don't have easy access to Chinese typing at work, so I will use English here.

First of all, it is easy to show that the state of the weights is independent of the order that the students get called in, only the student set matters.

How many subsets are there? Suppose there are N students, then there are 2^N subsets (each student can be in or out of the subset).  Now, consider each weight, depends on whether a student (who's name is on this weight) is in the subset or not, the weight will be either on the right or on the left. In other word, each weight has equal number of times being on the left, or being on the right if we take all the subset into account. Thus, if we add up all the weight of all the subsets on the left, it should equal to the sum of all the weight of all the subsets on the right. We know there's a subset that makes the balance tilt to the right (the initial state), thus, in order to make the sums equal, there must be a subset that tilt the balance to the left. QED

超级菜鸟

  • Newbie
  • *
  • Posts: 3
Thanks. Prof. Wan.
« Reply #12 on: 七月 26, 2004, 10:09:20 am »
NICE!