One prize, infinitely many choices

Question

Having reached the final stage of a game show, you face an endless row of doors labelled $1$, $2$, $3$, ... The game show host has selected a whole dollar amount, and has put this exact amount as a prize behind the door labelled with that dollar figure.

You have absolutely no clue what prize is for grabs, and you have to continue opening doors until you hit upon the prize. But be aware: each door you open costs you a dime ($0.10), payable to the game show host.

If the opening of a door reveals the prize, it's yours and the game ends. If a door being opened reveals an empty room, the door gets closed again, and the game show host secretly moves the prize one door up (from behind a door labeled $n$ to a door labeled $n+1$), or one door down (from a door labeled $n$ to a door labeled $n-1$). Note: following each closing of a door the prize must move, but it's the game show host's sole decision which move to make.

You want to leave this game with a profit, so it is of the essence to find the prize following a limited number of door openings. However, the game show host will do his utmost to reduce the game show cost. And to make things worse: prior to the game and before the game show host decided on the dollar amount for the prize, you have to specify to him the full strategy that you will follow.

What will this strategy be?

Answer 1

Solution for the variant with 1 cent per door

Here is a deterministic strategy for the variant where we only have to pay 1 cent per opened door (but that does not work if we have to pay 1 dime as in the actual problem statement.)

The Strategy:

Here is a deterministic strategy for this problem. It goes through many phases until it finds the desired door. During the $p$-th phase ($p=0,1,2,\ldots$), we open all the doors with numbers between $1$ and $3^p$ in decreasing order.

Intuitively, in an even phase ($p=0,2,\ldots$) we assume that the good door (in the very beginning) started off at an odd position; in an odd phase ($p=1,3,\ldots$) we assume that the good door started off in an even position. Since every phase opens an odd number of doors, the odd / even phases are correctly synchronized with the movement of the good door.

First observations:

1. In the $p$-th phase, we open exactly $3^p$ doors. The total number of doors opened during the first $p$ phases is $N_p=1+3+3^2+\cdots+3^p<3^{p+1}/2$.

2. If at the beginning of an odd phase $p$, the current position of the good door is odd and less or equal to $3^p$, then I will catch the door for sure during this phase. (I am always opening a door with the same parity as the current good door. Hence the door can not pass me by. I will corner and eventually catch it at latest at position 1.)

3. If at the beginning of an even phase $p$, the current position of the good door is odd and less or equal to $3^p$, then I will catch the door for sure during this phase.

Correctness:

Now suppose that the good door is initially at some position $g$, and let $x$ be the (unique) integer with $3^{x-1}<g\le3^x$. By statement (1), after the first $p$ phases, the good door has moved at most $N_p<3^{p+1}/2$ places to the right.

4. At the beginning of either phase $x+1$ or $x+2$, the current position of the good door must be odd.

5. At the beginning of phase $x+1$, the current position of the good door is at most $g+N_x\le 3^x+3^{x+1}/2<3^{x+1}$.

6. At the beginning of phase $x+2$, the current position of the good door is at most $g+N_{x+1}\le 3^x+3^{x+2}/2<3^{x+2}$.

Statements (4), (5), (6) together with the first observations imply that I will catch the good door for sure before the end of phase $x+2$. Hence the strategy is correct and indeed finds the desired door.

Profit analysis:

By statement (1) above, the total cost of the first $x+2$ phases is at most $N_{x+2}<3^{x+3}/2$ cent. My income is $g>3^{x-1}$ dollar, that is, at least $100\cdot3^{x-1}$ cent. As the income is larger than my expenses, I always will make profit.

Answer 2

Edit: added two more options at the end, including one that wins \$1 on the specific assumption that you can't actually lose money.

---

The best you can possibly do is win \$1. If your strategy will do better than that, the host will simply choose \$1 as the prize. So this is always going to be a lot of work for not much; but I don't think you can guarantee a profit at all.

Others have observed that if you choose a door that's higher than a given prize (wherever that prize happens to be) you can then capture it by choosing the next lowest door all the way down to 2. Also, you can only do this with even prizes or odd prizes on any given run.

