Find all the real money

Question

An eccentric billionaire invites you to join in one of her strange games. She lays before you 1000 $100 notes, and announces that half of them are actually fake. You check the notes carefully, finding yourself totally unable to distinguish the counterfeits from the real ones.

"Take $50000," says the billionaire. "If all the notes you take are real, they are yours. If not, you take away nothing."

“They all look the same to me!” you protest. "My chances are practically zero."

"See that detector over there? It accepts three notes each time and beeps if there's any fake among them. Use it. I'll be back tomorrow morning to verify your result." The billionaire swiftly left the room, barely finishing her sentence.

You want to leave nothing to chance about winning your $50000 prize. In the worst case scenario, what's the minimum number of times you need to use the detector to find all the real money?

Answer 1

I believe building upon and refining @BlueHairedMeerkat's approach it can be done in

1831

steps.

If you haven't read B.H.M.'s answer, now would be a good time.

We can find a significant saving by optimising the endgame, meaning the phase where we have already identified at least two good bills.

Let N be the number of unidentified bills left. We will know how many of those are fake, let's call that number k. What is the worst case number s(N,k) of steps we will need to identify all leftover bills using the following strategy?

If $3N > 3k \ge N$ I don't think we can do better than checking every individual bill, save the last: $s(N,k)=N-1$

Otherwise, if the fraction of fakes is small enough, it is worthwile checking triplets directly. If there is no beep, we are down 3 bills in one step. If there is a beep we check one of the 3 bills directly; if it is fake we are down one fake bill in two steps; if it is good we check a second one. The second one being good cannot be the worst case because then we know all three whereas if it is fake the third one could still be good or fake. In that case we are down 2 bills one of which is fake at the cost of 3 steps.

Taken together this yields the recurrence

$s(N,k)=\min(\max(s(N-3,k)+1,s(N-1,k-1)+2,s(N-2,k-1)+3),N-1)\qquad N>k>0$

Here the max picks the worst of the three cases just discussed. The min accounts for our switching strategy as soon as k becomes too large compared to N.

A closed form solution is

$s(N,k)=\min\left ( \left\lfloor \frac{N+7k-2} 3\right \rfloor, N-1 \right )\qquad N>k>0$

Now we apply this to B.H.M.'s strategy. We do not, however, do all 250 lots of 4, instead we stop the moment we find a clean triplet. Each of the m quadruplets except the last one have at least 2 fakes. We can find them in 3 steps (in addition to the 4 already spent). Leaving us with at most one ambiguous bill in each quadruplet. The total number of unresolved bills is thus $N=997 - 3m$ if we found the clean triplet first in its quadruplet (otherwise $N=996 -3m$). Of those $k=500-2m$ are fake (or $k=499-2m$) the number of steps already spent is $7m+1$ (or $7m+4$).

A computer search finds that the worst case, i.e. $\max (s(997-3m,500-2m)+7m+1,s(996-3m,499-2m)+7m+4)$ is $1831$, attained at m's maximal value $m=249$.

Answer 2

I can do it in

1995

tests.

Split the notes into 250 piles of 4, then for each pile check every combination of notes within it. This will take, in the worst case, 1000 tests.

If at some point you find three real notes, you will then need 995-996 tests - you want to check two good notes against each other note, except that you can deduce the final one and you may have already checked two of them against the fourth in their group. Assuming you find this trio as late as possible, this will take a total of 1995 tests.

If you don't ever find three real notes, this means that every pile has exactly two real notes in. Now combine two piles and test every trio of notes in in - this will take 56 tests. (Fewer, actually, but that's not important.) Now we have four good notes and can start testing the rest, but note that we can skip every fourth note - we know each group is 2 and 2, so after getting two of a kind we can deduce the rest of them. Hence we need 3 * 248 = 744 total tests, for a total of 1800. This is lower than the other case, so we can ignore it.

Answer 3

I can do it in

999 tests

by cheating. (That is, following the letter of rules instead of their spirit.)

