猜數字，允許說謊

我敢肯定，你們都知道猜數字遊戲（這裏似乎有不少問題），愛麗絲認爲這是一個正整數，而鮑勃試圖猜測它。愛麗絲迴應說：「你明白了」，「低」，「高」。 Bob可以做的通常策略是進行二進制搜索，它可以猜測O（log n）猜測中的數字，其中n是Alice正在考慮的數字。猜數字，允許說謊

我一直想知道Alice允許說謊的變體。假設現在Alice允許說謊的次數恆定（在Alice和Bob之前都已知），但只有在響應「高」，「低」時才允許說謊（即，如果Bob正確猜測了該數字，她不得不承認這一點）。

Bob仍然有可能猜出O（log n）猜測中的數字嗎？

如果Bob允許其他疑問，例如「您到目前爲止撒謊了多少次？」會怎麼樣？（愛麗絲必須如實迴應）？ O（log n）查詢仍然有可能嗎？

編輯：如果謊言的數量也被允許爲O（logn），那麼額外的查詢是：你撒謊超過x次？愛麗絲被允許在他們身邊撒謊......

編輯道歉。

來源

2011-04-15 user127.0.0.1

如果允許的謊言的數量 - 比如說k - 是獨立於n而固定的，Bob可以簡單地問每個問題2k + 1次，並且用O（log（n））消失。 – 2011-04-15 18:00:36

只需按照「多少次你說謊」的每一個「標準」問題 - 並相應地切換答案。結果：同樣數量的問題彷彿愛麗絲從不撒謊。 – pmg 2011-04-15 18:01:58

我喜歡它。兩個直接的想法（1）根據概率映射空間是什麼（2）一個計劃試圖識別或不正確的答案是什麼樣的？ – 2011-04-15 18:02:53

運行通常的二進制搜索算法。要麼你得到答案，要麼你得到不一致（一個空的候選集）。如果你不一致，愛麗絲至少應該撒謊一次。重新開始二進制搜索。除非我錯過了一些東西，在O（k * log（n））步後，你會得到答案（加上她說謊的次數的下限）。你不需要先知道k。

來源

2011-04-15 18:06:49 foxcub

我認爲它仍然是O（log n），因爲你指定愛麗絲只能躺在一個固定的次數。這意味着她最多可以將Bob所做的猜測數量乘以常數。

想象一下，愛麗絲可以撒謊5次。現在，無論愛麗絲何時離開，她最終都不得不自責。鮑勃會注意到這一點，並可以開始他的二進制搜索。 Alice也被限制在O（log n）猜測之內，否則Bob會正確猜測數字，Alice將失去機會。因此，在最差的情況下，在愛麗絲謊言的五次，每次/剛剛/鮑勃得到答案時，她只是導致鮑勃的二進制搜索採取6 *（log n）猜測（五個謊言+一個正確的答案），這仍然是O（log n）。

來源

2011-04-15 18:07:20 Cephron

猜數字，允許說謊

回答

相關問題