一個面試時的益智問題 - 面試

※ 引述《bitcx (Luke)》之銘言：
: ※ [本文轉錄自 ask 看板 #1JIHi7MQ ]
: 作者: O0l10 (七) 看板: ask
: 標題: [請問] 一個益智問題
: 時間: Sat Apr 12 18:52:52 2014
: 在地球上的某地，住著一個富翁以及他的僕人。
: 這個富翁非常的有錢，但是自從失明後疑心病就變的非常的重。
: 有一天這個富翁家裡的燈壞了，
: 請問這個僕人該如何向富翁說明家裡的燈真的壞了，需要花錢修理呢！
: GOOGLE也不知道怎麼辦......
這是邏輯上可解的數學問題

有興趣者請google "zero knowledge proofs"

簡單講就是舉辦一場單盲實驗

請僕人另外準備同款示但正常的燈
還有外形相同的A盒子與B盒子

由富翁將正常的燈和(宣稱)壞掉的燈隨機裝入AB盒子
(只有富翁自己知道哪個燈裝在哪個盒子)

然後找100個鄉民來

一次一人 隨機請鄉民回答下面其中一個問題：
1. A盒子內的燈是正常的還是壞的？
2. B盒子內的燈是正常的還是壞的？

如果裝正常燈泡的盒子 鄉民都回答正常
而且裝壞掉燈泡的盒子 鄉民也都回答損壞

那就可以相信宣稱壞掉的燈泡的確壞了

就算僕人真的存心要騙富翁而跟鄉民勾結

想把那顆好的燈泡說成壞的

可是鄉民無法分辨富翁拿給他的燈泡是本來就是好的那顆 還是宣稱壞的那顆

要是說謊有一半的機率會被抓包

這樣有1-(0.5)^100的信心度可以辨認燈泡是否真的壞了

--