Source: Wikipedia.
I’m writing this one just in case your kids ever wonder what math is good for.
Germany has had a remarkably rational, effective, and organized response to the COVID-19 pandemic. One thing I found out yesterday is that they test every hospital employee for the virus.
I was floored. How can they do that? U.S. hospitals have about 5.2 million employees on payroll. If you toss in volunteers, and physicians and others with hospital privileges, it’s safe to say that, in the U.S., you’d be talking about testing at least 6,000,000 people on a routine basis.
That would require about six times more tests than the US has done, in total, so far. Just to do one round of testing on all US hospital employees. US public health labs have done fewer than 200, 000 test. If you toss in a guess as to all the testing done in private labs, you’d still come up with somewhere in the neighborhood of 1,000,000.
How on earth can Germany do that, then? I mean, sure, they probably have more test per capita than we do. But, still, that’s a pretty big gap between what the entire U.S. lab system appears to be able to do, and what the Germans routinely do.
What’s their secret?
Teutonic Two-Tier Testing (TTTT), defined
The Germans test their hospital employees in batches of ten. They pool the swabs for 10 employees, test that, and then only when a batch is positive, they test the individual employees in that batch. Man, that’s smart.
So, TTTT is defined a testing your entire workforce in batches of 10, then testing individuals only when a batch shows a positive (infected) result. They don’t need to test the individuals in batches that test negative, because they know that nobody in that batch is infected.
For a hospital with 100 employees and one infected employee, they don’t need 100 tests. They only need 20. Ten for the first round of testing (batch testing), and ten for the second round (individual testing, within one batch).
Those of you who are in the computer sciences will recognize that as a form of an efficient search strategy. The upshot is that the Germans can do it because they’ve figured out how to do it efficiently.
From that, I’m going to present a series of real-world word problems. Answers will be given in tomorrow’s post.around 3 PM this afternoon. in the next post (don’t peek). Something for every math skill level, starting with long division.
1: TTTT, the math problem
Euler Hospital has a total of 500 employees. They have exactly one employee who is infected with coronavirus.
A) How many total tests will Euler Hospital need, in order to find that infected person, if they use the TTTT method described above (test in batches of 10).
B) How many tests did TTTT save, compared to testing each person separately?
C) What percent of tests did TTTT save, compared to testing each person separately?
2: TTTT, the algebra problem: Modified TTTT
Euler Hospital has a total of E employees. They decided to use a modified TTTT method. Instead of testing 10 in every batch, they decide to test N in every batch.
A) Write down the formula for the total number of tests T required, to test E employees, in batches of N employees each, under the modified TTTT method.
B) Check your formula by plugging in the numbers for Euler Hospital above.
Ignore rounding issues (i.e., a fraction of a test has to be rounded up to the next whole number. Ignore that for purposes of this question.)
3: TTTT, the calculus problem: Optimized TTTT
A) Using the formula derived from Problem 2, find the formula for the optimum batch size for a hospital with E employees. That is, find the batch size N that minimizes the total number of tests T, required to test the E employees of Euler Hospital, under modified TTTT. Under the assumption that there is exactly one infected employee.
Again, ignore any rounding issues.
B) Calculate optimum batch size and minimum number of tests for Euler Hospital, above.
4: TTTT, the numerical analysis problem: Who needs calculus when you have computers?
A) Using Excel (R) or other spreadsheet program, and the formula from Step 2, set up a simple spreadsheet that calculates the number of tests required when you enter the number of employees E, for batch size N. Like so:
Cells A2 and B2 have numbers that you type in. Cell C2 has the formula.
B) Now find the optimum batch size for Euler hospital by brute force search. That is, just calculate it for every reasonable batch size value, then look to see which one needs the fewest tests. Copy those three cells all the way down the page, and change column B to a formula so that it adds 1 to the value with each new line. Like so:
Now column A holds the number you typed in, column B starts with the number ten, then has a formula that adds 1 to the number above it for each new line. And column C has the same formula as it always did.
Look down Column C and find the optimum batch size for Euler Hospital. If possible, check that your answer, via numerical analysis, matches the calculus-derived answer from the prior question.
Again, we’re fudging the rounding issue, as always.
5: TTTT, the computer algorithms exercise. Better than optimized TTTT
Gauss General Hospital (in tiny Binary, Arkansas) has 256 employees. Because they are a small rural hospital, they were only given 20 test kits for testing their entire staff. And then they were told to use modified TTTT to test their entire staff.
A) Using the results from either 3) or 4) above, prove that they don’t have enough test kits to do that.
So, as is often the case in a crisis, these folks are going to have to think for themselves, and do it fast, if they’re going to succeed. They know they have one infected employee on their staff. The need to find that employee. They can’t do that using the standard method of any form of TTTT.
B) Two employees are talking. One says, if we could only cut this problem in half, we’d have enough tests. The other employee says, aha! I know how to do it.
Describe a method that would allow them to find their one infected employee, using no more than the 20 tests they have on hand. Hint: They are inspired by the name of their town. And the employee count is not a coincidence.
C) How many tests are required under your alternative to optimized TTTT? (Don’t make a rookie mistake here. Each tier of testing requires testing all the employee groups that made it to that tier. So the number of tests is a multiple of the number of rounds of testing. Don’t mistakenly give the number of rounds of testing as the answer.)
6: TTTT, the calculus-of-variations problem.
A) This is an open-ended question. Using whatever methods you prefer, tell me whether optimized TTTT matters more for larger or for smaller hospitals. That is, if you substitute optimized TTTT for testing every employee, trying to find that one infected employee, where do you get the greatest percentage reduction in tests? Is it in a small hospital? A large hospital? Or a medium-sized hospital?
The calculus-of-variations approach inspects the derivative of T with respect to E, in the formula for the optimized TTTT batch size. The rest of us can just calculate a few examples, and we’ll come to the same conclusion, using our spreadsheet.
This is the needle-in-a-haystack effect. The less dense your targets are, the more that search efficiency matters. Remember, there’s only one sick employee here in this problem, regardless of hospital size.
This same effect often limits what you can do, cost-effectively, to screen a population for diseases. Even for fairly prevalent diseases. For example, based on calculations I did years ago, the Medicare program spends more for breast cancer screening than it does for breast cancer treatment. That’s not an argument against mammography, it’s just a reminder that screening an entire population can be hugely expensive.
So, why don’t we just test everybody? That’s your answer.
7: TTTT, the epidemiology problem.
Let’s go back to standard TTTT now. And to Euler Hospital with its 500 employees.
Up to now, we’ve assumed there was exactly one infected employee. But what if that’s wrong? What if there could be several, even many, infected employees?
A) Using a worst-case-scenario approach, how many test would you need to do, under standard 10-at-a-time TTTT, to find two infected employees?
B) How many would you need to find 10 infected employees?
C) TRICK QUESTION, calculate the number and think about it first, before you answer this. How many tests would it take to find 60 infected employees, under a worst case scenario?
The epidemiology point of C is that, if you let this get far enough out of hand, there is no obvious clever solution. You might as well go ahead and test everybody.
8: Extras for experts: TTTT, “balance puzzles”, and robust algorithms.
Many of you have probably already recognized that TTTT is related to a class of brain-teasers know as “balance puzzles“. There, all you have is a standard two-pan balance, and you are required to identify (e.g.) which coin is under-weight, out of a stack of N coins, using the balance the fewest possible times.
Those are fun, but they don’t have any real-world relevance here, because they typically rely on knowing (e.g.) that there is exactly one bad coin in the lot. That allows you to divide the coins into three groups, test just two, and infer something about all three groups. In the real world, the true number of infected individuals is not known, and so you can’t do that.
Typical “balance puzzle” solutions are not robust algorithms. In the sense that, if you assume you only have one underweight coin, but you actually have many, they fall apart. The don’t work. And so, they depend critically on the real world exactly matching your assumptions. Which, in truth, just never happens.
If you haven’t gotten bored with this yet, satisfy yourself that all your methods here are robust, in the sense that, each of them will eventually find all your sick employees, no matter how many you have. But that as the infection rate rises, the total number of tests required also rises. And I’m pretty sure that, for all of them, if the infection rate rises enough, cleverness is just a waste of time. At a high enough infection rate, you might was well just test everybody.
