A couple years back we needed to patch a bunch of weak spots in the roof. We found all the spots that needed shoring up and measured how long they were, and went to buy some wood and get it cut to fit. I turned over the list of sizes and the guy told us we’d have to buy more than one of the standard-size sheets of plywood to do it. I thought, wait, no, that can’t be, and sketched out possible ways to cut the wood and fit pieces together. Finally I concluded that, oh, yes, the guy whose job it was to figure out how much wood was needed for particular tasks knew what he was talking about. His secret? I don’t know. What finally convinced me was adding up the total area of the wood we’d need, and finding that it was more than what one sheet would be.
Dave Blazek’s Loose Parts for the 19th uses a whiteboard full of mathematics as visual shorthand for “some really complicated subject”. It’s a good set of mathematics symbols on the whiteboard. They don’t mean anything in the combination shown, though. It’s just meant to bewilder.
Zach Weinersmith’s Saturday Morning Breakfast Cereal for the 21st is bewildering, unless you know what the mathematics principle the joke intends to present. This is what I’m here for.
The key is the Mover’s claim that he can look at any amount of stuff and tell you whether it fits in the moving bins. Working out something like this is a version of the knapsack problem. The knapsack problem is … well, the problem you imagine it might be, if someone told you “some mathematicians study a thing called the knapsack problem”? That’s about right. Formally, it’s about selecting from a set of things of different value. How hard is it to pick a subset of things with exactly that value? Or find that there is no such subset?
Well, in a sense, not hard at all. You can just keep trying combinations. Eventually you’ll either find a set that works, or you’ll try every possibility and find none of them work. This is known as “exhaustion”, and correctly. If there are ten things, there are 3,628,800 possibilities. Then it gets really bad. If there are twenty things, there are 2,432,902,008,176,640,000 possibilities. Finding the one that works? That could take a while.
So being able to tell whether a collection of things can fit within a particular space? That’s a form of the knapsack problem. Being able to always solve that any faster than just “try out every combination until you find one that works”? That would be incredible. The problem is hard. That’s a technical term. It means what you imagine it means, but more precisely.
So why the mathematician’s response? It’s because the problem of hacking the common Internet security algorithms is also hard. (I am discussing here how difficult hacking would be if the algorithm were implemented perfectly. There are many hacking techniques available because of bugs. Programs are not written perfectly. Compilers do not translate them to computer code perfectly. Computers are not built perfectly. These and more flaws make hacking more possible than it should be.) It’s the same kind of hard as this knapsack problem. I mean “the same” more technically than you might imagine. If you had a method to quickly solve this knapsack problem, then, you could use this to break computer encryption quickly. And, it turns out, vice-versa, so at least there’s some fairness to things. So if the the Mover can, truly, always instantly tell whether a set of things fit in the moving bins, then hacking e-mails should be possible to. The Mover would have to team up with a mathematician who studies computational problems like this. I don’t know how to do it, myself. I think about the how to do this and feel lost, myself.
So is the Mover full of it? Let’s put this more nicely. Is he at least unduly optimistic about his claims?
Nah. What makes the knapsack problem hard is that you have to find a solution that quickly finds answers for every possible set of things. But the Mover doesn’t have to deal with that. Most of the stuff is in boxes. It’s in mostly simple polygonal shapes. There’s not, like, 400 million items, each the size of a Cheerio. The Mover may plausibly have never encountered a set of things to move where he couldn’t tell whether it fits.
And, yes, there’s selection bias. Suppose he declared that no, this load had to fit into two vans. But that actually a sufficiently clever arrangement would have let it fit in one. Who would ever know he was wrong? He’d only ever know his intuition was wrong if he declared something would fit in one van and, in fact, it couldn’t.
Percy Crosby’s Skippy for the 21st is a student-at-the-board problem. It’s using the punch line that “I don’t know” might be a true answer to any problem. There are many real mathematics problems for which nobody really knows an answer.
But Miss Larkin has good advice here. Maybe you don’t know the final answer. But do you know anything? Write it down. It’s good for partial credit, at least. Working out a part of the problem might also be useful, too. Often you can work out how to do a hard problem by looking at a similar but simpler problem. If Skippy is lost at 8 + 4 + 7 + 5, could he do at least 8 + 4 + 7? Could he do 8 + 4? Maybe this wouldn’t help him get to the ultimate answer. Often a difficult problem turns out to be solved by solving a circle of simple problems, that starve out the hard.
Samson’s Dark Side of the Horse for the 21st is the Roman Numerals joke for this time around. I’m not sure this whether this is a repeat. The strip does a lot of Roman Numerals jokes, and counting-sheep jokes.
Our roof patches held up for their need, which was just to last a couple months while we contracted for a replacement roof. And, happily, the roof replacement got done speedily and during a week that did not rain. (Back in grad school the apartment I was in had its roof replaced on a day that, it turns out, would get a spontaneous downpour halfway through. My apartment was on the top floor. This made for an exciting afternoon.)
This wraps up the past week’s comics. There weren’t any that mentioned mathematics more fleetingly than Dark Side of the Horse did. A new Reading the Comics post should be at this link on Sunday. Thank you for reading along.