Venture Capital puzzles, solved step by step

Puzzles: 100
Traced to a firm: 7
Topics: 12
Hard: 30

Showing 1–1 of 1 · filtered from 100Clear filters

058One of 1,000 bank statements in a data room is forged. A forensic test run on a pooled sample of statements shows only whether any statement in the pool is forged, and every result takes a week. You have exactly one week. What is the fewest tests that identify the forged statement?Logic and brainteasersHardMulti-stage VCFintech VC
Try it first
How many tests, all started on day one?
Show the worked solution
Ten tests, run at once. Number the statements and write each number in binary, ten digits long. Test pool 1 holds every statement whose first digit is 1, pool 2 every statement whose second digit is 1, and so on. A week later the ten results, read as positive equals 1, spell out the forged statement's number. Ten is the minimum because nine tests give only 512 possible result patterns, fewer than the 1,000 statements.
Why can you not just halve the pile and test again?
Halving is the right instinct when you can see each answer before asking the next question, like guessing a number with higher or lower clues. Here every result takes the full week, so all the testing has to be designed up front. When questions must be asked in parallel, each statement needs its own unique pattern of answers, and the puzzle becomes how many yes or no answers it takes to give 1,000 statements a distinct pattern each. Ten answers give 2 to the 10, or 1,024 patterns; that is enough.
Writing each statement number in binary assigns it to the pools whose digits are 1, so a forged statement #357 lights up pools T2, T4, T5, T8 and T10, and those positives read back as 0101100101, which is 357.
How do you prove ten is the fewest?
Count the outcomes. Each test has two results, so n tests have at most 2 to the n distinct result patterns, and you need at least one pattern per possible forgery. Nine tests give 512 patterns for 1,000 suspects, so at least two statements would share a pattern and you could not tell them apart. Ten give 1,024, which is why 10 is both achievable and the minimum. One small detail: if you number the statements 1 to 1,000, the all-negative pattern is never used, which is fine because one statement is definitely forged.
The relationship
$2^{n} \ge 1000 \;\Rightarrow\; n \ge \log_2 1000 = 9.97 \;\Rightarrow\; n = 10$
n number of pooled tests run in parallel
2^n number of distinct positive and negative patterns n tests can produce
What it says in wordsYou need as many result patterns as suspects, and each extra test doubles the patterns.
Say where the trick breaks. It relies on exactly one forgery; with two forged statements, the positives are the union of two binary numbers and no longer name either one, so you would need more tests and a different design. It also assumes the test is perfectly sensitive in a pool of 500 statements. In real diligence a forger rarely fakes only one document, so the useful habit is the reasoning, counting outcomes before designing the checks.
Where candidates lose it
The common answer is a halving strategy that needs ten rounds, ten weeks. It is the right count for the wrong reason: the deadline rules out sequential testing, and the interviewer wants to hear you notice that before you start.
The second trap is giving 10 without the proof of the minimum. Say the counting argument in one sentence: nine tests give 512 patterns, fewer than 1,000 statements, so two statements would look the same.
What the interviewer asks next
What if two statements were forged?
If you had two weeks, could you do it with fewer tests in total?
How would the design change if a pool larger than 100 statements made the test unreliable?

n	number of pooled tests run in parallel
2^n	number of distinct positive and negative patterns n tests can produce

Try it first

Why can you not just halve the pile and test again?

How do you prove ten is the fewest?

Where candidates lose it

What the interviewer asks next