18
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ I feel like this puzzle should have both the weighing and graph-theory tags, but then again, maybe not. $\endgroup$
    – Bass
    Commented Oct 11, 2023 at 9:40
  • $\begingroup$ Remind me of this recent puzzle because of the common theme of "checking 3 things at a time". $\endgroup$ Commented Oct 11, 2023 at 11:31

7 Answers 7

7
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Since my answer is almost the same: 1 thing you forget is that one can also test a new pair , this gives extra term max( S(N-2,k)+1, S(N-1,k-1)+2) within the min(). If my program is correct that improves the answer to 1754 $\endgroup$
    – Retudin
    Commented Oct 12, 2023 at 7:58
  • $\begingroup$ I now see that 'your' optimum is almost at the end, so my calculations are wrong; Using a new pair is a (unmentioned) strategy, but I now doubt it matters. $\endgroup$
    – Retudin
    Commented Oct 12, 2023 at 8:20
  • $\begingroup$ final remark after I recalculated: It does not matter; However it would have saved 1 attempt in around a 3rd of other amounts of notes, e.g. if there were 1004 or 1016 notes. $\endgroup$
    – Retudin
    Commented Oct 12, 2023 at 11:07
  • $\begingroup$ @JS1 That is precisely what I am already doing, cf. "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." $\endgroup$
    – loopy walt
    Commented Oct 13, 2023 at 0:14
  • $\begingroup$ Sorry I didn't read that part carefully. You're right you are already doing that, and I think your solution is the most likely the best possible. $\endgroup$
    – JS1
    Commented Oct 13, 2023 at 2:32
18
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Going by the "worst case scenario" idea, what if all 250 stacks of 4 notes have 2 fake notes? $\endgroup$
    – nomad.lw
    Commented Oct 11, 2023 at 4:05
  • $\begingroup$ @nomad.lw That's the second scenario I describe - interestingly, it's actually a better case than one set having three $\endgroup$ Commented Oct 11, 2023 at 12:13
  • $\begingroup$ A clarification: in the first step, you only need to test piles until you come across a set of of three good bills. It is only in the (nearly) worst case scenario that you would need to test all of the piles. $\endgroup$ Commented Oct 11, 2023 at 18:43
  • $\begingroup$ Good point, have clarified. $\endgroup$ Commented Oct 11, 2023 at 20:43
  • $\begingroup$ This is in the worst case. In the average case I found that it takes 8 attempts on average to find 3 real banknotes just by trying random triples. $\endgroup$ Commented Oct 19, 2023 at 11:51
17
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ You can do it in half of that, worst case, if you find you have half bad notes. Then you can stop testing. $\endgroup$ Commented Oct 11, 2023 at 15:09
  • 2
    $\begingroup$ On the other hand, if you find them impossible to distinguish, what justifies your confidence the ones in your wallet are good? ^_^ $\endgroup$ Commented Oct 11, 2023 at 16:17
  • 6
    $\begingroup$ @MichaelFoster - it is in the best case that you stop with half that. In the worse case, with only two bills left to test, you have found only 499 good and 499 bad, and still have to test one more to get half either way. $\endgroup$ Commented Oct 11, 2023 at 19:04
  • 1
    $\begingroup$ @PaulSinclair, you're right...I was thinking about it more later, but didn't get around to deleting my comment. $\endgroup$ Commented Oct 11, 2023 at 19:06
  • $\begingroup$ in fact you can do it in two less tests if you add your own two good notes to the submission :) $\endgroup$ Commented Oct 18, 2023 at 13:29
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Three fake bills down one of the diagonals and all others real will result in all seven tests showing fakes. All eight if you also test the other diagonal. $\endgroup$ Commented Oct 11, 2023 at 19:11
  • $\begingroup$ @PaulSinclair, that is true; I had not considered the possibility. I still think this matrix concept can be revised, though, and will think on it. $\endgroup$ Commented Oct 11, 2023 at 19:20
  • $\begingroup$ Too late to edit comment. First thought: if you get 7 negative results, switch places of one diagonal corner with one non-diagonal corner, then re-test the one switched on the diagonal with one NOT switched and not on the diagonal. That increases the tests needed to 8, increasing the total tests by 100. Thinking more before I edit my answer. $\endgroup$ Commented Oct 11, 2023 at 19:25
  • $\begingroup$ Spurred on by your comment, I found another matrix with only four fakes for which even my new solution fails. It's harder to describe, but I'll number the boxes by row, and set 1, 3, 4, and 8 to fakes. Still thinking. $\endgroup$ Commented Oct 11, 2023 at 19:30
  • 2
    $\begingroup$ I suggest deleting it, then editing it (you can do that - if you delete it, you will still see it (as will others with high enough rep, by the way, but they cannot vote or comment). Then you can modify it at your leisure, and undelete it when it is ready. $\endgroup$ Commented Oct 11, 2023 at 20:10
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

IMO the biggest challenge would be to get a set to beep positive, post that it's n+997 (given the worst possible distribution), where n is the number of tries it takes you to get to a clean/positive set.

Being able to feed 3 notes at a time leaves you with two ways to rotate notes, one at a time, or two at a time.

  • Approach 1- One a time:
    • If there is a even distribution of fake and real notes, it would take 1000 tries to identify
    • (suppose evens are fakes) you then create a set from evens, then rotate each one with a corresponding odd to get a clean set?

Okay that's the extent of my imagination atm, I'm guessing there's a better method in statistical math. Looking forward to seeing what that is.

$\endgroup$
1
  • 1
    $\begingroup$ Do you have a specific strategy and a specific answer? $\endgroup$
    – bobble
    Commented Oct 12, 2023 at 22:41

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.