两道智力题，看看你有没有游戏设计的天赋？

kidolo

对于第一个问题我有新的解法。
首先设定这样一个规则：玩家可以在1到9里面随便选择3个数，然后规定最小的是剪刀，中间的是石头，最大的是布。然后各自在心里面想要选那3个数（比如2、6、7），然后对应自己的选择（剪刀就是2，石头就是6，布就是7，如果我选布，就是7了）。然后互相进行运算，比如A说：“你把你的数加上3。”接着B又说：“你把你的数乘以2。”（最好不要有减或者除，怕会出现0和小数。加和乘的数也控制在1到3就好）然后互相运算两三次就够了（千万不要弄得太复杂了），然后互相说出开始选的3个数以及最后的答案（比如A说：“2、6、7，答案是42。”B接着说“3、4、9，答案是25。”）最后倒推就可以知道对方出什么了。

其实游戏设计就是这样，不要往复杂的方向想，越简单越好。（我觉得我这个方法还是有点复杂，回头再想想有没有再简单的。）

webcraft

原帖由离非于 2008-3-13 19:04 发表
第一题的话可以这样，每人设计一套算法（对给定初始值有唯一结果），相互加密后再告知结果，这就不必非常准时。
具体方法：
x、y分别是A、B的答案，A(i)为A的算法，B(i)为B的算法。则两人分别做的计算为：
A：
( ...

你这个方法的问题在于如果我让对方先说出他的算法，我有可能快速找出一中“必胜”算法。
比如对如果石头，剪子，布分别是0，1，2。对方先说出了他的算法和他出的值，比如0，那么我希望我出的是2。也就是我要迅速找出一个算法，满足B(2)=我告诉对方那个的值，B(A(0))=我的终值。要找出这样一个B其实是很简单的，也有很多这样的B。比如可设B的形式是Ax+B的形式，用上面的两个等式解出A,B即可。

webcraft

原帖由 kidolo 于 2008-3-13 21:29 发表
对于第一个问题我有新的解法。
首先设定这样一个规则：玩家可以在1到9里面随便选择3个数，然后规定最小的是剪刀，中间的是石头，最大的是布。然后各自在心里面想要选那3个数（比如2、6、7），然后对应自己的选择（剪 ...

方法有点意思，思路的方向有些对了，可还不够简单。
嗯，不对，你的方法有严重问题：如果我知道对方是（2，6，7，12），我马上能推算出对方的结果。那么我可以永远让自己出5，并且把自己的初始序列在以下三种情况下对应选择：3,4,5; 4,5,6; 5,6,7；这样我必胜。

[ 本帖最后由 webcraft 于 2008-3-14 09:46 编辑 ]

kidolo

原帖由 webcraft 于 2008-3-14 09:39 发表

方法有点意思，思路的方向有些对了，可还不够简单。
嗯，不对，你的方法有严重问题：如果我知道对方是（2，6，7，12），我马上能推算出对方的结果。那么我可以永远让自己出5，并且把自己的初始序列在以下三种情况 ...

对方未必每一次都是2、6、7啊，如果他下一次是1、3、6，再下一次是3、4、8呢，那你怎么猜。

webcraft

看大家无花八门的回答真的是饶有趣味的事，那么我来说说答案吧。
先说第一题，第一题要解决的问题是怎样传送一个信息，它是被加密的，而且可以被验证而且不能被篡改。那么书上的答案是（记得不是很准确，大致如此）：
“我现在告诉你一个数，它是两个很大的素数的乘积，把这两个素数的最高位数（用个位数不好）相加除以三的余数就是我要出的结果。这个数是.....。那么你可以告诉我你出什么了。“😃

从这个答案可以看出，不需要对双方的结果加密，只要加密一方就可以了。而且加密的算法必须是公开的，这样才能被验证。而且只要是不能被很快破译的就可以了。其实有些朋友的答案已经接近了，可惜还不够简洁。我有以下一些比较简洁的方法：
"我出的结果是我母亲生日日期除以三的结果“，事后可以传真身份证验证。
”我出的结果是今天xxxxx股票收盘价的分位数除以三",哈，这个要确保对方不太关心股票的。
“我出的结果是今天湖人和火箭队比赛结果双方得分之和除以三“，如果不放心，可以多加几场比赛的结果。

总之，只要有一个客观信息，且对方不太容易获得的，都可以用来作为你的”加密“算法。

webcraft

再说第二题，这个kidolo已经给出了书上的答案，确实是很简单的，但很多人就是想不到。
当然YOYU的"小黑屋"方法未尝不可，看的出YOYU肯定不是学理科的人。所以有些题目是需要一些发散思维去考虑的，不要想复杂，也不要太专注于题目本身。

chariot6

呵呵,果然够美国人的.....第2个存在破绽啊,第一个人只要私底下问问第3个人就知道第2个人的工资了.还是YOYU的比较好,比较符合东方人思想.

当然在美国是不太可能的,不过在中国,第3个人是很大可能会如实说的.YOYU最满塞

离非

讨论的真热烈呀，呵呵。
web你可以能没看清楚，我的意思是双方在（猜拳）结果揭晓之前都不知道对方的算法，只是各自做两次加密运算。
在x、y、A(x)、B(y)、M、N都揭晓以后，如果对对方的算法有质疑，可以公布算法互相验证。
相对于你的“书上的答案”而言，只要A(i)、B(i)足够复杂，“迅速找出四个数的逻辑关系”不会比“迅速分解大素数”运算量低。
而下面简洁的方法其实是不成立的，首先它实际上已经借助了第三方的信息，我想这不符合设计题目的目的，其次如果在网络的帮助下，很多信息都是可以瞬间查到的，假如这是双方的一个高额赌博，就只能靠严密的逻辑来保证公平性。
我想这个题目的意义在于寻找一个“不依赖第三方信息解决二人信用问题”的答案，我现在只能用提升运算复杂度的方法来解决，还没想到一个完美的逻辑。

irstar

原帖由 chariot6 于 2008-3-14 10:54 发表
呵呵,果然够美国人的.....第2个存在破绽啊,第一个人只要私底下问问第3个人就知道第2个人的工资了.还是YOYU的比较好,比较符合东方人思想.

我的最好！全程随机数参与运算，最后神奇地算出了一个将随机因素控制在阈值内的结果！

mudmdw620911

你们都是数学达人…………

我是数学白痴…………

路过

kidolo

我只对了第二题，50分（或者更低），看来游戏设计要重修了。至于第一题，我老想着两方加密，其实只要一方加密就可以了，转不过来:Q

webcraft

原帖由 chariot6 于 2008-3-14 10:54 发表
呵呵,果然够美国人的.....第2个存在破绽啊,第一个人只要私底下问问第3个人就知道第2个人的工资了.还是YOYU的比较好,比较符合东方人思想.

当然在美国是不太可能的,不过在中国,第3个人是很大可能会如实说的.YOYU最满 ...

你说的不错，第二个问题中，只要两个人串通，就可以知道第三个人的工资。但其实数学家早就考虑过这种情况了，只要对这一方法稍加改进，就可以做到：如果有N个人，只有N-1个人串通，才可能知道余下一人的工资，其他情况下，工资仍旧是保密的。

mtgfan

很有意思的问题，我的解决方案：

双方都花一定时间在本地编辑好电话留言，然后立刻打对方的电话，只有一台电话的话需要轮流有点小问题，2台电话就基本完美了，应该来不及改留言的。留言可以设计成“石头+一段固定长度固定内容的话”这样在短时间内改就有难度了，因为来不及加上后面的内容。一台电话的情况下，听的时间限制可以比较短，只要听到“石头”就可以挂断，马上换对方打过来。
我觉得YuYu的第一个方案就可以，换成代币即可。

[ 本帖最后由 mtgfan 于 2008-3-14 14:40 编辑 ]

webcraft

如果要考虑“不依赖第三方信息解决二人信用问题"，那么目前只有大素数不能快速分解是一个可以简便利用的手段，你若能找到其他手段，那么绝对是密码学一大突破。😛

mtgfan

觉得我的答案怎样啊？：）

YOYU

原帖由 webcraft 于 2008-3-14 10:19 发表
当然YOYU的"小黑屋"方法未尝不可，看的出YOYU肯定不是学理科的人。所以有些题目是需要一些发散思维去考虑的，不要想复杂，也不 ...

我是学理科的
我是艺术院校工科女……

其实关于第一个问题我还有一个想法……还是不说好了

zeranix

原帖由 webcraft 于 2008-3-14 10:16 发表
看大家无花八门的回答真的是饶有趣味的事，那么我来说说答案吧。
先说第一题，第一题要解决的问题是怎样传送一个信息，它是被加密的，而且可以被验证而且不能被篡改。那么书上的答案是（记得不是很准确，大致如此） ...

两个大素数乘积……这不就是那个RSA还是什么加密算法的原理么……

irstar

原帖由 zeranix 于 2008-3-14 16:10 发表

两个大素数乘积……这不就是那个RSA还是什么加密算法的原理么……

对！最常见的公钥加密算法 RSA

ienzhangyan

呵呵，这是安全协议方面的经典问题了，其实目前解决方法远不止大素数一种，离散对数和椭圆曲线都是常用的手段

原帖由 webcraft 于 2008-3-14 13:59 发表
如果要考虑“不依赖第三方信息解决二人信用问题"，那么目前只有大素数不能快速分解是一个可以简便利用的手段，你若能找到其他手段，那么绝对是密码学一大突破。😛

webcraft

离散对数/椭圆曲线?太深了..