Reading the Comics, June 21, 2019: I Have An Anecdote Edition


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.

Caption: Chuck flunks out of Lemming University. Class of lemmings; there's a whiteboard full of symbols. Chuck, thinking: 'I'm not following *any* of this.'
Dave Blazek’s Loose Parts for the 19th of June, 2019. When I have something to write about Loose Parts the result should be at this link.

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?

An engineer, a physicists, and a mathematician are roommates moving to a new place. As the mover pulls up the mathematician worries there isn't enough room. The mover reassures them. Mover: 'I been at this 30 years. I can look at any amount of stuff and instantly tell ya if it can fit in the moving bins.' The engineer says ... 'It's obvious it can fit. Anything that doesn't go in the bins can be taped to the roof.' The physicists says ... 'It's obvious it can fit. If it were the density of a neutron star, our stuff would be the size of a baseball.' The mathematician says ... (groveling before the mover) 'PLEASE DON'T HACK MY E-MAIL!'
Zach Weinersmith’s Saturday Morning Breakfast Cereal for the 21st of June, 2019. I don’t always write about this strip, but when I do write about Saturday Morning Breakfast Cereal, the essay should appear here.

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.

In class; '8 + 4 + 7 + 5 =' is on the blackboard. Teacher: 'Skippy, will you come up and set down the answer?' Skippy: 'But I don't know it, Miss Larkin.' Teacher: 'Surely, Skippy, you're not going to give up that easily. Come up and put down something at least.' Skippy: 'Yes, Miss Larkin.' (Skippy puts a big '?' on the right-hand-side of the equation.)
Percy Crosby’s Skippy for the 21st of June, 2019. It originally ran, looks like, the 9th of February, 1932. Essays featuring Skippy should be at this link.

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.

Horace in bed, counting sheep jumping a fence: XXXXVII, XXXIX, and then, puttering along in a golf cart instead of leaping the fence, XL.
Samson’s Dark Side of the Horse for the 21st of June, 2019. And I don’t always write about this comic either, but when I do write about Dark Side of the Horse I make an essay that should appear at this link.

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.

Advertisements

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there. He/him.

One thought on “Reading the Comics, June 21, 2019: I Have An Anecdote Edition”

  1. ‘ Often a difficult problem turns out to be solved by solving a circle of simple problems, that starve out the hard.’ So well put that it’s just occurred to me this could have wider applications than mathematics – this word written in full to avoid the math/maths dilemma.

    Like

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.