珍珠湾ART

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

作者: husonghu 时间: 2008-7-1 08:47
标题: 好题大家做: 对底下yinyin"就楼下阳光MM的第二题砝码出个推广题"的猜想和求助

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,....直到13

用四个砝码(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会揭晓答案.

作者: idiot94 时间: 2008-7-1 09:37
标题: 试试3进制数？

试试3进制数？

作者: 呵呵呵呵 时间: 2008-7-2 08:08
标题: 回复：好题大家做: 对底下yinyin"就楼下阳光MM的第二题砝码出个推广题"的猜想和求助

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个砝码的组合实现

作者: husonghu 时间: 2008-7-2 18:03
标题: 嗯,很好[:-Q]只是"1至(3^(x+1)-1)/2区间所有的整数平分成3部分"欠准确

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

作者: husonghu 时间: 2008-7-2 18:12
标题: 能否再证明这里各砝码重量的取法(1,3,9,27,...)是唯一最佳的呢?

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

欢迎光临珍珠湾ART (http://zzwav.com/)