十三間密室排成一排，小偷躲在其中一間，每過一天必轉移到相鄰的密室，轉移方向隨機。每天只能搜一間，問如何保證找到密室里的小偷？

12-05

十三間密室排成一排：1，2，3，4，5，6，7，8，9，10，11，12，13
小偷躲在其中一間
每天只能搜一間(如果小偷在裡面，一定可找到)
每過一天，小偷必轉移到相鄰的密室. 轉移方向隨機。
請問如何能保證找到密室里的小偷？

小偷一定是奇偶奇偶這樣變換房間的，所以可以做二分假設，第一天小偷要麼在偶數房，要麼在奇數房。
假設小偷第一天在偶數房的話，我們的策略就是第一天搜2號房、第二天搜3號房、第三天搜4號房。。。第11天搜12號房，小偷一定會在這個過程中被逼相遇。（因為你和小偷的距離要麼是0要麼是2的倍數）
如果這麼一輪都沒有遇到小偷的話，說明我們的假設是錯的，即小偷第一天應該是在奇數房的。這樣的話也不用擔心，說明第12天的時候小偷一定在偶數房了，這樣的話我們第12天再去2號房，第13天再去3號房。。。第22天去12號房，這樣第二輪的過程中小偷一定會被逼相遇。
所以最壞情況下22天可以保證遇到小偷。

對於n個房間(n&>2)，最優解是2n-4, 對於13間房，則是22次。搜查方案的一個實現的方式就是頭n-2步依次搜查2~n-1號房間，最後一次搜查完後，小偷可能在的房間只能是與n同奇偶的房間，接下n-2步是反過來搜索n-1~2號房間即可。

最優性證明如下：

對於某個房間 $iin {2..n-1}$ ，如果搜查方案中它從未在奇數天被搜查過，那麼可以構造出小偷的一個移動方法使他不被搜到：第一天呆在i房間，第二天前往i-1和i+1中當天不被搜查的房間，第三天回到i房間，……這樣小偷就一直不會被抓到。所以搜查方案必須要在某個奇數日期搜查房間i，同理，搜查方案也必須要在某個偶數日期搜查房間i。所以總搜索日期的下界就是2(n-2)=2n-4。前面的搜查方案說明了這個下界是可以達到的。

先試著找到可行解再嘗試找最優

首先從1號房間開始一次查看每個房間到13號時如果沒有見到小偷因為小偷每輪必定會移動則此時小偷只有可能在 2,4,6,8,10,12 這6個偶數編號的房間里否則在遍歷過程中已經被發現
然後再搜索一次13號房若沒有找到小偷則此時必在 1,3,5,7,9,11 這6個房間中與當前搜索的房間編號差為偶數
此時依此往回搜索因為不論小偷怎麼移動所在房間與當前搜索房間的編號差必定是偶數所以往回搜索的過程中一定會發現小偷

此解也是 N 個有限房間情形的通解：首先從一端遍歷所有房間如果找不到則此時小偷所處房間與當前搜索房間的編號差為奇數停留一輪編號差變為偶數並且確定在當前搜索房間的一側此時反向遍歷必能找到小偷

接下來再看如何找最優解
簡單想了一下第一次遍歷可以是從 2 號房間開始到 N-1 號房間然後在 N-1 處停留一輪再反向遍歷
共需 2(N-2) 步
暫時沒想到其它的優化方式歡迎評論與補充

數學歸納法

先考慮你和小偷的距離是偶數（跨1格、3、5....）的情況，假定房間總數是n：
n=3的情況，你往右移一格，第二天就抓到了
n=4的情況，你往右移一格，小偷要是往左走，直接抓到，要是往右走，會變成n=3抓到
n=5的情況，一樣的你往右走一格，小偷只有兩種可能，直接抓到，或者變成N=4了
以此類推，只要你和小偷初始距離是偶數，每天往右移一格，一定抓到

然後考慮你和小偷距離是奇數（比方說，就在你隔壁）的情況，仍然從最左邊每天往右抓
n=3的情況，一定抓不到^_^，但是當你抵達最右邊的時候，原地不動站一天，小偷必須動，形式變成偶數n=3的情況，一定抓到
n=4，一樣的，你從左往右走，跑到最右邊仍然抓不到，於是你可以強行在最右邊站一天，又變成偶數的情況了
以此類推。。。。。

所以，辦法就是，從最左邊開始，每天往右移一格，要是沒抓到，那麼在最右邊站一天不動，然後從右往左再抓一邊，一定能抓到，證畢

好幾個人都答出來了不過妹子關注了所以我也答一下 @VeranoXxz

策略就是 @王tosure 說的，從1到13找一次，找不到就再來一次，以下在他答案的回復里我已經說了一次……就相當於幫忙做個解釋吧。

每一次小偷隨機移動到相鄰房間，那麼每次奇偶性都改變，我從1到13的過程中也是每次奇偶性改變，如果第一次找1的時候小偷在偶數，那麼經過一輪1到13，第二次找1的時候相當於找第14次，小偷就在奇數。

所以在某一輪(第一或者第二輪)中我們和小偷所在房間號的奇偶性一直是一樣的，下面只考慮這一輪。

這時候我們和小偷的「距離」(小偷房間號-我找的房間號，不一定是正數)一定是偶數，而且每一次尋找，這個距離不變或者減小2(同向或者反向運動)，找1的時候距離是非負的，找13的時候距離是非正的，所以中間一定在某處取到0，這時候也就是抓到小偷的時候。

先從1搜到13，如果沒有，則再從1搜到13。這樣可保證一定會抓到小偷。

呵呵，你這題目問的應該是最短花多長時間找到或者規劃一種能找到的方案，這是一刀開放型測試題。因為僅僅按照能找到的標準，你一間間屋子按順序搜即可找到