在数学趣题发现的,未有答案,陋笔觉得有趣,搬来和大家研究.

有个国王,他要求将大部分财宝放进一个仓库,锁上若干把锁,每把锁配若干把钥匙,然后将钥匙分给他的五位儿子,使得其中任意三人在一起可以打开仓库,任意两人打不开仓库,大臣之中有一位爱好数学的智者替国王想出了一种绝妙的方法,国王对他非常赏识,并按他的方法照办了.这时国王的两个女儿跑来了,要求得到和哥哥们一样的权利.智者说,这有何难,只需在原来基础上再造一些锁和钥匙分下去就行了.国王虽然也宠爱女儿,但他觉得女儿不能和儿子平起平坐,就决定给一半的权利.智者一时想不出来,陷入了沉思.智者回家后把难题告诉了他的妻子,他的妻子也是非常聪明的人,她说对这个问题可以用另外一个观点来看待,就会非常简单了,并且还可以保证她得到的方案是所有可行的方案中锁和钥匙数目都是最少的.她还说,大王子作为王储,应该得到其他王子两倍的权利,按照她的观点,对这种情形一样可以毫不费力的得到最佳的方案.
各位朋友,你们知道智者和他的妻子想出的分别是什么办法吗?

注:
1 对于最后一种情形,可以给大王子赋权2,其余王子赋权1,公主赋权0.5,权和大于一半的那些人在一起就可以打开仓库,否则打不开;
2 本题大部分为原创,若转载,请注明 ”命题人:liangzhaojian”.

如果允许所有拓扑形式：1X5至少需要7把锁，2+1X4+0.5X2要11把。
如果要求所有的锁都是并联的(bipartite)，前者需要10，后者23。

[此贴子已经被作者于2006-7-24 12:15:53编辑过]

陋笔听过拓扑这两个字,但不知为何物,
这题的答案也未知道,陋笔解法是19把锁(用最少的锁),
另外,陋笔也不明白这两句...............
1X5至少需要7把锁，2+1X4+0.5X2要11把。
前者需要10，后者23。
即是多少把锁?
呵呵.............................

晕，题目不止一个问题， OK? 姑且考虑全并联的情况好了。19如果对应2+1X4+0.5X2肯定是错误的，不信你写来看看，马上就能告诉你为什么。
呵呵.............................

2+1X4+0.5X2的答案
[username=liangzhaojian,LIKEME,天罪,儿死散巫酒,少林诺尘,divingbird]
找出7人中的组合，满足：1)权重不过半;2)加入其余任意一人则过半。每个组合必然至少对应一把锁打不开，任意两个组合可打开所有锁。这样的权重3组合7个，3.5组合16个。钥匙78支。感觉题目里“对这个问题可以用另外一个观点来看待,就会非常简单了”就是指全并联的情况。允许环环扣的情况比较复杂，目前最少是11把锁，27把钥匙。
跟陋笔没法沟通，看看对不对哈：）
[/username]

[此贴子已经被作者于2006-7-27 2:38:11编辑过]

5楼的留言,陋笔看不到,也不清楚..........
1X5至少需要7把锁，2+1X4+0.5X2要11把。
前者需要10，后者23。
.........是什么意思,即是多少把锁,
若果少于19把锁,那陋笔先把想到的蠢方法公开,
若果多于19把锁,那陋笔的方法是暂时最佳的了.
呵呵........................

公开吧，11比19小。
呵呵........................

想不出。
定员贴中间得是半角, ：（

那先看看陋笔的方法:
锁:ABCD=EF,GHIJKLM,NOPQ=RS
大子:ABCDHIJKLM
二子:AGHJLNOP
三子:BGHKMNOQ
四子:CGIJMNPQ
五子GIKLOPQ
公主:ER
公主:FS

从前也有类似的题目,丝丝雨丝的解法很特别,锁都互扣的,可以省不少锁,但陋笔始终不明,所以到现在都觉得方法未必是最佳.

这是密码学中秘密共享的问题，利用拉格朗日插值公式。