-2
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ Please edit to include your efforts. I suggest working this out for some explicit choice of cost function. Taking $f(i)=i$ seems natural. $\endgroup$
    – lulu
    Commented Jul 27 at 20:34
  • $\begingroup$ 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. $\endgroup$
    – K. Grammatikos
    Commented Jul 27 at 20:38
  • $\begingroup$ @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$). $\endgroup$
    – lulu
    Commented Jul 27 at 20:46
  • $\begingroup$ @lulu I added a clarification $\endgroup$
    – Simd
    Commented Jul 27 at 20:54
  • $\begingroup$ I don't think anyone has said the question is still unclear. Is this a punishment for it being unclear previously? $\endgroup$
    – Simd
    Commented Jul 28 at 7:31

2 Answers 2

Reset to default
2
$\begingroup$

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\}$.

$\endgroup$
2
1
$\begingroup$

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<n$, then all other costs to open boxes not containing the coin in the set will inevitably be greater.

$\endgroup$
1
  • 1
    $\begingroup$ Consider the case $n=2$ with cost $f(1)=1$ and $f(2)=1000000$. $\endgroup$
    – RobPratt
    Commented Jul 27 at 22:44

Not the answer you're looking for? Browse other questions tagged .