将5块石头排序

野菜花 · 发表于 2006-2-10 04:27:06

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

"A

将它们按重量排序？

天人 · 发表于 2006-2-10 05:59:27

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

流动的建筑 · 发表于 2006-2-10 12:00:31

我觉得这道题难在数学表达上，下面介绍一下我用到的数学表达式：
- [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:46

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

野菜花 · 发表于 2006-2-10 19:08:13

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

是否能解释一下第

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

野姐姐又变成野

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

constant · 发表于 2006-2-10 21:09:13

只能想出10次来。

新用户 · 发表于 2006-2-10 21:18:14

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

"Awww.ddhw.com

将它们按重量排序。

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

野菜花 · 发表于 2006-2-11 00:02:00

改得好，谢谢新新！

野菜花 · 发表于 2006-2-11 00:04:08

能否证明9次不够？

constant · 发表于 2006-2-11 01:07:28

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

新用户 · 发表于 2006-2-11 01:09:22

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

野菜花 · 发表于 2006-2-11 01:38:31

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

constant · 发表于 2006-2-11 02:04:46

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

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

野菜花 · 发表于 2006-2-11 02:05:43

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

了

流动的建筑 · 发表于 2006-2-11 02:20:28

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

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

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

野菜花 · 发表于 2006-2-11 03:03:39

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

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

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

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

野菜花 · 发表于 2006-2-11 03:09:18

厉害！

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

流动的建筑 · 发表于 2006-2-11 03:18:06

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

野菜花 · 发表于 2006-2-11 03:39:17

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

99-99 · 发表于 2006-2-11 07:26:22

还是这个笑的灿烂

有空想想 · 发表于 2006-2-14 01:32:38

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

野菜花 · 发表于 2006-2-14 02:31:38

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

有空想想 · 发表于 2006-2-14 03:08:46

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

野菜花 · 发表于 2006-2-14 04:56:45

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

huxlnn · 发表于 2006-2-14 06:54:40

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

A<(B

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

野菜花 · 发表于 2006-2-14 07:43:19

你的第一点，不知道

(B的括号是什么意思

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

A<(B

huxlnn · 发表于 2006-2-14 08:02:33

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

野菜花 · 发表于 2006-2-14 08:16:36

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

huxlnn · 发表于 2006-2-14 08:26:08

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

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

野菜花 · 发表于 2006-2-14 08:35:32

野菜花 · 发表于 2006-2-14 08:43:01

你的第一个问题

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

等于问了两个问题了

A？ B？

何么 · 发表于 2006-2-18 06:40:28

不对.

		自动登录	找回密码
密码			立即注册

动态微博

将5块石头排序

回复：将5块石头排序

可以

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

回复：可以

只能想出10次来。[:((]

这道题目应该这么出

改得好，谢谢新新！[@};-][@};-][>:D<]

能否证明9次不够？[:)]

闹半天野姐姐是逗我们玩儿的[:X]

haha, 不好意思，我是来凑凑热闹 [:E]

我怎么逗你们玩啦？[:O][:E]如果你愿意把10个问题写出来，不胜感谢！[@};-][@};-]

回复：我怎么逗你们玩啦？[:O][:E]如果你愿意把10个问题写出来，不胜感谢！[@};-][@};

如果我开始就这么写，Con 兄就不会对我发[:X]了[:((]

上当了！[:X]

息怒,息怒，俺给你们陪不是[:P][:P][:P]，谁叫你们一个个都这么厉害，

厉害！[:B][@};-]如果光要求你们证明"不可能"，不是也看不到这么好的10个问题了吗？[;)]

菜花MM的笑脸能把三伏天的冰雪都化了！[@};-][>:D<]

笑脸有这么厉害吗? 以后就多笑笑[:D)][:D)][:D)]

[:D)]还是这个笑的灿烂[:D)][:D)]

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

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

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

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

9个问题可以的

回复：9个问题可以的

回复：回复：9个问题可以的

回复：回复：回复：9个问题可以的

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

[@};-][:)]

回复：我觉得可以

回复：将5块石头排序