Communications of the ACM
Last byte
Randomized Anti-Counterfeiting
Consumers and pharmaceutical companies have been known to disagree over drug prices but have at least one interest in common: Neither wants the consumer to consume counterfeit drugs. The drug companies do not want to lose the sales, and consumers may have a critical need for the drug they paid for.
Counterfeiters have other ideas, however, so produce and sell packages full of fakes (usually simple sugar pills) in a $100 billion-per-year worldwide business. The drug companies have fought such fakery by incorporating special packaging (holograms, unique numbers, sometimes even electronic tags) on the drug containers. With so much money to gain by selling sugar pills for high prices, however, the counterfeiters have managed to copy the packaging very expertly.
A clever but so far fictitious drug company has implemented the following random algorithm-style invention: Give each drug package (or bottle) a unique identifier, number each pill within a package—1, 2, 3, ...—and insert an innocuous food coloring, from a palette of at least two colors, inside each pill. The food coloring is invisible until the pill is consumed.
Now suppose each package receives a random sequence of red or blue food colors, with equal probability. For concreteness, suppose package 133 has colors in the following numeric sequence
1: red, 2: red, 3: blue, 4: blue, 5: blue, 6: red, 7: blue, 8: red, 9: red, 10: blue
Package 152 has
1: blue, 2: red, 3: blue, 4: blue, 5: red, 6: red, 7: red, 8: red, 9: blue, 10: blue
While the colors are invisible before consumption, the consumer sees the color after taking the pill. A consumer worried about counterfeiting can log into a drug company website and, upon demonstrating some proof of purchase, look up the package number to see the pills associated with each number (such as, 1: red, 2: red, 3: blue, ... for package 133). Once the consumer starts taking the pills, the consumer can compare the pill's color with the one intended for that pill number in that package. If even a single color does not match, that pill, as well as all the other pills in the package, should be presumed fake. Because the counterfeiter would have to guess the coloring, after only two pills have been consumed, the consumer has probability 1 - ((1/2)x(1/2)) or 3/4 probability of knowing the package is fake.
But mistakes happen. For example, suppose the consumer has opened packages 133 and 152 and separated the pills into two jars—J1 and J2—but does not remember which jar corresponds to which package. The consumer does not want to take two real pills on any particular day (they can be toxic in high doses) and wants to, of course, avoid taking only fake pills any day.
Problem. How can the consumer still determine whether the pills in each of the two jars are fake with a probability of 3/4 for each jar after taking at most six pills altogether?
Solution. The consumer picks a number i between 1 and 10, such that the intended color of pill i from package 133 differs from pill i from package 152. In our example, i could be 1 because pill 1 in package 133 should be red, and pill 1 in package 152 should be blue. If the consumer picks pill 1 from jar J1 and it is red, the consumer can then hypothesize that jar J1 corresponds to package 133 and will continue to choose two more pills from J1. The consumer checks these pills against the intended colors from package 133. If both are indeed the intended color, then J1 consists of real pills with probability ¾. In this case, the consumer can turn to jar J2, and if the colors of two selected pills correspond to package 152, then, with probability 3/4 is also good.
If the pills from J1 reveal a mismatch with 133, the consumer would then declare J1 to be fake. Now J2 could be 133 or 152 or could again be fake. From J2, the consumer chooses pill numbers where 133 and 152 differ in their intended color (such as pill 5 and pill 7). If pill 1 from J2 is consistent with package 133, the consumer should then check pill 5 and pill 7 for consistency with 133. Otherwise, if pill 1 from J2 is consistent with the colors from package 152, then the consumer should check pill 5 and pill 7 for consistency with 152 next.
However, consumers can sometimes be even more absent-minded. Suppose, for example, a consumer mixes the pills from package 133 and package 152 together in one jar, as in the figure here.
This time, the consumer has bought the packages in different cities so can legitimately assume that at most one of them is fake. The consumer also assumes that every self-respecting counterfeiter would put harmless and impotent fake pills in a fake pill bottle. So the jar has two identical-looking pills numbered 1, two identical-looking pills numbered 2, ..., two identical-looking pills numbered 10. With the same requirement that the consumer should never take more than one real pill per day, what strategy of pill-taking can be used so that, after four days, the consumer knows, with a probability ≥¾, that the consumer will be able to take exactly one real pill (and possibly one or more fake ones) over the subsequent eight days?
Solution. The consumer takes one pair of pills with the same number and color as, say, the pills numbered 2. If either pill is blue, then one of the two packages is fake. The consumer does not know which one, but it does not matter, and can subsequently take both pills with the same number from then on every day (such as the next day), take the two pills numbered 1, then the two pills numbered 3, and so on. Because the consumer knows at least one package is good, the consumer will be getting exactly one real pill every day, as desired.
Counterfeiters produce and sell packages full of fakes (usually simple sugar pills) in a $100 billion-per-year worldwide business.
On the other hand, if both pills numbered 2 are red after day two, then the consumer takes the numbered 5 pills on days three and four, respectively. If there is one red and one blue pill, the consumer then knows with probability ¾ that both packages are good, so can take the rest of the pills, one per day, preferring pairs with the same color, as with, say, pills 3, 4, 6, 8, and 10, unless a mismatch is found in which case the consumer can take the pairs with the same number from then on.
Upstart. More colors help, but more packages hurt. Suppose there are c colors of pills, and k packages have been put in the same jar and at most f < k can be fake. What is a good consumer strategy for taking at most one real pill per day and having a high probability of a real one every day, too?
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.
No entries found