作者andan (Everything)
看板puzzle
标题Re: [问题] 猜牌的游戏
时间Thu Oct 21 01:24:37 2010
七次的确也是最佳解了
给个简易版的证明概念
假设六次可以
表示我们要创作出6位元的0-1字串两两距离不能是0 or 2
算一下就会发现
0个1的共1组
1个1的最多只能放1组
2个1的最多只能有3组
3个1的最多也3组
4个1的最多也3组
5个1的最多1组
6个1的总共就1组
全部加起来才13组~
其中还有很多互斥的组, 比如选了0个1的就不能选2个1....etc
所以13组是不可能的!
因此七次的确是最佳解~
※ 引述《LPH66 (-858993460)》之铭言：
: 原题目恕删
: 这里提供一个问七次可以保证猜中的问法
: (同样限定恰说谎一次)
: 这七个问题是: 分别询问是否出现在下列集合当中
: {A,3,4,6,8,T,K}
: {A,2,5,6,8,J,Q}
: {8,9,T,J,Q,K}
: {A,2,4,7,9,T,Q}
: {4,5,6,7,Q,K}
: {2,3,6,7,T,J}
: {A,3,5,7,9,J,K}
: 这些问题有个特性:
: 对任何两个数字至少有三个问题两者恰出现其中之一
: 因此对任何一个数字恰错一题的答案对其他数字至少错两题
: 所以只要一个一个对答案对过去 恰错一题的数字就是它了
: ---
: 这题目和所谓的容错/纠正码有关
: 如果把在七个问题里回答是或否标记成 1 或 0 的话
: 这便是要我们寻找一个编码 使得它能够发现且修正单一 bit 的错误
: 上面给的答案使用的是 Hamming(7,4) 编码
: http://en.wikipedia.org/wiki/Hamming(7,4)
: 它使用 7 bits 来编码 4 bits 的资讯
: 使得当这 7 bits 中有不多於 1 bit 的错误时能够发现并修正它
: 这个题目范围是 1 ~ 13 正好是 4 bits 的资讯
: 所以套用这个编码就成了这个答案了
: (仔细看的话, 第 3,5,6,7 四个问题组合起来正好是各数字的二进位
: 也就是正好是 Hamming(7,4) 当中的资料位)
: 使用 Hamming 编码能够以 2^m-1 bits 来编码 2^m - m - 1 bits 的讯息
: 以发现且修正单一 bit 的错误
: 这类型的编码通常是在通讯理论上使用 减少通道杂讯影响传输正确性
: 其中一种很常用的编码 Reed-Solomon 编码 (比 Hamming 更强 它能修正更多 bit)
: 广泛使用在诸如 RAID 6, QR code, DVD/蓝光光碟, WiMAX 等地方
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.193.20.2
1F：推 ACGfans:我总觉得七次最少怪怪的... 没办法用问问题的技巧来改善吗 10/21 01:51
2F：→ ACGfans:目前的七个问题感觉都是相同性质的 能不能用不同性质切开 10/21 01:52
3F：→ ACGfans:搞不好会有更少的解 举个例子好了 10/21 01:54
4F：→ ACGfans:重复两次问他一个他不想被人知道的隐私问题 10/21 01:54
5F：→ ACGfans:他为了不想让人知道 就会选择在这里用掉说谎 10/21 01:55
6F：→ ACGfans:剩下就只能说实话 13张牌用二元搜寻法只要四次 10/21 01:56
7F：→ ACGfans:这样就只要2+4=6 次就可以了 有没有类似这样更好的方法阿? 10/21 01:56
8F：推 longlonglong:可以问说 你今天午餐已经吃了而且牌是xxx 10/31 12:42
9F：→ longlonglong:每题都这样问 就看他哪一题会说他没午餐(还没)吃 10/31 12:43
10F：→ longlonglong:就知道他哪个问题说谎了 这样会很贼吗 10/31 12:43
11F：推 kohttp:楼上不行,你用了[而且],这样跟只问数字是一样的 11/02 09:36
12F：→ kohttp:他回答no,你还是不知道是真的数字错还是说谎 11/02 09:37