Also, no matter what strategy you produce that captures a finite set of prizes, the host can choose a higher prize. So your strategy must be able to handle infinitely high prizes; but it must get the lower prizes first or you will lose money on them.

I'm going to assume that you've worked out the intricacies of small integers for everything below some large number, so that I can ignore +1 terms etc (for example, $n \approx n+1 \approx n+2$).

Let's assume that you have a strategy that covers everything up to n, at a cost of no more than cn doors. Now you sweep out every prize from kn down, where k > 1. After cn doors, the kn'th prize will have been moved up to $kn + cn$, so it will take you $kn + cn$ doors to do that sweep, so now your total door count is $kn + 2cn$.

We need $kn + 2cn < c(kn)$, to preserve our cost limit. That means $k + 2c < ck$. In this case we need c to be no more than 10 (10 doors costs a dollar). We can find k that satisfies this: $k + 20 < 10k$ means $k < \frac{20}{9}$. But the smallest k can possibly be is given by $k(c - 1) > 2c$, ie $k > \frac{2c}{c-1}$. So k must be greater than 2, which definitely rules out any kind of linear search (we must at least double our door count on every run). We must climb exponentially, but we can definitely catch any given prize. Similarly, $c > \frac{k}{k-2}$, so c must exceed 1 and c and k can't both be small.

But what about the cost? Our host will choose the very worst prize for our strategy, which in this case is a number just above n, and with the wrong polarity. Thus, we will sweep prizes between $n$ and $kn$, and then between $kn$ and $k^2n$, just to get a prize of $n$. From $n$ at a cost of $cn$, we go to $kn$ at a cost of $kn + 2cn$; and from there we go to $k^n$ at a cost of $k^2n + 2kn + 4cn$, and this gets us a prize of n at a cost of $\frac{k^2n + 2kn + 4cn}{10}$ dollars.

To make $\frac{k^2n + 2kn + 4cn}{10} < n$, we will need $k^2 + 2k + 4c < 10$. In fact if we substitute $c = \frac{k}{k-2}$ into $k^2 + 2k + 4c$, take the derivative and set that to zero, we find the minimum value of $k = c = 3$, which means $k^2 + 2k + 4c = 27$, which is clearly more than 10.

Our host, therefore, can set an arbitrarily high value for the prize and reap a handsome profit. To stop him, we need to negotiate a price of $\frac{100}{27} = 3.7$ cents or better; or else call in sick.

---

This is the best you can do deterministically. If you can include a random number source (say, a good strong hot cup of tea), then you can reduce your losses for a given prize because the host can't choose the optimal number in a range. What you do is randomly vary the value of k around 3. This increases your cost and takes a while to make the ranges completely random, but I'm going to ignore those effects by waving my hands and chanting "for large n".

Now the host can't get "just above your last guess", and more importantly can't guarantee to get the wrong polarity. So we will sweep prizes between $n$ and $kn$, and then between $kn$ and $k^2n$, and get a prize averaged between $\frac{kn-n}{2}$ and $\frac{k^2n-kn}{2}$, depending on which way the polarity went.

That's nice, but it still doesn't reach profitability (it does make the calculations uglier, though). To get a profit, you need another assumption.

---

Now I'm going to assume that since this is a game show, they can't charge you money. So if you have a strategy that either makes \$x or loses \$y, you walk away from any potential losses and get an expected value of $\frac{x}{2}$.

Therefore, we will use one of the opening sequences already established - door 1, door 3, then door 2. This guarantees that a \$1 prize is found immediately, and a \$2 prize is found at a cost of \$0.20 for a payoff of \$1.80.

Now we will flip a coin. Heads, we assume the prize is even, tails we assume it's heads. We then proceed with c = 3, k = 3. In general this ensures we cover everything up to $n$ at a cost of at most $3n$ doors; at each next step we cover everything up to $3n$ at a cost of $3n + 3n + 3n = 9n$ doors, and we get a prize of \$n for a profit of $n - \frac{9}{10}n = 0.1n$. If our coin-flip failed, we get nothing, so the expected value is $0.05n$. For any large n this is more than \$1, so the host won't choose these.

