珍珠湾ART

标题: 将5块石头排序 [打印本页]

作者: 野菜花 时间: 2006-2-10 04:27
标题: 将5块石头排序

5块重量不同的石头A，B，C，D，E，能否通过问9个这样形式的对与否问题：

将它们按重量排序？

作者: 天人 时间: 2006-2-10 05:59
标题: 回复：将5块石头排序

应该不可以吧？这是个排列问题，9个问题相当于9种排列，而5块石头的全排列5！为120种。9个问题能确定120个问题中的唯一，这是不可能的事。不知对否？

作者: 流动的建筑 时间: 2006-2-10 12:00
标题: 可以

我觉得这道题难在数学表达上，下面介绍一下我用到的数学表达式：
- [A B...] 表示方括号中的 A,B,... 顺序未知；
- {AB BA,...} 表示花括号中的是可能的排列顺序，[A B]={AB BA}；
- AB... 表示已知顺序 A- ABC? 表示问的问题是 A- S₁,Q?,Yes/No->S₂ 表示通过问题 Q，答案 Yes/No，从状态 S₁ 到 S₂ 的转换；
- (S₁->S₂)=n 表示从状态 S₁ 到 S₂ 最多需要问 n 个问题；
- S=n 表示从初始状态到状态 S 最多需要问 n 个问题；

原始的问题就是：XXXXX = 9 ?

有了合适的表达方式，剩下的就是简单递推：
1. ABC[D E],CDE?->ABCXX, ==> (ABC[D E]->ABCXX) = 1;
2. ([A B]C[D E]->XXC[D E]) = 1, ==> ([A B]C[D E]->XXCXX) = 2;
3. (AB[CD E]->ABXXX) = 2;
4. (AB[C D E]->ABXXX) = (AB[C D E]->AB[XX E]) + (AB[XX E]->ABXXX) = 3;
5. XX[X X X]=6;
6. [X X]X[X X]=7;
7. XXXXX = XX[X X X] + (XX[X X X]->XXXXX) = [X X]X[X X] + （[X X]X[X X]->XXXXX) = 9.

细节我就不多说了。也许野MM有更好的解法。

本贴由[流动的建筑]最后编辑于：2006-2-10 13:34:27

作者: 野菜花 时间: 2006-2-10 19:03
标题: 好，现在有两种针锋相对的意见，大家都来看看到底可以还是不可以？[;)]

好，现在有两种针锋相对的意见，大家都来看看到底可以还是不可以？

作者: 野菜花 时间: 2006-2-10 19:08
标题: 回复：可以

你的思路和数学表达都很巧妙!

是否能解释一下第

5 或第6步是怎样得到的？

野姐姐又变成野

MM了，野姐姐, 野MM, 我也只好让你们随便叫了，谁让我自己取了这个名字。

作者: constant 时间: 2006-2-10 21:09
标题: 只能想出10次来。[:((]

只能想出10次来。

作者: 新用户 时间: 2006-2-10 21:18
标题: 这道题目应该这么出

5块重量不同的石头A，B，C，D，E，通过问个这样形式的对与否问题：

"Awww.ddhw.com

将它们按重量排序。

问题：至少需要问多少个这样的问题，能保证将它们按重量排序？

作者: 野菜花 时间: 2006-2-11 00:02
标题: 改得好，谢谢新新！[@};-][@};-][>:D<]

改得好，谢谢新新！

作者: 野菜花 时间: 2006-2-11 00:04
标题: 能否证明9次不够？[:)]

能否证明9次不够？

作者: constant 时间: 2006-2-11 01:07
标题: 闹半天野姐姐是逗我们玩儿的[:X]

不严格的证明：不管怎么比，前四次可能都是“不对”。每个不对最多可以排除20种组合，还剩40种，至少还要6次。

作者: 新用户 时间: 2006-2-11 01:09
标题: haha, 不好意思，我是来凑凑热闹 [:E]

我实在想不出怎么做，于是就想把题目弄得难一些

作者: 野菜花 时间: 2006-2-11 01:38
标题: 我怎么逗你们玩啦？[:O][:E]如果你愿意把10个问题写出来，不胜感谢！[@};-][@};-]

能否解释一下40个可能为什么5个问题不够？

作者: constant 时间: 2006-2-11 02:04
标题: 回复：我怎么逗你们玩啦？[:O][:E]如果你愿意把10个问题写出来，不胜感谢！[@};-][@};

比5次最多有32种答案，不能区分超过32种组合。

比10次：先选出3个数，5次可以完全确定顺序。（一共6种可能。）设为Awww.ddhw.com

