(5) Bonus question. A prisoner escapes to the number line. He chooses some ne Z to...

Transcribed Image Text:

(5) Bonus question. A prisoner escapes to the number line. He chooses some ne Z to hide on the zeroth day. He also chooses some k Z, and every day hides at a number that is k higher than in the previous day. Hence on day te {0,1,2,...) he hides at n+k.t. Every day the detective can check one number and see if the prisoner is there. If he is there, she wins. Otherwise she can check again the next day. Formally, the game played between the prisoner and the detective is the following. The prisoner's strategy space is {(n,k) n,k Z), and the detec- tive's strategy space is the set of sequences (a0, a1, a2,...) in Z. The detective wins if at =n+k-t for some t. The prisoner wins otherwise. (a) 1 point. Prove that the detective has a winning strategy. (5) Bonus question. A prisoner escapes to the number line. He chooses some ne Z to hide on the zeroth day. He also chooses some k Z, and every day hides at a number that is k higher than in the previous day. Hence on day te {0,1,2,...) he hides at n+k.t. Every day the detective can check one number and see if the prisoner is there. If he is there, she wins. Otherwise she can check again the next day. Formally, the game played between the prisoner and the detective is the following. The prisoner's strategy space is {(n,k) n,k Z), and the detec- tive's strategy space is the set of sequences (a0, a1, a2,...) in Z. The detective wins if at =n+k-t for some t. The prisoner wins otherwise. (a) 1 point. Prove that the detective has a winning strategy.