So we start having covered 1 and 2 at a cost of 3 doors. If we have correctly chosen even numbers, the sequence looks like this:

Covered  Cost (doors)  Smallest door in range  Profit (if the door is found here)
   2          3
   4          9                4                 3.10
  12         29                6                 3.10
  36         93               14                 4.70
 108        293               38                 8.70
 .....and we're well over 20.

And if we've correctly chosen even numbers, the sequence looks like this:

Covered  Cost (doors)  Smallest door in range  Profit (if the door is found here)
   2          3
   3          8                3                 2.20
   9         24                5                 2.60
  27         78               11                 3.20
  81        236               29                 5.40
....and we're well over 20.

Expected profit values have to be divided by 2 to cover failed coin-flips, but these are all greater than \$2, so the expected profits will always be greater than \$1.

Therefore, we announce this strategy to the host, he chooses a prize of $1 which we find immediately, and showers of confetti are unleashed.

Answer 3

Given that the only constraint on the host is that very every wrong guess n is either incremented or decremented, there are three things which conspire to make it very difficult for you to win this game:

it's the game show host's sole decision which move to make.

and

the game show host will do his utmost to reduce the game show cost.

and

prior to the game and before the game show host decided on the dollar amount for the prize, you have to specify to him the full strategy that you will follow.

In fact, I would assert that you cannot win at all with any deterministic strategy. Any such strategy you pick, the host will know for either of his choices what your next move will be. And to reduce the game show cost the host will pick the route that minimizes the show's cost. The host can see every possible path, and find the one that will result in you never finding the number, or at the least, making it cost you more to find it than you get back.

For instance, if you simply pick 1, 2, 3, 4, etc. in order, then the host will pick a starting number n0, so that when you pick n, the prize $n0 is behind door n+1, and then he will decrement so you are looking in door n+1 when the prize is behind door n. The host has an unlimited number of choices even: in this case he could pick 2 (you pick 1, he moves 2 to 1 after the door closes, you pick 2, he moves to 2 after the door closes, etc.) or he could pick 2 and increment every time and you would never catch him, etc.

The main problem with a deterministic strategy is that the game show host always has a way to escape from your next pick, he can either move up or down to avoid your next move. The host always has two options (up or down, two possible numbers), and you have one (a single number). There is always an escape, unless you box him in at the bottom, and this is very costly to do.

With a non-deterministic strategy you would do something where a random number is involved, for instance, you will flip a coin each time to determine what to do, or pick a number from a hat or whatever. In this case, the host cannot know ahead of time what you will do, so either move he makes is equally likely to wind up being the one you randomly pick. There are an infinite amount of numbers, but the larger numbers also pay out bigger, and you will eventually hit the correct number, it is only a question of whether or not you will do so before you pay more than the cumulative cost of opening the doors.

Arguably, a non-deterministic strategy won't actually be better in EV than a deterministic one, although for any given outcome you could get lucky and get a good payoff. So the host might get unlucky and have to pay out a lot, but he probably won't.

Note: A "win" by the host doesn't necessarily mean you don't find the number. It can simply mean that when you do, you have paid the host more than you get back. Per the constraint given in the question that:

You want to leave this game with a profit

For the answer by @Volatility, for example, it can be seen that the strategy is successful in finding the door because you are essentially boxing in the host into winding up at door 2 when you are at a higher numbered even door. But in such a case, the host will win if he picks any door number higher than 5, which will cost you more to play than you will win.

Non-deterministic strategies where you pick a random number slightly above MAXINT (the maximum amount of money the host can put behind the door) and then decrement to 1 while a lot less costly (MAXINT/10 best case) and most likely to win (50%) still have a negative EV because the host will just pick door 1 in that case.

Answer 4

I feel like I've almost got the solution, but can't quite figure out the right parameters to use for it. My strategy is basically the same as @Volatility's with one significant change. The trick is to realize

we can exclude more than one possibility in each step.

Each step will be very similar to @Volatility's strategy other than the trick:

Exclude a \$2 prize as a possibility by choosing door 2. (1 door opened, smallest possible prized obtained is \$2)

The next two steps are similar:

