# How to find an optimal strategy for a coin finding game [closed]

There is exactly one coin hidden amongst $$n$$ boxes. The box it is placed in is chosen uniformly at random.

You can choose an index $$i$$ and the first $$i$$ boxes will be opened. The cost of doing this is an increasing positive function $$f(x)$$ . You must do this with different values $$i$$ until you find the coin. Clearly if $$i=n$$ then you find the coin immediately.

To clarify, if you choose $$3$$ you get to open boxes 1, 2 and 3 and it costs you $$f(3)$$. Having chosen 3, you must pay $$f(3)$$ regardless of whether boxes 1,2 have been checked already.

How can you find an optimal strategy to play this game with minimum expected cost?

• Please edit to include your efforts. I suggest working this out for some explicit choice of cost function. Taking $f(i)=i$ seems natural.
– lulu
Commented Jul 27 at 20:34
• If the cost only depends on the box number, then why wouldn't I open boxes one by one until I find the coin? Since the cost increases with box number it isn't worth risking going far beyond the location of the coin. Commented Jul 27 at 20:38
• @K.Grammatikos As I understand the rules (which are a bit vague), if you select box $3$, say, you must pay for boxes $1,2$ as well regardless of whether or not they have been opened already. Thus, if you first select $1$ and then $3$ you must pay $f(1)+f(3)$ where you could have simply paid $f(3)$ initially (though you'd regret that if the prize was in box $1$).
– lulu
Commented Jul 27 at 20:46
• @lulu I added a clarification
– Simd
Commented Jul 27 at 20:54
• I don't think anyone has said the question is still unclear. Is this a punishment for it being unclear previously?
– Simd
Commented Jul 28 at 7:31

You can solve the problem via dynamic programming as follows. Let value function $$V(k)$$ denote the minimum expected cost when you know that the coin is not among the first $$k$$ boxes. You want to compute $$V(0)$$. The boundary condition is $$V(n-1)=f(n)$$, and for $$j < n-1$$ conditioning on $$i$$ yields recurrence $$V(j)=\min_{i=j+1}^n \left(f(i) + \frac{n-i}{n-j}V(i)\right).$$ That is, you pay $$f(i)$$ immediately, with probability $$\frac{i-j}{n-j}$$ the coin is found among the $$i-j$$ newly opened boxes (ending the search), and with probability $$\frac{n-i}{n-j}$$ the coin is among boxes $$\{i+1,\dots,n\}$$.
If you begin with a probability distribution of the set of boxes, $$N$$, where some box $$n$$ is in the set, $$n \in N$$, then you can formulate a cost function based on the optimal transport formula, $$c(T) = \sum_{n \in N}^{}c \left ( n, T(n) \right )$$ Unless $$f(x)$$ is a probability distribution where $$x$$ is relevant, it is better to define the total cost of opening $$i$$ boxes in the set $$N$$ as $$c(T(i))$$, where $$T(i)$$ is the transport map, which is not entirely clear from the question as the cost of opening $$i$$ boxes is not numerically defined. Assuming the relation between $$i$$ and $$c(T(i))$$ is linear, then the solution should be, $$c(T(i)) = \min \sum_{i \in N}^{}c \left ( i, T(i) \right ) = \sum_{n=i}^{}c \left ( n, T(n) \right )= c \left ( n, T(n) \right )$$ meaning in order to minimize the total cost, open all the boxes, since the coin can be found in one transport operation, and if $$i, then all other costs to open boxes not containing the coin in the set will inevitably be greater.
• Consider the case $n=2$ with cost $f(1)=1$ and $f(2)=1000000$. Commented Jul 27 at 22:44