作者: 野菜花 时间: 2006-2-11 02:05
标题: 如果我开始就这么写，Con 兄就不会对我发[:X]了[:((]

如果我开始就这么写，Con 兄就不会对我发

了

作者: 流动的建筑 时间: 2006-2-11 02:20
标题: 上当了！[:X]

以为9个是正解，就理所当然了。仔细验算了一下，没能找出小于10的解。

要证明至少需要10个问题，也许可以从信息论的角度来着手，可惜不是我熟悉的范围。

本来想改口叫菜花MM的。。。

作者: 野菜花 时间: 2006-2-11 03:03
标题: 息怒,息怒，俺给你们陪不是[:P][:P][:P]，谁叫你们一个个都这么厉害，

这是俄国2000年的奥赛题，昨天我译成中文后看看：“能否通过问9个这样形式的对与否问题，将它们按重量排序？”觉得可能会产生误解，想改成证明9个不可能，但想想你们一个都这么厉害，反正题目里是问“能否”, 就没改。www.ddhw.com

那个奥赛题里面有人给出答案，但并不是标准答案，今天看到你的这么好的思路和分析，我也怀疑原来那个答案是否正确，所以想看看你的细节, 绝不是故意的。www.ddhw.com

给你们陪笑脸吧www.ddhw.com

现在可以称我菜花姐姐了吧?

作者: 野菜花 时间: 2006-2-11 03:09
标题: 厉害！[:B][@};-]如果光要求你们证明"不可能"，不是也看不到这么好的10个问题了吗？[;)]

厉害！

如果光要求你们证明"不可能"，不是也看不到这么好的10个问题了吗？

作者: 流动的建筑 时间: 2006-2-11 03:18
标题: 菜花MM的笑脸能把三伏天的冰雪都化了！[@};-][>:D<]

菜花MM的笑脸能把三伏天的冰雪都化了！

作者: 野菜花 时间: 2006-2-11 03:39
标题: 笑脸有这么厉害吗? 以后就多笑笑[:D)][:D)][:D)]

笑脸有这么厉害吗? 以后就多笑笑

作者: 99-99 时间: 2006-2-11 07:26
标题: [:D)]还是这个笑的灿烂[:D)][:D)]

还是这个笑的灿烂

作者: 有空想想 时间: 2006-2-14 01:32
标题: 可以只用一半问句么，也就是只问 “A< B 对吗？”？

可以只用一半问句么，也就是只问 “A< B 对吗？”？

作者: 野菜花 时间: 2006-2-14 02:31
标题: 不行，如果可以，也不需要9个问题了。[:)]

不行，如果可以，也不需要9个问题了。

作者: 有空想想 时间: 2006-2-14 03:08
标题: 那我要是把另一半做为dummy 呢？虽问了，但并不理会。

那我要是把另一半做为dummy 呢？虽问了，但并不理会。

作者: 野菜花 时间: 2006-2-14 04:56
标题: 关键是要知道那作为dummy的一半是对的，如果不对，无论另一半怎样变动，回答都是"不对"

关键是要知道那作为dummy的一半是对的，如果不对，无论另一半怎样变动，回答都是"不对"

作者: huxlnn 时间: 2006-2-14 06:54
标题: 9个问题可以的

一、4个问题解决ABC的顺序

A<(B

-----n:(Bwww.ddhw.com

作者: 野菜花 时间: 2006-2-14 07:43
标题: 回复：9个问题可以的

你的第一点，不知道

(B的括号是什么意思

如果4个问题的回答都是 No，还有两个可能：B， C，所以4个问题还不一定能确定ABC的顺序。但5个问题是足够了，所以你给出了很好的10个问题解。一、4个问题解决ABC的顺序

A<(B

作者: huxlnn 时间: 2006-2-14 08:02
标题: 回复：回复：9个问题可以的

解释一下，A<(Bwww.ddhw.com

作者: 野菜花 时间: 2006-2-14 08:16
标题: 回复：回复：回复：9个问题可以的

A<(B并不一定能确定B如果这两个问题的回答都是 no ，有可能是 B，B还是对的.

作者: huxlnn 时间: 2006-2-14 08:26
标题: [:E]说的是，必须要5个问题才能确定ABC的顺序[:P]

[:E]说的是，必须要5个问题才能确定ABC的顺序[:P]

本贴由[huxlnn]最后编辑于：2006-2-14 0:30:30

作者: 野菜花 时间: 2006-2-14 08:35
标题: [@};-][:)]

作者: 野菜花 时间: 2006-2-14 08:43
标题: 回复：我觉得可以

你的第一个问题

位置1的石头在A，B里面对吗？

等于问了两个问题了

A？ B？

作者: 何么 时间: 2006-2-18 06:40
标题: 回复：将5块石头排序

不对.

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