Let's exclude \$1 and \$3 as possibilities by opening door 4 and going down to door 2 (1+3=4 doors opened, \$1 is smallest possible prize obtained).

Then we'll exclude \$4, \$6, \$8, and \$10 as possibilities by opening doors 14 down to 2 (4+13=17 doors opened, \$4 SPP obtained)

We continue using this same pattern:

Exclude odd numbers \$5 through \$15 by starting at door 32 and moving down to door 2 (17+31=48 doors opened, \$5 SPP)

Exclude evens \$12 through \$28 by opening 66 down to 2 (48+65=113 doors opened, \$12 SPP).

And that's as far as we can get with my current parameters:

Prize $17 could now be behind door 130, meaning we need to have opened a total of 243 doors to ensure that we'll get it. The total number of doors we need to have opened at each step more than doubles at each step, so we need to exclude possibilities at the same rate. I just haven't found a way that works yet.

Answer 5

Start by opening door 1. If the prize is $1, you win.

If the prize is $2, then it could either be behind door 1 or door 3. Open door 3. If it is not there, the prize must be back in door 2, so open door 2.

If the prize is $3, then in 3 moves the maximum number door it could be behind is 6. Choose 6. If you don't get the prize, move down one door at a time, until you either get the prize or reach door 2.

If you don't get the prize, guess that the prize is one dollar higher ($4 in this case), take the total number of moves already made (8 in this case), add that to the value of the prize (4 + 8 = 12) to find the maximum number door possible for that prize value, and start from that number door. Move down one door at a time again.

Repeat until successful.

Because the possible doors the prize can be behind are always two apart from each other, there will never be a situation where you choose a door one door away from the prize, and when you move down, the host moves the prize to the door you just chose. This means you will eventually get the prize no matter what the prize actually is (although for high prize values you will probably ultimately lose money from opening all those doors).

Answer 6

Here is a bit of analytics to support the idea that you can win at this game.

First, it is important to note that in order to trap the host's door, you have to have the same evenness as the host, and a higher value than the host. If your number is lower, the host can simply run away from you to infinity and you will never catch him. If his door is less than yours, every move the host must change his evenness in sync with you, and you can chase him down 2. To maximize how much you have to pay the host must always run away towards 1, and to minimize how much you have to pay you must catch him at 2 as he steps back towards you (because he has no place to go).

It is important to try to eliminate multiple doors at once. For instance, if you pick 5, 4, 3, 2, you will win if the host started at 1, 3, or 5. But if you only eliminate even or odd on each pass you will lose, because you are racing a linear number (how much you get) against an exponential (how much you have to pay) due to the need to keep backtracking.

So at a minimum you must catch both evens and odds in a single pass, which means you must repeat each door twice every time.

In order to not lose, you must catch numbers in increasing order, so as to stay in budget for all possible values. So to begin with, assume you will win \$1.00; this gives you a budget of \$0.90, or 9 doors to open if the starting door is 1. If you pick 5, 5, 4, 4, 3, 3, 2, 2 then you will catch any initial pick from 1-5 in 8 picks or less for a maximum cost of \$0.80 and a minimum profit of \$0.20.

So if the host picks a number above 5, then you have a minimum win of \$6, giving you a budget of \$5.00 extra or 50 extra picks to maintain your minimum \$0.20 profit. If you pick 26, 26, 25, 25, ... , 2, 2 , then what initial number will have gone no higher than 25? You have opened 8 doors, so 25-8=17. So any doors up to 17 will now be caught with a minimum profit of \$0.20.

If the host picks a number above \$17 you now have a minimum win of \$18, giving you a budget of \$12.00 extra, or 120 extra picks to maintain your minimum \$0.20 profit. You can thus start at 61, 61, 60, 60, ... 2, 2. But you have opened 58 doors before you start, and 18 + 58 = 76. So you can't even catch 18!

But if you catch fewer numbers to begin with, what happens?

