Searching for a secret door

Question

You have reached the final stage of a game show, and now face an endless row of doors labelled $\ldots,-3,-2,-1,0,1, 2, 3,\ldots$, going from minus infinity to plus infinity. Your goal is to detect a secret door that has been chosen by the game host (and that is static and will not change throughout the game).

• The door with number $0$ is already open and forms the starting point of your search.

• In every further step, you first pay 1 Euro to the game host and then open the left or right neighbor of your current door. (In other words: if you open door $n$ in some round, then in the following round you must open door $n-1$ or door $n+1$.)

• Once you open the secret door, you may keep the money that is hidden behind it.

Prior to the game and before the game show host chooses the secret door, you have to specify to him the full (deterministic) strategy that you will follow for the entire evening. Only then the host will select his secret door (with number $x\ne0$) and will put an amount of $8.999|x|$ Euros behind it (where the multiplicator is $8.999=9-1/1000$ and hence slightly smaller than $9$).

Is there any deterministic strategy that guarantees you some positive profit in this game?

(Note: This puzzle was inspired by the puzzle One prize, infinitely many choices. In this other puzzle, the secret door moves in the same fashion as the searcher does move in my puzzle.)

Answer 1

I would like to thank dmg and user3294068 because their insights helped me find this answer.

dmg tried moving out twice as far in each step, whereas user3294068 tried moving w times as far in each step as the last step.

We will use a different strategy, but I am copying this logic from user3294068

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step.

What we will do is try to go as far as possible in each step before turning around, and we will see that this results in a solution that works.

Let's work through the first 2 numbers. I will start going in the + direction. The furthest I can go is dictated by the fact that when I get back to -1, that must still be profitable. Therefore I can go to +3 since it will be 7 steps when I get to -1.

Next, it must be profitable when I get back to +4. I have traveled 6 steps in the previous journey from 0 to 3 to 0, will need 4 to get from the origin to +4 later on, and must be less than 36 total. Therefore I can go to -12.

Proof: I will make use of 3 variables, $n$ The step number. $t_n$ The displacement from the origin of each step it is positive for odd n and negative for even n. $L_n= \sum_{i=1}^{n} 2 |t_i|$ The distance traveled by all steps to venture out and return to the origin.

We start out by defining the condition for choosing a step and staying profitable. Based on the above argument looking at a single step at a time, that condition is: $$L_n+|t_{n-1}|+1<9(|t_{n-1}|+1)$$algebra $$t_n<4t_{n-1}+4-\sum_{i=1}^{n-1}t_i$$Therefore $$t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$$

Now given $t_0=0$, this recursive formula leads to closed form expression $t_n=3*n*2^{n-1}$. Proof by induction at end.

So what we have done is constructed a path such that the least profitable point on that path is still profitable. We can see from the form of $t_n$ that it is monotonically increasing. Since we required this path to be profitable in its constrution and we move further from the origin than the previous n, This path can be continued indefinitely. For values above $L_n=1000$, the difference between $8.\bar{9}$ and 8.999 will mean there needs to be corrections, but I am too lazy to apply them.

Here are the steps I could calculate before my 32 bit int overflowed:

[3], [-12], [36], [-96], [240], [-576], [1344], [-3072], [6912], [-15360], [33792], [-73728], [159744], [-344064], [737280], [-1572864], [3342336], [-7077888], [14942208], [-31457280], [66060288], [-138412032], [289406976], [-603979776], [1258291200]

Proof by induction: $t_n=4t_{n-1}+3-\sum_{i=1}^{n-1}t_i$ and $t_0=0$ leads to $t_n=3*n*2^{n-1}$

1. Base case n = 1

$t_1=4*t_0+3-\sum_{i=1}^{0}t_i=3$ and $t_1=3*1*2^0=3$

2. Given $t_{n-1}$ prove $t_n$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (t_{n-1}-4t_{n-2}-3)$$

$$t_n = 4* 3 * (n-1) * 2 ^ {n-2} + 3 - (3*(n-1)*2^{n-1}-4*3*(n-2)*2^{n-3}-3)$$

Some algebra leads to the closed form expression.

