免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] n+1个砝码按质量依次放在天平较轻一端,求证最后天平平衡

$n+1$个质量为正整数的砝码总质量为$2n$,按质量降序从左到右排列,开始天平两端平衡,从最左边依次取砝码放在天平较轻的一端,若天平平衡则放任意一端,求证最后天平仍平衡
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

刚刚问了一位网友,他给了一个解答。为了不影响别人的思路,先不发上来。想看看其他网友的解答。我自己没想出来。

TOP

相关问题:
已知用克数都是正整数的k块砝码和一台天平可以称出质量为1,2,3,…,1093克的所有物品。
(1)求$k$的最小值;
(2)当$k$取最小值时,这$k$块砝码的组成方式是否是唯一确定的?并证明你的结论。
            
            变式:题目改为:
已知用克数都是正整数的k块砝码和一台天平可以称出质量为1,2,3,…,2014克的所有物品。
(1)求$k$的最小值;
(2)当$k$取最小值时,这$k$块砝码的组成方式是否是唯一确定的?并证明你的结论。

TOP

我把网友的解答发上来,但我觉得他这个解答有问题,最后那两行,如果按他说的分配进两个集合,那样砝码的大小顺序就会改变
当$n = 1, 2$时显然,当$n \ge 3$时
若所有$n+1$个砝码中至多有一个质量为$1$,则其余$n$个质量至少为$2$,总质量$S \ge 2n+1 > 2n$矛盾
所以所有砝码中至少有$2$个质量是$1$
假设$n = k$时成立,即任意$n+1 = k+1$个总质量为$2n = 2k$的砝码都能使天平平衡
则当$n = k+2$时,共$n+1 = k+3$个砝码,总质量为$2n = 2k+4$
由归纳假设知前$k+1$个总质量为$2k$的砝码能使天平平衡,即能分为$A, B$集合使得$\displaystyle\sum_{\alpha \in A}\alpha = \displaystyle\sum_{\beta \in B}\beta$
所以对于前$k+1$个总质量为$2k+2$的砝码
若多出的$2$质量分为两个$1$分别分配进$\alpha \in A, \beta \in B$,则天平平衡
若多出的$2$质量单独分配进$\alpha \in A$或$\beta \in B$,则天平两端相差$2$
此时用剩余的两个质量为$1$的砝码调节即可,由归纳法知对任意$n$都能使天平平衡

TOP

请大家再看一看这个题,我觉得网友的解答是有问题的

TOP

回复 3# 其妙
这题如何做?

TOP

命题加四个字,修改为:大于等于n+1个质量为正整数的砝码总质量为2n,按质量降序从左到右排列,开始天平两端平衡,从最左边依次取砝码放在天平较轻的一端,若天平平衡则放任意一端,求证最后天平仍平衡.
证明:容易得最轻的砝码质量为1,并设除1以外最轻的质量为a,可得至少有a个质量为1的砝码.
n=1,2时,显然.
假设n≤k时,命题成立.
当n=k+1时,若a为偶数,暂时去掉a,此时有k个砝码,总质量为2M=2k+2-a,符合归纳假设,
那么可以按要求分成两部分依次放置在天平上,此时最上方分别有s,t个质量为1的砝码,
不妨设0≤s≤t,(自然a≤s+t),除掉1以外的砝码质量为M-s,M-t,(显然M-s≥M-t)那么只需要把质量为a的,放在M-t上,并把上面的0.5a个1移动到另一边,如此完成了偶数a,n=k+1的递推要求.
当a为奇数时候,暂时去掉a,和一个1,余下类似.
因此按数学归纳法,命题成立.

TOP

回复 5# abababa


我看没啥问题,顶多是表达上不太清楚

首先$n=1$时显然
然后归纳,设$n=k$时成立,当$n=k+1$时,相当于在$n=k$基础上加了一个砝码,$2$质量

