5
$\begingroup$

You have $93$ of $100 bills and there is a counterfeit 100 dollar among them. You do not know which one is counterfeit bill. You go to the bank and ask whether if there is counterfeit among a group of 100 dollars bills. But every time you ask for a group of money or a just a bill,

  • If the response is NO, you will lose 1 dollar.
  • If the response is YES, you will lose 3 dollars.

In the worst case scenario, at least how much money are you going to lose after you find out the counterfeit?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
7
$\begingroup$

At the first look it seems pretty obvious, simply split the notes in a 1:3 ratio to minimize the money lost. However, if we look more closely, we see that as soon as we have 4 or less bills, we simply have to check them one by one. This fact slightly changes the optimal ratio, therefore I made the decision tree shown below.

enter image description here

The tree shows the maximum number of notes where we can identify the counterfeit bill. I omitted the repeated tree parts on the left side which are simply copies of the sub-trees on the right. The row where each box is placed defines the amount of money we lost. We always present the smaller group of bills to the bank, red boxes are "Yes" answers, green boxeys are "No" answers. We can see that to identify the counterfeit note among 89 to 129 notes we will loose $14 in the worst case.

I have still no idea why the starting number 93 was chosen.

Improve this answer
$\endgroup$
2
$\begingroup$

Since we want our expected loss to be the same whatever answer we get, we want to have the \$3 loss be three times as "helpful" as the \$1 loss.

This means we should:

ask about a group of 1/4 of our items every time. Our greatest loss comes from rounding the "wrong way" each time. The best way to round is towards the 3/4 section: then the maximum loss is "yes-yes-yes-yes", for a total of \$12.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If you round towards the 3/4 section, your worst case won't be in the 1/4 section. $\endgroup$
    – Sleafar
    Commented Dec 16, 2017 at 13:00
  • $\begingroup$ +1. But if you round towards the larger, then, say with 7 notes remaining, you'll be presenting the notes 1 at a time (7/4, 6/4, 5/4, 4/4), after which you'll need to switch to something else (3/4 rounded down is 0 - no cost, but no progress, either). $\endgroup$
    – Lawrence
    Commented Dec 16, 2017 at 13:29
  • $\begingroup$ The question asks not to minimise expected loss, but to minimise worst-case loss. $\endgroup$
    – Jasen
    Commented Dec 17, 2017 at 2:10
  • $\begingroup$ @Jasen - yes. If our expected loss is "unbalanced" between two options, then we can assume an adversarial opponent that will pick the worse of the two. (We want to distribute our total loss evenly among all possibilities.) $\endgroup$
    – Deusovi ♦
    Commented Dec 17, 2017 at 2:36
1
$\begingroup$

Suppose you instead had \$$n$ to spend on guesses. What is the maximum amount of potentially Benjamins you could find the fake among? Call this amount $a_n$. This satisfies the recurrence $$ a_n = a_{n-1}+a_{n-3} $$ Why? Suppose you have \$n to spend, there are currently $b$ Benjamins, and you send $k$ to the bank. In order to succeed, it must be true $k\le a_{n-3}$ so you can succeed if the test is positive, and also $b-k\le a_{n-1}$ so you can succeed when the test is negative. The best case is when these inequalities are equalities.

This recurrence relation, along with the base cases $a_0=a_1=a_2=1$, allows us to compute $a_n$ easily, which gives:

 n │  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
───┼────────────────────────────────────────────────────────────
a_n│  1   1   1   2   3   4   6   9  13  19  28  41  60  88 129

The first n for which $a_n\ge 93$ is 14, so you will need to spend \$14 in the worst case. The winning strategy if you currently have $b$ Benjamins is to send $a_{n-3}$ Benjamins to the bank, where $n$ is the smallest numbers for which $a_n\ge b$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.