魔方吧·中文魔方俱乐部

标题: 奇尺问题 [打印本页]

作者: 镜子580 时间: 2009-6-27 22:42:58 标题: 奇尺问题

奇尺问题

1、在9cm长的直尺上只标记3个刻度，即可把1-9之间的正整数全部测量出来。
2、在10cm长的直尺上只标记3个刻度，要全部测出从1到10的整数长度是不可能的。
3、在12cm长的直尺上如果只标记3个刻度，可以测出10种不同的长度。
4、如果要想在12cm长的直尺上测出1-12之间的全部长度，至少需要标记4个刻度。
5、在13cm长的直尺上只需要标记4个刻度，就可以测出1-13之间的全部长度。

（1=1，2=2；3=13-10；4=6-2；5=6-1；6=6；7=13-6；8=10-2；9=10-1；10=10；11=13-2；12=13-1；13=13）

根据以上命题原则，请各位贤人继续努力找出直尺长度36cm以内的用最少刻度测出直尺全部尺寸的标注刻度方法，每把尺子的刻度数不要超过8个。当然如果还有精力还可以继续寻找最佳刻度，只是尺子太长了手里不太好拿。

直尺13刻度标注示意图：

[ 本帖最后由镜子580 于 2009-6-28 20:46 编辑 ]

附件: image002.jpg (2009-6-27 22:42:58, 5.17 KB) / 下载次数 44
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTY5ODZ8ZGMzZDFlMTh8MTczMTczOTQ2M3wwfDA%3D

作者: q376997368 时间: 2009-6-27 23:13:10

有点创意，留名研究下

作者: 骰迷 时间: 2009-6-27 23:22:01

這個比較有趣，想起了法碼問題。佔板凳明天想。

作者: nick159951 时间: 2009-6-28 03:06:29

·················我只刻一个1

然后要量几就量几次·············

哈哈··········

作者: edmond-xym 时间: 2009-6-28 07:16:05

先说LZ的问的36cm的尺子，我觉得5个刻度就够了，分别为1、3、6、12、21
简单一些分析就是2可以用3-1来量出、4可以用3+1来量出、5可以用6-1来量出，有1、3、6最大可以量出到10、那么11可以用12-1来量出，以此类推。
如果这样符合LZ问题的标准的话，那么楼主的第2个和第4个命题就值得商榷了。
问题就在于LZ所说的奇尺问题，是否允许出现2=3-1，即2用3-1来量出的情况。不过根据楼主的第1个命题中的4只能用6-2来量出，可以看出这种减法是允许的，所以我觉得我的解法还是可行的。
有错误之处希望大家指出，希望进行更深入的讨论，谢谢。

作者: 骰迷 时间: 2009-6-28 15:35:51

樓上，減是沒問題，加就不能了。其實不是什麼加減，而是兩個刻劃之間的距離。

作者: kexin_xiao 时间: 2009-6-28 15:37:14

有点用三个固定容积桶倒水的意思

作者: yq_118 时间: 2009-6-28 15:44:36

我觉得只用标记一个1cm就可以测出所有长度。

作者: conwood 时间: 2009-6-28 16:23:19

这个东西似乎叫 Golomb ruler ，楼主可以去找找相关资料，已经有很多人研究过了。

http://en.wikipedia.org/wiki/Golomb_ruler

作者: 骰迷 时间: 2009-6-28 17:03:06

樓上，先別發出來，讓我們自己研究嘛
我初步得出結果為
刻劃數　尺子長度極限
0 1
1 3
2 6(3*2)
3 9(3*3)
4 12(4*3)
5 16(4*4)
6 20(5*4)
7 25(5*5)
8 30(5*6)
9 36(6*6)
好，發完這個，去看樓上的答案
------------------------我是無奈的分隔線----------------------
這個要求是PERFECT，與維基的答案有所差別。有待研究

[ 本帖最后由骰迷于 2009-6-28 17:29 编辑 ]

作者: 榕城之蓝 时间: 2009-6-28 17:06:44

对啊，其实只要有1就可以测出全部的长度，只是费事一点。

作者: superacid 时间: 2009-6-28 18:10:53

我在数学协作体做过36cm这道题，要8个刻度，只有两个解（互为镜像）

作者: 镜子580 时间: 2009-6-28 18:29:15 标题: 回复 9# 的帖子

非常感谢提供相关资料！不过还是自己能研究出来才有趣味，国外的研究总是领先我们一步，我辈还需努力啊，但愿有后起之秀，能人辈出！（说明一点：我是把原来的英寸改为cm了）

作者: 金眼睛 时间: 2009-6-28 18:46:36

恩，很有意思的题目，LZ的意思是长度必须一次量出，不可累加亦不可相减。

否则，可以利用1，2，4，8，16 …… 这个数列来解决所有整数尺寸的度量，这倒是有助于商品化，呵呵！

因为任何一个10进制数可以表示为2进制数，1的位置代表加，0的位置代表不加，就可以了。

比如6为110，110—421，也就是用4+2即可度量出来。

作者: 镜子580 时间: 2009-6-28 20:59:21

6楼的理解正确。我在题目中增加了一个举例，只能用减法。

作者: edmond-xym 时间: 2009-6-28 23:33:53

原帖由骰迷于 2009-6-28 15:35 发表
樓上，減是沒問題，加就不能了。其實不是什麼加減，而是兩個刻劃之間的距離。

那LZ的题目没有说清楚啊。没有了加法，反倒不难了。这种人为的规定只能使得题目不严谨。

[ 本帖最后由 edmond-xym 于 2009-6-28 23:44 编辑 ]

作者: 金眼睛 时间: 2009-6-29 22:18:32

我觉得提加减容易使人混淆，其实就是N以内的正整数长度均能利用刻度线一次量出。

可以有两种表述形式：
1：像LZ那样用刻度线表示，即要求，刻度线之间的差的绝对值能够覆盖1~N，是减的概念。
2：如果用各段的长度表示，则要求，各个连通段（说白了就是形成一团）的长度能够覆盖1~N，是加的概念。

给出36单位长度尺的分法：
1：用刻度表示
解1：0—1—3—6—13—20—27—31—35—36
解2：0—1—5—9—16—23—30—33—35—36
2：用各段长度表示
解1：1—2—3—7—7—7—4—4—1
解2：1—4—4—7—7—7—3—2—1 即是12楼所说的镜像情况。

我是用程序算的，算法不是很复杂，36以下的都可以很快得到的，期待高手介绍一下理论上的方法！o(∩_∩)o...

作者: 镜子580 时间: 2009-6-29 22:31:08

还是编程法算得又快又准，可惜没学会。不妨把标法都贴出来欣赏一下。

作者: 金眼睛 时间: 2009-7-2 23:28:24

画个图吧：）

附件: [1~36 均取第一解] 奇尺.JPG (2009-7-2 23:28:24, 30.49 KB) / 下载次数 54
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc1MzZ8MzJkMzE3NDV8MTczMTczOTQ2M3wwfDA%3D

作者: superacid 时间: 2009-7-3 08:38:31

这是一个NP问题，好像没有理论方法...

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)