So although this proves that it is possible to beat the dealer, it still might not be the ideal solution. I think there is a way to guarantee winning 3 or 4 euros by taking smaller initial steps and setting a margin of error so that the least profitable step in each series is still worth a couple euros.

Answer 2

My answer (if I have not made any mistakes).

Our best strategy is the "accelerating pendulum" one. We go in one direction with x doors and after that go in the other x to get to zero and 2*x. To get to the current maximum 2*z, we've made 4*z steps (2*z in that direction, 1*z to get back from the previous peak, and 1*z of all the previous moves). This means that if we win on the "peak" of the swing we'll get 9*z and thus 5*z (5/9 of the winnings). Our worst case is to have a peak at door number -2*y but the winnings are at 2*y. However even in that case we'll get 2*9*y and we will have moved a total of 4*y + 6*y = 10*y. Which is still 8*y (that is 4/9 of the winnings), which ain't that bad.

P.S.: The edit does not affect my solution at all.

Answer 3

Based on the answer by dmg, our plan is to pick a number $a$, start going to the right, and turn around the first time we reach door $x = (-a)^i$. Thus, for $a = 2$, we would turn around at $x = 1, -2, 4, -8, ...$.

To calculate how many steps it takes to reach a turnaround door, we assume a linear function $f(x) = r|x| - s$.

To go from door $x$ to door $a^2 x$, we go back $|x|$ doors to $0$, then $a|x|$ further, then turn around, $a|x|$ back to $0$, then on $a^2|x|$ more. This distance is $|x| + 2a|x| + a^2|x| = |x| (a+1)^2$.

But $$f(a^2x) - f(x) = r | a^2 x| - s - (r|x| - s) = r (a^2-1) |x|$$

So, $$ r (a^2-1) |x| =|x| (a+1)^2 $$

Dividing out $|x|$ and using $a^2-1 = (a+1)(a-1)$, we have: $$r = {a+1\over a-1}$$

Since we always turn around at $x = 1$, we have $s = r-1$. A bit of testing shows that our assumption of a linear function works, and thus for turnaround doors $x = (-a)^i$, the number of steps to reach that door is

$$f(x) = {a+1\over a-1} |x| - {2 \over a-1}$$

Thus, for $a = 2$, we have $r = 3$ and $s = 2$, so $f(x) = 3|x| -2$ (whenever $x = (-a)^i)$.

The worst case result is 1 door past a turn-around, because we almost reach it, go back, come forward again, and then 1 more step. This takes a total of $f(x) + (2a+2)|x| + 1$ steps.

Thus, the number of steps to reach the door just past turnaround door $x$ is: $$g(x) = f(x) + (2a+2)|x| + 1$$ $$ = \left({a+1\over a-1} + 2a + 2\right) |x| + {a-3\over a-1}$$ steps.

Setting $g(x) = w|x| + t$, we have $$w = {a+1\over a-1} + 2a + 2$$

For $a = 2$, we have $w = 9$, and $g(x) = 9|x| - 1$. But the money behind this door is only $8.999(|x|+1)$ euro, so if $9|x|-1 > 8.999(|x|+1)$, we lose. The first time this happens is for $x = 16384$. It takes 147455 steps to reach door 16385, and behind it is only 147448 euros.

Can we do better than $a = 2$? For $a = 3$, we have $r = 2$ (better), $s = 1$, and $w = 10$ (worse). Likewise, for $r = 4$, we have $r = 5/3$, $s=2/3$, and $w = 11.67$. Clearly increasing $a$ will not help.

The first derivative of $w$ in terms of $a$ is: $$w' = {-2 \over (a-1)^2} + 2$$

Solving $w' = 0$ gives $${-2 \over (a-1)^2} = -2$$ $$1 = (a-1)^2$$

Or $a = 0,2$. The second derivative is positive at $a = 2$, so that makes this a minimum. Thus, there is no solution where $w < 9$, and thus no solution to the problem.

Caveat: I have not considered non-exponential solutions. However, I expect the exponential solution to be the most efficient. Any other order could be approximated by an exponential with varying $a$, and thus either $a > 2$ or $a < 2$, and would therefore be suboptimal compared to an exponential with $a = 2$.