Re: [問題] 猜牌的遊戲

[andan (Everything)]

        七次的確也是最佳解了
        給個簡易版的證明概念
        假設六次可以
        表示我們要創作出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
推 ACGfans:我總覺得七次最少怪怪的... 沒辦法用問問題的技巧來改善嗎
→ ACGfans:目前的七個問題感覺都是相同性質的  能不能用不同性質切開
→ ACGfans:搞不好會有更少的解  舉個例子好了
→ ACGfans:重複兩次問他一個他不想被人知道的隱私問題
→ ACGfans:他為了不想讓人知道  就會選擇在這裡用掉說謊
→ ACGfans:剩下就只能說實話 13張牌用二元搜尋法只要四次
→ ACGfans:這樣就只要2+4=6 次就可以了 有沒有類似這樣更好的方法阿?
推 longlonglong:可以問說 你今天午餐已經吃了而且牌是xxx
→ longlonglong:每題都這樣問 就看他哪一題會說他沒午餐(還沒)吃
→ longlonglong:就知道他哪個問題說謊了 這樣會很賊嗎
推 kohttp:樓上不行,你用了[而且],這樣跟只問數字是一樣的
→ kohttp:他回答no,你還是不知道是真的數字錯還是說謊