Suppose you pick 4,4,3,3,2,2. You will catch any initial pick in 1-4 in 6 picks or less for a maximum cost of \$0.60 and a minimum profit of \$0.40. If the host picks a number above 4, then you have a minimum win of \$5, giving you a budget of \$4.00 extra or 40 pics to maintain your \$0.40 profit. Since you have had 6 picks, you must start at least as high as 5+6+1=12 to catch just 5. This will cost you 2*(12-2+1) or 22 picks.

In general, you can catch any pick in the range of 1-n in 2*(n-1) picks. Whenever you make m picks to get the range 1-n, you now must start at least as high as n+1+m+1 to catch n+1. since m=2*(n-1), this is n+1+2*n-2+1 or 3*n. You have a minimum profit of \$n+1, but have already spent your previous \$n0 of that, so you have 5*(\$n+1-\$n0) picks.

So in order to win you must consistently have 5*(\$n+1-\$n0) >= 3*n.

5*(n+1-n0) >= 3*n
5*n+5-5*n0 >= 3*n
2*n+5 > 5*n0
n+2.5 > 2.5*n0

It looks like the problem is that n must be at least ~2.5 times greater than n0 each iteration. But is this doable? The following chart suggests it is:

     catch  picks   next minprofit maxcost total min/total
  n   1-n   2*(n-1)  3*n                
  1   1-1     1      3      1       0.10   0.10 10
  3   1-3     4      12     3       0.40   0.50 6
  12  1-12    22     36     12      2.20   2.70 4.4
  36  1-36    70     108    36     10.80  13.50 2.7
 108  1-108   214    324    108    32.40  45.90 2.4
 324  1-324   646    972    324    97.20 143.10 2.3
 972  1-972  1942   2916    972   194.20 337.30 2.8
1942  1-1942 3882   5826   1942   388.20 725.50 2.7
3882  1-3882 7762   11646  3882  1164.60 1890.1 2.0

So this suggests that the optimal sequence to play is:

1, 3, 3, 2, 2, 12, 12, 11, 11, ..., 2, 2, 36, 36, ..., 2, 2, 108, 108, ..., 2, 2, etc.

Edit: It looks like there are some mistakes in this table. maxcost should be picks/10 I think, but it is mistakenly next/10, which is a larger number, so this shouldn't affect the doability, just how profitable it is reported as. I'll fix tomorrow.

Answer 7

A potential answer:

Choose the highest value you think the game host can afford then make your plan to double your door value each time. (Or even ten fold, etc. Just force him to choose your first door)

Counter argument to any other potential strategy:

If the game show host HAS to know the strategy, and you HAVE to eventually hit the prize, you can force the game show host to accept whatever value you want. If the game show host knows your strategy is to increase from $1$ to infinity for example, then what stops him from choosing $2$ and increasing it by one each time? If your strategy is to increase from $x$ to infinity, what stops him from choosing $x+1$ and increasing to infinity? If the game show host is forced to choose an option that results in a finish (which is the only way the listed conditions are definitely satisfied), then he will accept the lowest cost possible (your first door in the given strategy).

Answer 8

I seem to agree with @Michael and @Quark that it's really difficult to win anything in this game.

each door you open costs you a dime, payable to the game show host

