After some thought, let us return to the shop to buy some matches.
What strategy should you employ, knowing that the clerk has full knowledge of your strategy?
One strategy is to buy a lot of matches and hope that the clerk hasn’t had time to ruin them all. This strategy might work in the real world, but it doesn’t work in our world. The clerk has all the time he needs to ruin any number of matches–even all of them, if he chooses to do so. You will leave the store, staggering under the burden of all of the matches, and then die at the end of your journey because none of the matches will light.
Another strategy is to buy a bunch of boxes of matches, and then carefully open each box and try the first match from each box. If the match lights, then you assume that the box was not tampered with, and that the rest of the matches in that box are good. If you run out of boxes, then you buy more. This won’t work because the clerk knows that you’re planning to try the first match in each box, and therefore makes that match the only match that lights. Therefore, having lighted the only working match in each box, you then set off into the wilderness with a box that contains 99 ruined matches, having chosen the one good match, and the die at the end of your journey because none of the remaining matches will light.
You can make things a little harder for the clerk by introducing some randomness–instead of choosing the first match in each box, choose one at random. The clerk doesn’t know which match you’ll choose, but his strategy doesn’t have to change. If he puts one working match in the box, then there are still only two possible outcomes for each box: you’ll either choose that match (and it will light and you’ll take that now-useless box), or you’ll throw away that box and try again. It’s likely that you will have to try many boxes before you draw out a match that works. The more boxes you try, the more obvious it is that the clerk is trying hard to kill you–and knows your strategy, and in the end you will eventually be fortunate, pick out the one working match, and then march off to your doom.
Every strategy that has this basic form is doomed, no matter how clever. Consider the following refinement to this procedure: buy a box of matches, select half of the matches at random, and try to light them all. If they all light, take the remaining matches. Otherwise, try the whole process again. The clerk can still attempt to kill you by filling the box with half good and half ruined matches, but the probability that you will randomly select exactly the half that light is astronomically small–the same probability as flipping a fair coin 50 times and having it come up heads every time. This will happen by blind chance one time in 1125899906842624. If that isn’t good enough for you–after all, your life is hanging in the balance–buy two boxes, pour out the contents of both into a big heap, and try to light 100. The probability of success for you (lighting 100 successfully) and success for the clerk (lighting exactly the correct 100) is now one in 1267650600228229401496703205376. In layman’s terms, this ain’t gonna happen, but if you’re very worried, or there are computers involved, you can always add more boxes of matches until the probability that the clerk will trick you successfully is as close to zero as you like.
This approach ensures that if the clerk is trying to kill you, you’ll probably never leave the store because it is extremely likely that you will catch the clerk every time he gives you a box of matches that would result in your death. You’re probably not going to die on your expedition, but you’re also probably going to die of old age in the store.
The problem is that we’re giving the clerk as many tries as he needs to get lucky and arrange things in the one way that will send you off to your doom, and since the clerk knows your strategy and therefore knows exactly how to prepare the boxes of matches so that you will either buy another box or leave the store with a box that has no working matches.
Every strategy of this sort–where we give the clerk the opportunity to provide us with only exactly enough matches to pass the test and won’t leave the store until our conditions, which the clerk knows, are satisfied–will fail. I’m going to make this claim without any proof–in the worst possible example of mathematical rigor, since I’ve only bothered to describe one type of strategy, and there are many. In this family of strategies, you’ll either buy another box (because you think the box you have is bad), or you’ll leave the store with a box containing nothing but matches that don’t work. By fine-tuning your strategy, you can make it more “difficult” for the clerk, but this just means that you have to buy a lot more matches before we stumble into the unlikely situation where you accept the box of matches that the clerk offers, and then wander off to die in the wilderness.
The fundamental problem is that we’ve designed a game with only one (eventual) outcome: going on the expedition. If that’s the only choice, and the clerk controls the matches, then we’re dead. The clerk doesn’t need intelligence or luck; he only needs patience.
At this point, it would seem like a better idea to simply abandon the expedition and stay home. In any case it would be quicker.
This insight provides the path to a solution.
Keep in mind that the clerk wants to kill you. He wants you to go on your expedition, and he will do whatever he can to make you think that you have a working match. He doesn’t want you to give up and stay home and quietly live out the rest of your life.
In order to suceed, you need a different strategy: one that gets you out of the shop in a reasonable period of time, go on your trip, with a reasonable chance of survival. Most importantly, however, you must provide the clerk with an attractive opportunity to kill you. Remember that the clerk can simply ruin every match in the store, if he chooses to do so. You might be able to detect that he’s done this, but there’s no way to prevent it. You want to give the clerk an incentive–specifically, the opportunity to kill you–to leave some of the matches in working order, and you want to come up with a test for whether there are any working matches that is unlikely to consume all of them.
Buy some number of boxes of matches–let’s say 20. After they are safely in your possession (and can’t be modified by the clerk), divide them into two piles by flipping a coin for each box. There will be approximately ten boxes in each pile; if chance is against you and there are only a small number of boxes in one pile, start again. Open all of the boxes in the heads pile and try to light matches until you either find one that works, or discover that they are all ruined. If some number of the boxes (i.e., 5) in the heads pile contain a working match, take the tails boxes with you on your trip. Note that there’s no point in taking the remnants of the heads pile–you might have used up all of the good matches; there might have only been one good match in each box. If any of the boxes in the heads pile do not contain at least one working match, stay home. Don’t go on the trip. Once you’ve purchased the 20 boxes, the game is essentially over from the perspective of the clerk; you won’t buy any more boxes, no matter what the outcome is.
In order for the clerk to kill you, he needs to guess correctly which boxes will be in the heads pile (and put at least one good match in five of them) and which boxes will be in the tails pile (and put no working matches in any of them). This is possible, but unlikely, and if the clerk attempts it then what is far more likely is that at least one of the boxes containing a working match will end up in the tails pile. Since this is the clerk’s one and only chance to kill you, he will need to prepare enough boxes of matches that contain at least one good match that you’ll be confident that it’s safe to go on your trip (or else he’ll lose his chance to kill you), and he’ll have to be very lucky (or else you’ll end up with at least one of the working matches).
I won’t work through the probabilities that if there are twenty boxes and only five of them contain working matches that all five will end up in the heads pile, but you can do it for yourself and explore how the numbers change if you use larger numbers of boxes, different success criteria, or a biased coin. You can make the probability as high as you like that if you leave the store thinking that you probably have a working match, that you actually do, and decrease the probability that you won’t stay home if you actually have a good match. You can’t eliminate the possibility that the clerk will be lucky and you’ll end up dead, but then again the arctic is not without its perils.
If you think about it long enough, I’m sure you’ll find a better solution.