这时有两种方法
一是加了一个$1$质量砝码,另外$1$质量随便分配到之前$n+1$个砝码的任意一个上面
此时不管那个被加了$1$质量的砝码在哪边,只要把多出来的这个$1$质量砝码放到它对面就行了,肯定会平

二是直接加了一个$2$质量砝码,这时比较麻烦,要用到之前证明的至少有两个$1$质量砝码
考察这两个$1$质量砝码在之前的分布情况,要么它们放在同一边,要么放在两边
假设放同一边,则此时如果把它们同时拿下来,补上这个新的$2$质量砝码,天平仍然是平衡的,然后再把两个$1$质量砝码放两边,平衡了
假设放两边,把它们同时拿下来,天平仍然平衡,把$2$质量砝码随便放一边,再把这两个$1$质量砝码同时放另一边,还是平衡

TOP

回复 8# 战巡
我还是不太理解这个,就是在于多出的2质量,不是一定要作为一个砝码存在,而是可能被分配进前面几个砝码当中,比如前面的砝码本来是10,8,7,4,如果多出的2质量分配进了7里,那7就变成9了,这样就改变了原来砝码排放的顺序,假设10放左盘,原来从左到右拿的时候本来应该先将8放右盘,但是现在多了一个9,就先要将9放在右盘,虽然接下来仍然是将8放在右盘,但是要保证这个顺序还是需要证明才行,我觉得那个证明就是这里没有说清楚

TOP

本帖最后由 战巡 于 2014-11-26 09:12 编辑

回复 9# abababa


多出2质量的同时必须多1个砝码啊,要不然你还是k+1个砝码,而n=k+1时要求k+2个砝码

还有一种情况就是从某处(可以是从多个砝码)借了$p$质量过来,组成一个$p+1$或$p+2$的砝码
但无论如何最终还剩下两个1质量砝码时要么平衡,要么差2

TOP

7楼还有没漏洞?

TOP

回复 10# 战巡
但是要增加一个砝码,也有可能是后面,比如说后面还有一个6质量的砝码,可能是将2分配到7里变成9,然后将6拆成两个3,也能保证砝码的数量正好

就是觉得一旦将多出的质量向已经放在盘里的砝码分配,就有可能改变它们的质量顺序,原来本来放左盘的就有可能放在右盘里,我觉得要证明砝码放在左盘还是右盘在增加质量后不会改变左右,或者从某个砝码起,后面所有的砝码原来在左边的都去了右边,原来在右边的也都去了左边

TOP

回复 7# realnumber

我还是觉得顺序上有问题,因为$a$质量还没有上盘,那么盘上就不能有$1$质量,如果$a$质量上了盘,那么左右盘里的$1$的数量也会改变才对

TOP

有的,平衡后a是插入的,不是把a放最上,因为a是次轻的,一定在1下,在其它上面.

TOP

本帖最后由 abababa 于 2014-11-26 10:28 编辑

回复 14# realnumber
有点理解了,偶数的时候我觉得7楼的$0.5a$个$1$的说明有点问题,我按7楼的思路再写一下
假设$M-s$放左盘,$M-t$放右盘,现在把$a$放右盘,两盘质量差是$(M-t+a)-(M-s)=s-t+a$,总共还有$s+t$个$1$质量
必须证明$s+t\ge s-t+a$,这样才有足够的$1$来平衡天平
这就是证明$2t \ge a$,因为$a \le s+t,s \le t$,所以能证明
还必须证明$(s+t)-(s-t+a)=2t-a$是偶数,这样平衡后多出来的$1$才能平均分配到两个盘里再次平衡,当$a$时偶数时也成立

也有可能两盘质量差是$t-s-a$,就是$a$质量上盘后仍然是右盘轻
这时就要证明$s+t \ge t-s-a$和$(s+t)-(t-s-a)=2s-a$是偶数
就是必须证明$2s \ge -a$,这也成立
奇数的时候还没细看

TOP

出现a时,必定有a个1,又t≥s,t+s≥a,保证了t≥0.5a,
你说的7楼已经考虑进去了.

TOP

返回列表 回复 发帖