I pull two known-good notes out of my wallet,

after which I can test each note individually. The last one I won't need to test even in the worst case.

Answer 4

I don't know if the following is optimal. This solution uses

$1019+996=2015$

tests.

The first stage is

to find a set of three real bills. If we split the $1000$ bills into $249$ groups, then by the generalised pigeonhole principle at least one of the groups will have three real bills (because there are $500$ real bills, and $500/249>2$).
So split the $1000$ bills into $245$ groups of $4$ and $4$ groups of $5$. For each group we can test all possible subsets of three bills. This would take $245\binom{4}{3}+5\binom{5}{3}=1020$ tests. Note however that we can quit after $1019$ tests since if they were all negative, the last test will have to be positive.

The second stage is

to combine some of the real bills we found with each of the other $997$ bills in turn to determine which are real. This takes $997$ tests, but again we can omit the last test because its outcome can be deduced.

Answer 5

I can do it in:

2168

tests.

Explanation:

Create 200 groups of 5 bills each. Test every combination, of which there are 10. If any results in no fakes then it would be quicker, so they must have fakes in every combination. This would normally take 2000 tests, but each group of five that has fakes in every combination MUST have a minimum of three fakes in it, so if you get to 498 fakes in 166 groups, with 1660 tests. The next group MUST find three real bills, so 1670 tests.

Additional notes:

If you did 1670 tests, then the remaining 165 untested bills (1000 - 835 tested) must be real, and need not be tested. You also have another set of three bills tested to be real, so have 168 real bills. Test the tested groups' bills against two real bills until you have 500. Note also that each group can have no more than TWO real bills, so no more than three tests per group of five, so a maximum of 498 more tests (166 X 3 tests).

If you did less than 1670 tests, then you found some real bills early, and can then proceed to checking unchecked bills against them. The sooner you found them, the fewer tests you will end up doing, so only the previous section is relevant, as is worst-case.

Answer 6

This refines BlueHairedMeerkat's solution to use

1900 tests

As before, start by

splitting the bills into 250 groups of 4, and testing all 4 triples in each group.

Now,

if you find a legit triple, let $r$ be the number of remaining untested groups. If $r \geq 25$, then you've spent at most $225 \cdot 4 = 900$ finding a legit triple. With a pair of legit bills, you can test each bill within $1000$ tests, for $\leq 1900$ tests total. (Actually a bit less, but I'm not optimizing the exact numbers.)

Another outcome is

if we don't find any legit triples, all the groups must have split two legit and two fake, which can be handled in 1800 total guesses as BlueHairedMeerkat explains.

Finally, the interesting case is where

we find a legit triple with $r<25$ untested groups remaining. This took a maximum of $4(250-r)$ tests, and we can now identify the $4r$ bills in untested groups individually in $4r$ guesses, for a total of $1000$ tests so far.
Now, we use the information from the previous $249-r$ tests to save on identifying bills. Each earlier-tested group has at least 2 fake bills, or we would have found three real bills among it. This accounts for $2(249-r)$ fake bills of $500$, which leaves $2r+2$ "additional" fake bills beyond two in each group. Now, we test 3 of the 4 bills in each previous group with two known legit bills, for $3(249-r)$ tests. We guess that the remaining bill is whatever gives a total of two legit and two fake in the group (unless we see 3 fake, in which case the last is legit). This is true for all but the $\leq 2r+2$ groups with an "additional" fake bill, where we may guess it's legit even though it's fake.
But, we can confirm these guessed bills by dividing them into groups of 3, and checking that all 3 are legit, for $(249-r)/3$ tests. For the $\leq 2r+2$ checks that got contaminated by an "additional" fake bill, we check all the 3 bills directly. This costs $ \leq 6r+6$ tests.
The total number of tests we've used is at most: $$1000 + 3(249-r) + (249-r)/3 + 6r+6$$
which is $1836 + 8/3 r$. Since $r \leq 24$, this is at most $1900$ as desired.