Dr. Ake's 36 Logic Puzzles

Author: Dennis Xia Sha (USA)
Publisher:
Publish Date: 2005-11-01
Features: Expensive Safe Blood
Dr. Max Jacob, wearing a sport jacket and a tie, but with a stethoscope around his neck, glanced at us for a few seconds. "Miss, I hope you're not easily nauseous," he said to Len, who was 11 years old. "We're going to talk about blood." "Human blood or newt blood?" Len asked with a grin. Dr. Jacob smiled. "Smart one. Dr. Ako and the professor, the questions I'm about to ask will require some smart thinking. You probably know that hepatitis C makes patients very weak and can be transmitted through blood transfusions. The test for hepatitis C is called the IIJSA test, and this test is not accurate enough—it gives us false positive reactions (good quality blood is considered bad) and false negative reactions (bad quality blood is considered good). There is a technology based on polymerase chain reaction (PCR) that is expensive but more accurate. This technology is accurate enough that if there is one bag of hepatitis C-infected blood among 50,000 different bags, a single drop of blood can detect it." "Our center receives 100,000 bags of blood every day." Nearly 1% of these blood bags are infected with this disease. We hope to identify which blood bags are infected with no more than 20,000 tests. But each test takes 2 hours, and we want to determine the fate of each blood bag within 4 hours. Can you help us solve this problem?" "Must it be accurate?" Len asked. "I mean, if you don't mind some good quality blood being thrown away along with the bad, then we don't need to test at all—just throw everything away." "You have a bright future in healthcare administration," Dr. Jacob replied with a grin. "First, let's set your premise as: for every bad blood bag you throw away, no more than 2 good quality blood bags can be thrown away with it." "Let's first try testing each blood bag for hepatitis C only once before deciding its fate (2 hours)," Ako suggested.
Beginner's Computer Problem: Before reading on, see if you can find a way to reach a conclusion with fewer than 35,000 tests, and assume there are 1,000 bad blood bags. Your method cannot discard more than 2,000 good quality blood bags. The fate of each blood bag must be determined within about 2 hours.
"Good idea, Uncle," Len said to Ako. "Well, since there are 1,000 bad blood bags and we allow 2,000 false positive reactions, we divide these blood bags into groups of 3, making 33,333 groups, plus one group with 1 bag. The blood in each group is tested together. There are 1,000 groups, each containing 1 bad blood bag. All 3 bags in these 1,000 groups are discarded."
Beginner's Computer Problem: If you have 4 hours to test, and there are 100,000 blood bags with 1,000 bad ones and you can discard 2,000 good quality blood bags, what can Len achieve? What about you?
If you must not make any mistakes, how about that?
Beginner's Computer Problem: Len can achieve the 4-hour zero-error requirement with 20,000 tests. Can you do it?