I think it would make most sense to pay that up front - or at least be able to land on a loss rather than only zero win, which makes the game even less worth playing. (If you don't risk any loss, I think any strategy will do as bad as the other, but a random one is likely better suited to even out the better odds for the optimal opponent.)

If you still must play I'd suggest you play by your own rules to defeat the game.

First open the last door or the first door, whichever is furthest away. That's right, keep on walking... we're soon there... still just an infinite number doors ahead... There is no second step needed. Then assume that there is an audience that will grow tired of this show, or that the recording cost isn't negligible. And, of course, that the show pays for your hotel nights during the show!

This is a good strategy, knowing that:

However, the game show host will do his utmost to reduce the game show cost.

Thus:

The only way for them to even limit the cost would be to cancel the show or terminate you, before you even open the intended door. They will do the utmost for this, that's your only hope.

Call it the "Hunger Game Solution" if you will.

I can only guess that the host will now say the game is fully VR with instant door-to-door travel time.

As for a puzzle question I think it would be interesting to know why the rules are this hard and then discuss which to change to make the game worth playing.

Always avoid games where you face unlimited loss for a slight chance of winning. Nobody playing is the only way to beat the lottery.

Answer 9

Strategy: Choose any prize value/door, and continue guessing the next highest door if you didn't yet get the prize.

This strategy relies on three hard rules and one assumption reworded as the following:

• Rule 1 – You must disclose your strategy to the host before he decides where to place the prize.
• Rule 2 – The host will minimize the cost to the game show above all else.

• Rule 3 – The prize value does not change when it is moved.

• Assumption 1 – You can pay the cost of guessing the doors to the host at the end of the game, because you weren't given any starting conditions on your money pool.

Let's consider what happens if we pick any value that is not 1.

Case 1: The host places the prize behind a door lower than what you chose.

Because the host can only move the prize to a directly adjacent door, if you keep incrementing your guess by one, you will never uncover the prize and the game will never end. The cost of continuing to run the game/show will increase towards infinity.

Case 2: The host places the prize behind your door, or behind a door higher than what you chose.

There are a number of things that can happen here:

Case 2A: The host chooses a value that is not your door and keeps moving the prize to the next highest door no matter what.

Again, if you keep incrementing your guess by one, you will never uncover the prize and the game will never end. The cost of continuing to run the game/show will increase towards infinity.

Case 2B: The host chooses a value that is not your door, increments or decrements at will, but will not keep the game going into perpetuity.

If you keep incrementing your guess by one, the gap between your guess and the prize will decrease when the host decrements, and you will eventually reach the prize. This gap is unknown to you, but it doesn't really matter; according to Rule 3, the prize value is set based on the first door that the host chooses.

The host can opt to choose a higher value, decrement to near your current choice, increment over a long period of time, then allow you to "win", so as to dime you out of a profit, but he can do this at any time in likely any situation, so leaving with a profit can't really be a hard rule. The host must still pay out a higher value than what you had at your door.

Case 2C: The host chooses your door. The game pays out your prize.

According to Rule 1, you must disclose your strategy to the host, and he will thus come to these same conclusions. Cases 1 and 2A are not viable for the host, as they break Rule 2. Of Case 2B and 2C, 2C offers the least loss to the game show.

Thus, you should choose any high value, and the host would be forced to choose your door to minimize loss to the game show above all else.

Even if this isn't the answer you were looking for, Rule 1 is probably the most important factor in the problem. The true solution likely revolves around limiting what the host can do with his knowledge of exactly what you will do, and forcing him to choose an option that benefits you.

Answer 10

I would go with a strategy something like

"My strategy, Mr. Host, is to tell you that I'm going to start at door 10,000 and then work my way down to door 1, one door at a time. Then, I'm going to tell you that I'm going to do the opposite of my strategy." Since the entirety of my statement is my strategy, and it itself says I'm going to do the opposite of it, I can go either forward or backward during the game.

Alternatively, something like this might work too:

"My strategy is to avoid telling you my strategy."

Regardless, there really is no optimum way to solve this, since the host could easily start at door 999,999,999,999,999 and go upward, which practically guarantees that any strategy the player picks will result in him running out of money before he finds the prize. The only way to do it is to start at some arbitrarily high number x, then choose x, x, x - 1, x - 1, x - 2, etc...

EDIT: In other words, for you mathematicians out there, the only way to solve this would be to name an upward boundary -- a point such that when the host chooses door y or greater, the player is guaranteed to win some money using your proposed strategy. Since the host is trying to save the show money, he would reasonably be forced to choose a door less than y, giving you an upward boundary from which to start.

EDIT II: This is my serious guess as to the optimum strategy:

Choosing odd numbered doors twice consecutively (1, 1, 3, 3, 5, 5, etc...) will guarantee that you eliminate all doors as you move forward. This keeps you moving linearly at the same rate as the host as long as he steadily increases his door. So the strategy I would follow is this: "I will start at 1, then go upward by odd numbers (1, 3, 5...). However, before I move to the next door, I will flip a coin. If the coin is heads, I will choose that door once. If the coin is tails, I will choose it twice." This way, you're not guaranteed to find his door, but you at least have a chance, and he cant predict your moves.