# A Counterfeit $100 Bill among 93 Bills 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? 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. 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.
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$.