好题大家做: 对底下yinyin"就楼下阳光MM的第二题砝码出个推广题"的猜想和求助

husonghu

yinyin原题:  用n个砝码，最多能用来称出多少个从1开始相继的整数克？

http://www.ddhw.com/lista.aspx?topic_id=9&msg_id=8183&page=1

 

从答阳光MM的砝码题中可猜想:

 

用两个砝码(1,3), 可称1,2,3,4

用三个砝码(1,3,9), 可称1,2,3,4,5,6,....直到13www.ddhw.com

用四个砝码(1,3,9,27), 可称1,2,3,4,5,6,....直到40

.....................

不难推广, 本题中, 砝码质量1,3,9,27,...构成公比为3的等比数列, 故用n个砝码可称1,2,3,4,5,6,....直到(3^n-1)/2区间所有的整数克.

(其中(3^n-1)/2是该数列的前n项之和. 所以本猜想等同于说: 等比数列1,3,9,27,...3^(n-1), 前n项各项的所有的可能组合的代数和取遍1到(3^n-1)/2各整数).

 

但在没证明前, 这只是猜想.  现在的问题是如何证明. 我水平低, 请各位踊跃. 数学归纳法应该可行, 但好象不容易. 不知有否其它方法. 当然最后yinyin会揭晓答案. 

 

 

www.ddhw.com

 

husonghu

  能否再证明这里各砝码重量的取法(1,3,9,27,...)是唯一最佳的呢?

husonghu

1至(3^（x+1）-1)/2区间所有的整数不能正好平分成3部分, 在   你说的区间b:(3^x+1)/2至3^x-1 和 区间c:3^x+1至(3^(x+1)-1)/2 之间 有 3^x, 正好是x+1号发码的重量, 不用加也不用减其它法码. 我原来以为用归纳法不易, 被你一指点就简单了. 多谢了.  www.ddhw.com     本贴由[husonghu]最后编辑于：2008-7-2 10:8:32

呵呵呵呵

1。当n=2时，显然成立。 2。把砝码从小到大编号。假设n=x时结论成立，即1到x号可以组合1至(3^x-1)/2区间所有的整数克.则n=x+1时, 我们把1至(3^（x+1）-1)/2区间所有的整数平分成3部分： a.1至(3^x-1)/2区间, 可由1至x号砝码组合实现 b.(3^x+1)/2至3^x-1区间，可由x+1号砝码分别减去1至x个砝码的组合实现 c.3^x+1至(3^（x+1）-1)/2区间, 可由x+1号砝码分别加上1至x个砝码的组合实现

idiot94

  试试3进制数？