The Mathematics Behind Xkcd

The Mathematics BehindxkcdA Conversation with Randall MunroeTLaura Taalmanhis past April, MathHorizons sat down withRandall Munroe, theauthor of the popularwebcomic xkcd, to talkabout some of his most mathematical comics. We met at ChristopherNewport University, Randall’s almamater, where he was about to give aninvited talk to a packed auditoriumof fans. (You can see his ChristopherNewport address online at www.youtube.com/watch?v 3XctkVYvY0c.)Tic-Tac-ToeMath Horizons: Let’s start with one ofyour most complex comics, the mapof tic-tac-toe moves.Randall Munroe: I remember that—I have a callus in my handfrom making it. I think I drewmaybe a fifth or a sixth of theactual chart by hand, and thenput that in the computer andmirrored and flipped it, andpieced together the rest of it.It took me something like 12hours to draw out the fifth of itthat I did. There was no way Iwas doing the rest of it by hand!MH: How come you didn’t start withX in the middle?RM: Because it doesn’t matter. Withevery opening move for X it’s goingto be a draw if you move optimallyfrom that point onward. Part of whatstarted this off is that I had tried doing these maps when I was in Englishclass in 11th grade, sitting there andworking out a tree fordid the calculations, andwhen I realized that formost of tic-tac-toe, and Ithe full tree I would needhad sort of taken it as ana piece of paper that wasarticle of faith that thebigger than the diningbest move for X is in theroom table, I thought,center. The reason I wentI’m not drawing that!for the upper-left openingI was trying to figuremove in this comic wasout if there was a waythat with this one, thereto present the informaare some winning movestion so that at everythat aren’t the ones thatRandall Munroestage you are makingeveryone knows.a choice on a grid of nine possibiliMH: So you wanted to go with a lessties. It seemed like there should becommon opening move?some way to present the data whereRM: Yes. I was looking for movesmaking the choice is just zoomingwhere you can force a win, and youin on the grid or something, and Ican do it in a way that isn’t obvious.wound up doing what you see in theThe thing that was interesting for mecomic. It’s a way to organize thathere was the moves that take into acmakes it so you can quickly shadecount psychology and the places thatin, for example, all the winsfor X, and you’ll be able to seewhether there are a lot of themor only a few. At the very least,it looks pretty.MH: It’s so efficient, likeEdward Tufte’s Visual Explanations book.RM: Yes, Tufte’s real focus is always to convey the informationwith as little ink as possible. Ilike that the tic-tac-toe comic didn’tpeople are least likely to see that ahave a lot of extraneous stuff. I didwin is forced.put in some boxes, and that helpedMH: What gave you the idea towith visually organizing the boardspresent the information in this way?a little, but the presence of a box,People have made these trees before,even, tells you something: It tellsand some of them are quite compliyou if that’s an end-board state. Thecated, but you managed to fit it allconsequence of using boxes only forin one page.the end states is that, not countingRM: The full tree of possible moveswould be a lot bigger than this. Ithe big boxes around each panel,I really enjoy solving thesekinds of things, and it’sa bonus if I realize thatI can put boxes around itand make it a comic.www.maa.org/mathhorizons : : Math Horizons : : September 2012 5

you never have a box inside anotherbox. This means that you don’t havethe problem of nested boxes for eachstate that would quickly eat up all ofyour space with margins.Self-DescriptionMH: Another one of your comicsthat fascinates math people is theself-referential one where each paneldescribes the amount or location ofblack ink in itself and other panels.Various people have analyzed thiscomic by writing code to iterate andget your comic as the fixed point.(Readers can see one example usingMathematica, by Jon McLoone, atblog.wolfram.com/2010/09/07/selfdescription/.) Is that how you foundit, or did you find it another way?RM: I found it another way. I didn’tactually write any code for this. Istarted off thinking about the piechart in the first panel. I was tryingto figure out what other charts theremight be that don’t disintegrate tonothing.That was the problem; there arecertain charts or plots whose fixedpoints are zero. Like a situationwhere one chart was referring to another, and the other to the first, andyou end up with an equilibrium statewhere both graphs are empty.And you don’t need a computerprogram to figure that out. You justsort of think, OK, well, if this graphis right for the one I’ve drawn now,and I make it a little smaller, howdoes the other one change?And so just thinking about it, Irealized that the three ideas in theOn this page and the facing page: The only winning move is to play, perfectly, waitingfor your opponent to make a mistake.panels would work; they’d all havea reasonable amount of black inkin each one, which would make themiddle chart work, and so on.MH: How did you determine howmuch black ink to put in each of thecharts?RM: I figured out how to measureeach of the quantities shown in“Self-Description,” Randall Munroe, http://xkcd.com/688/The contents of any one panel are dependent on the contents of every panelincluding itself. The graph of panel dependencies is complete and bidirectional,and each node has a loop.6 September 2012 : : Math Horizons : : www.maa.org/mathhorizonsthe charts. I drew up the outlinesin Photoshop, added the captions,drew in eyeballed estimates, andthen used some utilities to countthe number of pixels.Photoshop will tell you how manypixels are in this area, if you selectin a certain way, and I’ve been pixelpainting in Photoshop forever. Ijust wrote down the numbers, useda calculator, and calculated for thefirst two panels: What should theheight of the bar graphs and theangle of the pie chart be?The third panel I generated byjust taking the image and cloningand shrinking it. I had a big sheetof paper to keep track of the math,and I was just doing it all by hand.

