又是一年找工作的高峰期，各種各樣千奇百怪的智力題也在考驗(yàn)著學(xué)子們的智商，其中有些題目更是讓人腦細(xì)胞大量死亡。。。近來有同學(xué)問一道，帶有說謊的猜數(shù)字游戲，問“元芳，這事你怎么看？”，我這想一口鹽汽水噴死他。好了，言歸正傳。

問題描述：

A,B兩名玩家首先約定正整數(shù)N,然后A在心里想一個正整數(shù)x，其中x在1和N之間，B通過提問來猜出A心中所想的數(shù)字x。B提問的格式只有一種：先列出一些數(shù)字，然后問“x”是否在這些數(shù)字中(當(dāng)然B也可問：x是否在某個區(qū)間內(nèi))，B可以提問任意多次，A可回答“是”或者“否”。A可以偶爾撒謊的，但是A不能連續(xù)兩次撒謊。問：B是否可以通過詢問得到A心中的所想的數(shù)字，或者給出一個集合保證A所想數(shù)字x必定落在次區(qū)間內(nèi)，如果能請給出策略；如果不能請說明理由。

問題解答：

乍一看這個問題確實(shí)比較棘手，不知道從何開始，再次情況下，先求解簡單的特殊情況，然后逐步歸納得到一般地結(jié)論，是一個不錯的選擇。因而我們可以從最簡單的情況考慮，假設(shè)N=2，那么A所想的數(shù)字要么是1要么2.這種情況下如何呢？

由于A不可能連續(xù)說謊，所以如果對于同一個問題連續(xù)問兩次，A兩次給出相同的答案，那么我們是可以猜出答案的。比如：B連續(xù)兩次提問“x=2嗎？”，A如果給出答案“是是”，那么A兩次必然都說真話，所以x=2；如果A回答“否否”，那么兩次“否”也是真話，因而斷定x不等于2，x=1。

然而A給出不能的答案，B連續(xù)兩次提問”x=2嗎？“，A回答“是否”，我們只能斷定有一次說了假話，不能斷定哪一次說了假話，因而得不到任何有用的信息。在此基礎(chǔ)上，如果再問“x=1嗎？”，A可以根據(jù)上次說真話還是假話來給出回答，如果上次說的假話，那么只要保證這次說的是真話就可以了，但是我們并不知道他是否正在說真話，因而還是得不到有用的信息；如果上次說的真話，那么這次真話假話都可以，就可以隨便答，如果繼續(xù)逼問”x=1嗎？“，A上次說”是“，這次就說”否“，上次說”否“，這次就說”是“，我們是無論如何都不可能知道他什么時候在撒謊的。因而如果只有兩個值，那么B是不可能通過提問來猜出x的。

上面的過程可以通過下面這個簡單的例子看出，假設(shè)x=2。

(1)”x=2嗎？“ ?”是“ ?”x=2嗎？“ ?"否" ?”x=2嗎？“ ?”是“。。。(交替回答即可)。。。。”x=1嗎？“ ?”是/否“(上次說真話，這次隨便) ”x=1嗎？“ ?”否/是“

(2)"x=2嗎?" ? "否" ? ”x=2嗎？“ ?”是“ ?”x=2嗎？“ ?”否“。。。。(交替回答即可)。。。”x=1嗎？“ ?”否“(上次說假，這次必須說真) ?”x=1嗎？“ ?”是“

因?yàn)?和2是稱的，如果接著問”x=2嗎？“，只需要把上述(1)(2)中回答1和2的策略交換即可。

----------------------------------------------------------------------------我是分割線---------------------------------------------------------------------

N=2是不能斷定的，那么N=3情況會是怎么樣的呢？A只能想123中的某一個數(shù)。同樣根據(jù)A不能連續(xù)說謊兩次，我們可以對一個問題重復(fù)問2次以上，如果A的回答是相同的，那么必然是可以得到信息的。

例如連續(xù)問”x=3嗎？“，A的回答方式只可能是”是是“ ”否否“”是否“”否是“這四種情況。

(1)如果A回答”是是“，立刻斷定兩次都為真話，因而x=3.

(2)如果A回答”否否“，立刻斷定兩次都為真話，因而x不等于3，可排除3.

(3)如果A回答”否是“，繼續(xù)問”x=2嗎？” ?A只能回答“是/否”，分情況討論：(3a)如果A回答“是”。也就是“x=3嗎？”“是”“x=2嗎？”“是”。由于兩者中至少有一真，有不可能都是真(x不能即等于2也等于3)，所以兩者中必有一真一假。這樣可以得出x要么等于2要么等于3,因而可以排除1。(3b)如果A回答是“否”，也就是“x=3嗎？”“是”“x=2嗎？”“否”。這時如果x=2，那么可以得出他兩次都說假話。因而可以得出x不等于2，即可以排除2.

(4)如果A回答“是否”，繼續(xù)問“x=3嗎？”，如果回答“否”，按情況(2)處理，如果回答“是”，按情況(3)處理。

因而通過上面的提問策略我們總是可以排除其中的一個數(shù)，在大多數(shù)情況下不能得到更多的信息，除了情況(1)可直接得到答案。

----------------------------------------------------------------------------我是分割線-------------------------------------------------------------------------

現(xiàn)在我們開始考慮原始問題，如果N比較大怎么辦呢？我們可以把N分成三等分(不一定要求相等，盡量即可)，這樣把上面的策略中的123，換成集合123即可，比如“x在第三個集合中嗎？”，這樣的話，我們每次可以淘汰1/3的所有數(shù)字，直到最終剩下兩個數(shù)字，就歸結(jié)為第一個小問題，不可能得到確定的某一個數(shù)字。

本來討論到這里已經(jīng)結(jié)束了，但是有同學(xué)說，其實(shí)這個問題Matrix67已經(jīng)有討論過，并且還有更一般的結(jié)論，有興趣的同學(xué)請點(diǎn)擊這里。

博主python27對本博客文章享有版權(quán)，轉(zhuǎn)載請注明出處，對解題思路有任何建議，歡迎在評論中告知。

總結(jié)

以上是生活随笔為你收集整理的猜数字游戏python123_【趣味数学】可以说谎的猜数字游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。