You’re in the market for a “Gizmo.” A shop has five Gizmos available to buy, but the shopkeeper has bad news: two of them are malfunctioning, and she doesn’t know which ones are working and which ones aren’t. She explains that you can run a diagnostic test by linking two Gizmos together and having them assess each other. A single test yields two simultaneous results: the first Gizmo’s report on the second and the second Gizmo’s report on the first.
A functioning Gizmo will always give you an accurate assessment of whether the one it’s linked to is functioning or malfunctioning. But a malfunctioning Gizmo could say anything about the one it’s linked to—it could report the other as functioning or malfunctioning regardless of the truth. The shop is closing, and you only have time to run two tests. You also only have enough money to buy one Gizmo. How can you guarantee that you walk out with a functioning Gizmo?
First, pick any two Gizmos—let’s call them A and B. Link them and run a diagnostic test. We can sort the possible outcomes into two cases.
Case 1: At least one of the Gizmos claims that the other is malfunctioning. If the Gizmos do anything other than vouch for each other as functioning, then we know there must be a malfunctioning Gizmo in the duo. A functioning Gizmo would never lie and call a good Gizmo broken, so if one declares the other to be malfunctioning, they can’t both be good. Either one of the two Gizmos is functioning and correctly identifies that the other is malfunctioning or at least one is malfunctioning and lying about the other’s status.
In this case, we cast both A and B aside and know that we have discarded at least one broken Gizmo. Next we test two of the three remaining Gizmos, C and D. If they both report that the other is functioning, you can buy either one. They are both good: We know that there is no more than one malfunctioning Gizmo in the C and D pair because we discarded the other malfunctioning Gizmo after the first test. If C were broken, then D would tell us as much, and vice versa.
If instead either C or D reports that the other is malfunctioning, then we know there’s a bad Gizmo in the duo, and we discard them both. We’ve now discarded the two malfunctioning Gizmos and can safely buy the fifth one without needing to test it.
Case 2: Gizmos A and B both report that the other is functioning. This could either mean that A and B are both safe or that A and B are both malfunctioning and giving us bad intel. Test C and D next. The first possibility is that C or D accuses the other of malfunctioning, which would mean that there is at least one broken Gizmo in that duo. This means that A and B cannot both be broken and are therefore both safe to buy. The other outcome is that C and D both say functioning. There are only three functioning Gizmos, so either A and B are both lying or C and D are both lying. It doesn’t matter which situation is true. You will buy the untested fifth Gizmo, which must be functioning because you have already discarded the two malfunctioning ones.
We’d love to hear from you! E-mail us at games@sciam.com to share your experience.