“Tic-Tac-Toe,” Randall Munroe, http://xkcd.com/832/MH: Wow, you iterated it by hand?How many times did you have toiterate?RM: Yeah. I think there were about10 or 12 iterations, which reallyisn’t so bad if you compare it to theamount of time it would have takenme to write the code, which I wouldhave had to learn things to do partsof it.For example, I don’t know of alibrary for pulling in an image anddoing things like that, so I’d be justreading in a bitmap and then using itas an array and—I never rememberhow to do half that stuff, you know,whereas I did know how to measuresize in Photoshop, and I knew I hadsome paper there. I always go for thelazy solution that doesn’t require alot of new stuff.I draw the comics at somethinglike 10 or 15 times the resolution thatthey are online, and after just 10 or12 iterations, it was getting to wherethe image wasn’t changing enoughthat it would make a real difference.It would just be like a slight difference in the gray at the top of one ofthe lines on the bar graph. It got tothe point where it was like staying within a pixel—and it got therepretty quickly.MH: Did this one take you more timethan the tic-tac-toe comic?RM: This one took less time, I think.I started in the afternoon, and it wasmaybe five hours or something. Ithink this one went up on time. Fivehours isn’t a lot of time in terms ofhow much time a job normally takes.They take longer than they look,because I write out all the dialogueby hand, and I do it in pencil oncejust to make sure it is all in the rightplaces, and then I’ll do it again, andthen I scan it in, and then I processit.Usually for a really simple comicthat I know the script and I knowwhat the joke is, I tend to set asidetwo or three hours. If I have to workout the wording, or other things,then four hours. So this one tooklonger than usual, but not ridiculously. Not as long as some of theother ones.MH: Do you think the solution isunique? For example, is it possiblethat there is a larger pie you coulddraw here that would be part of adifferent fixed point, if you iteratedit?RM: No, I think this is a unique solution. Look at the limit case for all ofthese—say, if you color the pie chartin all the way. For the second panel,the overall scale is sort of arbitrary,but even if you had a scale and thefirst two bars were all the way up,the third bar is constrained; onceyou’ve set two of them, you’ve constrained the third. Even in this limitcase, your very first iteration willtake you to something that looks alot like the final comic, because evenwhen you’ve shaded in all of the piechart, this is still basically a whiteimage.MH: Do you think it’s possible tofind this fixed point without iterating? Maybe algebraically?RM: Yeah, I think it’s totally possible. One thing that I really likedabout this is that every paneldepends on the state of every otherpanel and on itself. Which is why,when I hit on these three panels,that I stuck with those choices. Iliked that there was nothing thatwww.maa.org/mathhorizons : : Math Horizons : : September 2012 7

“Movie Narrative Charts,” Randall Munroe, http://xkcd.com/657/In the Lord of the Rings map, up and down correspond LOOSELY to northwest and southeast, respectively.you could set and say OK, now I’vesolved this part, I’ll figure out therest of it from there. Everythingdepends on everything. Solving italgebraically, I feel like it could be ahard problem.When people look at these comics, they always assume, oh, the guythat drew this must have done allthat. But for me, I just found a coolway to get to the result that skips allthat, even if it’s not as general or satisfying. People tend to assume thatI’ve done whatever the most expertway of getting to it is, and so theyassume that I know a lot more aboutthe subject than I do.MH: Although iterating it by hand is. . . pretty badass.RM: There’s a lot of stuff for a lot ofthe things that I do that look coolerthan they are, because no one wouldhave thought to do something thatboring.MoviesRM: For example, I did a big chartof movie narratives. That was oneof my favorites, that was one thatwas fun to do. And I didn’t use acomputer at all in that.MH: Did you have to watch the movies over and over again to get thatright?RM: That’s kind of the embarrassingpart . . . once or twice I fact-checkedmyself on the Wikipedia article forLord of the Rings, but I’ve seen thosemovies a lot. I pretty much just satdown and drew that by hand. Ittook me a couple of days, but whenI show that to someone, people willsort of respond by saying, “OK, Iguess you could do a program; youcould download a copy of the script,and then do a language parser, figureout who’s talking to who, that’lltell you who’s near who, and thenyou get the rules for how to makethe lines go back and forth to each8 September 2012 : : Math Horizons : : www.maa.org/mathhorizonsother”—they’ll come up with thisidea, but no one would implementthat because that is a lot of work!But it turns out that just doing itby hand is totally doable if you havea weekend free. And if your job ismaking pictures like this. So it’s noteven that I figured out somethingclever. It’s just I have the patience todo the thing that no one would thinkof, or that anyone would ever botherto do. And sometimes that’s key. It’sjust like I have that much free time.MH: That sounds like a good life.RM: Well, it’s fun. And it’s fun when Ihit on something like this. I really enjoysolving these kinds of things, and it’s abonus if I realize that I can put boxesaround it and make it a comic.NP-CompleteRM: On the other hand, there areother comics that it might surpriseyou how much code I wrote for them.For example, there was one that in-