Thursday, December 31, 2015

Monte-Carlo Battleship!

I’m going to do something a little different in this post, which is geared more towards grown-ups who like playing around with programming and recreational mathematics. Even so, there might be some good stuff here for kids who are comfortable with some programming basics. Instead of a problem set, I thought I’d tell you about a random bit of modeling I ended up doing over the holiday that you might have fun playing with too. One of the things I think is great about learning how to write code is that it gives you the tools to chase down lots of fun questions and see how different kinds of system work by building them and then changing things around. In this post, I’m going to tell you about my efforts this past week or so to learn some things about a system I bet you’re familiar with.

My daughter got a Battleship set for Christmas just a few days ago after learning how to play the game at after-school daycare. Before we got this for her for Christmas, I made up a bunch of paper-and-pencil versions we could use to play at home (You can download a PDF of these here, if you like). Like any game, the finer points of strategy took some time to impart, and she’s still working out how to plan her missile shots to efficiently search the grid. The game also can take a fair bit of time (and a lot of disappointing missed shots) to complete, so like we’ve done with other games, I’ve occasionally introduced some changes to speed things up just a bit. These have included: (1) A smaller board (8x8 rather than 10x10), (2) 2 shots per turn rather than 1, (3) Different ship sizes. One of the nice things about the paper-and-pencil version is that you can invent whatever sizes and shapes of ships you want, which makes these changes very easy to implement.

Playing (and talking through) the game with her a bunch of times, the different formats we invented got me thinking about how this simple system works and what you, the player, might want to know about it. Board games as simple as this one are kind of fun to poke at this way because you can usually see your way to some aspects of the game’s structure by either writing some expressions that describe how the game works formally, or when all else fails, writing some code that helps you understand some aspect of the game.

For Battleship, I decided to tackle a straightforward question Blaise and I face every time we play: Where should you take your first shot? How does that depend on the size of the board and the ships that are available to place on the grid?

The answer certainly will depend on whatever biases human opponents have for placing ships on the grid. There are probably some general factors that come into play, like the fact that most people have a left visual-field bias that affects a lot of different tasks. There are also probably lots of individual differences as well: Do you really like to put ships on the edges? Do you like to bunch everything up in one place? Do you hate/love using the corners? What these biases are could be it’s own fun problem to consider, but for now we’re going to act like they don’t exist. This way, we can start to develop a kind of simulation called a Monte-Carlo model that will let us understand some things about Battleship and how to plan your first shot.

What is a Monte Carlo model? Basically, it’s a way of simulating a probabilistic system by making lots of random draws and keeping track of what happens each time. For example, suppose you have 10 coins you want to flip and you want to know how often you’ll get exactly 3 heads – that’s something you can work out analytically, but if you didn’t know how (or just didn’t want to), you could also just flip the 10 coins lots of times and see how often you got 3 heads. That latter approach is more or less what we’re doing in a Monte Carlo simulation: Given a random process, we “draw” an outcome and record what features of the outcome we care about so we can estimate properties of the system that we’re interested in. While this strategy has been around for a long time, the advent of computers capable of doing the random draws and multiple iterations for us meant that MC simulations became much more widely used in the mid 20th century. To my knowledge, a mathematician named Stanislaw Ulam (who is a fascinating person to read about) is responsible for developing modern MC approaches, which he and others including John Von Neumann and Enrico Fermi used to examine issues in nuclear physics arising from the Manhattan Project. This was a case where they really didn’t know how to write down deterministic equations to explain the systems they cared about, so simulating them with random draws was about the only way forward.

OK, so how do we use these methods to talk about Battleship? First, let’s define what we want to know: Where should we take our first shot? I’m going to rephrase this as, “How likely is it that any given square will be occupied by a ship?” After all, if a square isn’t likely to be occupied, we wouldn’t want to waste time shooting at it. Second, let’s define how we think this system works in terms of a random process. Here are the rules I’ll use for our Battleship simulations:

1) There are five ships. One ships takes up 2 squares, two ships take up 3 squares, one ship takes up 4 squares, and one ship takes up 5 squares.
2) No square may be occupied by more than one ship (no overlap).
3) The ships are placed on a 10x10 board.
4) The ships are placed randomly by the opponent. For each ship, each legal ship position is equally likely to be selected.

Note: It’s really rule #2 that makes things a little tricky to compute deterministically, since the placing of one ship constrains the possible positions of the others.

So now what? The next step is to write code that allows us to randomly arrange the 5 ships for a single game and record where they were positioned. Here’s a picture showing you what a single game looks like using code that implements the four rules above.

Now that we can do this, we run that code thousands of times, keeping track of the ship positions for each simulation. When we’re done, we’ll count up how often each square was occupied across all of our thousands of random games. The result is a map of the game grid, with a number in each square telling us how often that square was occupied across the whole set of simulations. When I tried it out with 10,000 iterations, I got the following map:

What do we see? Well, it’s definitely a good idea to shoot for the center, but we can even say roughly how good an idea it is relative to other spots. For example, the center squares are occupied about 3 times more often than the corner squares! That’s not a bad thing to know about the game, and it all comes from the constraints placed on ship positions imposed by our rules.

My guess is that at this point this basically matches your intuitions about the game, so you may not be very impressed. Sure, we got some quantitative data about the relative merits of the center vs. the other locations, but how big a deal is that? Arguably, not much of a big deal, but the real fun starts by messing with those rules and seeing how things change. See, I wrote all my code so I can manipulate the size of the board, and the size and number of ships and do all this over again. Let’s see how the maps change when we use a smaller board (9 squares and then 8 squares).

The same overall structure, but the absolute numbers change a good bit (note that the ~3:1 ratio for center vs. corner is roughly preserved, though). What about changing the ships? Let’s see a version where we only have ships that are 4 squares long:

Now let’s compare that to what happens if our fleet is only made up of ships that are 6 squares long:

Check out that cross shape! The center isn't really favored any more than the arms of the plus sign - see if you can figure out why this changed the way it did intuitively.

There’s tons of other stuff you can do with this little game by simulating different scenarios, and these are nice ways to see how some candidate rule changes might make the game more or less fun. What if you introduce squares that can never be occupied? How about ships with different shapes? What if you make your game toroidal by letting ships “wrap around” the edges of the grid? Suppose we let the “no overlap” rule go? There are lots of possibilities to explore, and an MC simulation lets you quickly get some insight into how they work.

That’s the end of my grown-up post, and I hope you found it at least somewhat fun. I really think learning how to play with mathematical objects opens the door to lots of great ways to explore ordinary stuff, and hopefully this was a good example of why I think that’s fun to do. Please feel free to play with the code yourself, and I’ll try to develop a few more posts about similar topics. Thanks for reading, and happy modeling!

Tuesday, December 29, 2015

Free books!

This isn't a new problem set, but I thought this was too good to not post here. Springer has made a large number of graduate and undergraduate mathematics textbooks available for free! Obviously these are for grown-ups who want to learn more mathematics rather than kids, but go get yourself some PDFs if you want to brush up on just about anything!

Stay tuned for another non-problem set post about some adventures in monte carlo modeling!

Friday, December 18, 2015

Ice Skating (approximately)!

Link to PSet
Answer Key: Pending

It's been a while since I posted a new problem set (and I still owe everyone an answer key for HW8), but hopefully I can make up for that with the return of Boofernaut and Boofinski. This time, the two of them are doing some ice skating together and Boofernaut is trying to figure out how to make the best copy (or approximation) that she can of the paths her brother makes on the pond.

The goal of this assignment is to get kids thinking about how to make a model of something complicated with simpler tools. We tackle this in one dimension by trying to make piecewise-linear approximations of curved paths and then in two-dimensions by using LEGO bricks to make a model of a closed contour. In both questions, we ask kids to think about what changes in their approximations as they get to use a lower vs. higher resolution model (more lines in 1D, or making the shape bigger/smaller in 2D) as well as how they decide what approximation is the best. How do you choose what details to leave out and which ones to model?

I also ask kids to think about the "inverse problem" in each case: If you only have the approximation to start with, what do you think the original curve or shape was? This is particularly fun because there is definitely not just one right answer - there are endless original curves that could lead to the same simpler model. Inverse problems are everywhere in science and mathematics (we deal with them in my lab when we try to use EEG measured on someone's scalp to make guesses about where in the brain activity is coming from), and hopefully this is a nice introduction to the challenges of making inferences from sparse data.

We ask you to use some LEGO bricks to solve the second set of problems here, so I thought I'd include a link to one of my favorite 3D shape approximations - the LEGO sphere! The instructions at this link are not mine, but we did manage to follow them a while ago to make a pretty sweet approximation of a half-dome out of standard bricks (we didn't have enough unused bricks to make the whole thing). Enjoy!

Friday, November 6, 2015

Adding Arrows!

Link to PSet
Answer Key: Pending

You know what we're doing a lot of in first-grade math at school? Adding small numbers. Over and over and over again.

Needless to say this is wearing a bit thin already, so I thought we could extend addition a bit by introducing vector addition in this problem set. If you've ever worked with vectors, you know that all we're really doing is adding numbers in two dimensions, but my thought here was that this was a nice way to start developing intuitions for how to alternate between geometric and algebraic viewpoints. We talk a bit in this problem set about how to develop a notation for vectors that will allow us to work with them algebraically, but most of the actual questions are about drawing vectors in the plane.

Compared to some of the other Psets, this one is likely to be a bit easier, but hopefully still interesting. I'm still working on finding the right level of difficulty and the right level of fun stuff to do, so if you've been working through any of these with your kids, I'd love any thoughts about what kinds of questions have been the most fun to work on. Enjoy!

Monday, October 26, 2015

Halloween Geometry

Link to PSet

Since Halloween's nearly here, I thought a problem set with some spooky shapes would be fun. There's no answer key for this one because these are more like exercises than real problems: We walk through two fairly simple compass and straightedge constructions to make some Halloween-y moons and ghosts that have some special properties. If you end up making either of one of these (or both) feel free to send them my way and I'll post some student images here on the site!

A practical note: I suggest in the PS that you may want some graph paper for Exercise 2 in particular. If you don't feel like buying yourself a whole pad, you can find some patterns to print out a sheet at a time here. This site also has hexagonal graph paper and some other fun options we may use in later problem sets.

We're really only introducing two new topics here, but they may lead you to some fun ways to play around with Euclidean constructions. Once you know how to bisect lines and arcs, there's a lot of neat stuff you can do to play around making symmetrical shapes of your own design. Those shapes may also be a fun starting point for making your own tessellating shapes, per Exercise 2. I don't really talk about tesselations in depth here (I figured this could be more of a "follow-the-steps" kind of problem set), but we'll almost certainly return to them in future assignments and talk about their properties in more detail. For now, I'd say that trying to work out why the ghost works (especially how his final zig-zag needs to be drawn) is a good way to build some intuitions about tesselations.

If you like tesselations (and who doesn't?), you may want to try playing around with the two shapes below, which are called the "Kite" and the "Dart." These are prototiles for an aperiodic tiling of the plane, which means that try as you might, you won't be able to come up with a way to make a repeating pattern with these.

If you want to find out more about aperiodic tiling, go check out the wikipedia page for Penrose Tiling, which will point you to more fun ways to cover the plane. Happy Halloween, and happy constructing!

Sunday, October 18, 2015

Cookie Cutting in HW5!

Link to PSet
Link to Answer Key.

In this assignment, I've decided to go back to some problems that are more geometric and encourage kids to play with making (and breaking) shapes. You may find that you want either a compass or a small circle stencil for some of these problems...I found a pretty handy stencil for about $2, and they're are fun things to play with that may come up again in future problem sets. If you're really stuck, however, coins of different sizes would probably do the trick.

My main goal in these problems was to give kids an excuse to experiment. To that end you'll find two worksheets worth of "cookies" to chop up in whatever way you like, and I'd definitely say that trying out different kinds of shapes (especially concave vs. convex shapes) is a great way to extend what's going on here.

Finally, if you want to read more about cutting up pastries for the sake of mathematics, Martin Gardner's article about cutting up a real donut is quite funny (especially the reader mail from people who tried to do it and found that real donut-cutting is heavily constrained by the crumbliness of actual donut matter).

Friday, October 9, 2015

Alternate Q2 and Q3 for HW4

Link to revised PSet

Last time I mentioned that the last two questions of HW4 seemed too hard (or at least too tedious), so I've revised those to be a little simpler. We're still asking you to think about how to count up the mismatched sets that Boofernaut can wear, but the number of colors is reduced from 5 to 4, which ought to make this easier to think through.

The last question is now one about rearranging a set of 3 colors into distinct orders, and I decided to actually give the answer but challenge students to fill in the possibilities. In general, we've found this is a decent strategy for making problems easier to attack: The uncertainty of knowing whether or not you're done is a big stumbling block sometimes.

Somewhat unrelated to the homework, but I just finished Siobhain Roberts' book "Genius at Play" about John Conway, who is an incredible mathematician who you can find lurking around the biographies of other incredible mathematicians and in lots of material about recreational mathematics. His own biography is fantastic and includes lots of great descriptions of games, puzzles, and pure mathematics.

Saturday, October 3, 2015

Notes from the field, HW3 and HW4 suggestions

Now that we've had a chance to work through HW3 and part of HW4 in our house, I wanted to share a few things we ran into that might be stumbling blocks for other kids.

1) In the answer key to HW3, I suggest that kids might try to figure out the pattern for how many socks Grufftina needs to pull out depending on the number of colors. This part is pretty straightforward: She needs to grab a sock for each color in the drawer and then one extra.

The last part of this question suggests that maybe we could come up with a rule even if we don't know the actual number. In the text, I wrote this down as Grufftina having "n" colors in the drawer, and I was looking for kids to come up with the idea that whatever "n" is, "n+1" socks will do the job here. This turned out to be trickier than I thought it might be, mostly because my daughter was trying to sort out what "n" might stand for (maybe "nine?" maybe "ninety?")

My wife had an excellent way of breaking through this logjam, though, that I want to share here: She said that the sock monsters had some words for numbers that weren't the same as ours, so Grufftina might tell you that she has "Blorg" different colors in the drawer, but we don't know what "Blorg" means. Can you still tell her how many to pull out?

This turned out to totally do the trick, so definitely feel free to cross out my very boring "n" and do something like this instead if it helps.

2) OK, this one we haven't really run into yet, but as I was writing the answer key to HW4 it struck me that Q2 and Q3 are probably just a little too hard because of how many colors you need to keep track of. I was trying to get away from needing to talk about how you might multiply the numbers together to get to the right answer, but with 5 colors and 3 feet to think about, the tables/diagrams just get kind of big and probably annoying for young kids to deal with.

My suggestion here is that reducing the number of colors to 4 probably makes this all MUCH easier to think about. In particular, for Q2, it makes it easy to do "leave one out" reasoning about the number of different mismatched 3-sock sets with all colors different: If there are 4 colors and 3 feet that have to be all different, there's always one color left out! So leaving out each color in turn tells you that there are 4 different mismatched sets (as long as we don't care about what foot the sock goes on).

I may come up with an alternate version of the Boofernaut problem that's written this way and replaces Q3 with a question about finding all the different ways to rearrange a mismatched set on 3 feet. Stay tuned for an alternate draft in the next week or so.

If you happen to try either of these problems (or any others) and have thoughts about how to improve or simplify the questions for kids, please let me know! This is all a work in progress, so I'm very much still figuring out how to present some of these fairly tough questions so that young kids can work on them and have fun.

Thursday, October 1, 2015

Mismatching Sock Monsters! - HW4

Link to Pset
Link to Answer Key

Still more socks, but a new set of ideas in this problem set.

With the arrival of Grufftina and Boofinski's siblings, we meet some monsters who don't like matching socks. This (of course) gets us thinking about combinatorics: How many ways can we have a mismatching set? What conditions will we place on sets to be considered different from one another?

Like what we did in HW1, I think experimentation is a key feature of these problems. Actually trying to draw as many sets as you can is a good way to start, especially if you can start thinking about a strategy for how to keep track of what you've done. The core ideas about how to multiply everything together to compute combinations and permutations may be a little tough for some younger kids, but thinking about how to organize the sets of socks they draw may get across the important ideas. Answer key coming soon! UPDATED: The Answer Key for this pset is now available.

Sock Monsters! - HW3

Link to PSet
Link to Answer Key

We're leaving polyominoes behind in favor of socks!

The idea in these questions is to further introduce and extend the idea of proof. Chances are you've heard some version of the sock problem posed in Q1 and by itself it's just a different exercise in working out conditions for some mathematical object to be inevitable (here, a matching pair of socks). With the remaining questions, however, what I wanted to do is start introducing the idea of pursuing more general questions given a specific starting point. We do this by broadening the conditions that constrain the original scenario: What if the monster has more sock colors? What if the monster has more feet? What if both things are true? Besides solving these problems, thinking about other ways to generalize the question is part of what I'm hoping to get kids to do here.

I'm a little hard-pressed to think of a good supporting resource for this, but I will take the chance to mention Paul Erdos' biography "My Brain is Open." There's a bit in there where the author talks about Erdos' quest for ever more general theorems, which is really what this assignment is trying to introduce (very gently). If you haven't read about Erdos, definitely check out this book.

Building Shapes out of Polyominoes - HW2

Link to PSet
Link to Answer Key

Now that we've learned what polyominoes are in HW1, the questions in HW2 ask us to try building some different shapes out of them. We also start talking about how you can actually prove whether or not you can make a particular shape out of specific polyominoes.

The goal for these questions is two-fold: In the early questions, I wanted to encourage experimentation. The value of false starts, dead ends, and general mucking about is a good thing to learn about mathematical thinking. In the later questions, however, I wanted to try and introduce the idea that sometimes you can work something out without having to try lots of experiments. I do this here using the classic "Mutilated Chessboard" problem, which I hope is a clear enough example of a simple proof for kids to get the idea.

If you're still loving the polyominoes, you really need to get a copy of Solomon Golomb's book "Polyominoes: Puzzles, Patterns, Problems and Packings."

Intro to Polyominoes - HW1

Link to PSet
Link to Answer Key

Here is the first proper Bespoke Mathematics Problem Set! In these questions, you'll meet up with some very fun shapes called "polyominoes" which are a mainstay of combinatorial geometry. There's a TON of material about polyominoes out there and if you've played Tetris, you already know what these things are.

This problem set is mostly about teaching kids how we pick a definition for a new class of mathematical objects (establishing the "rules" for polyominoes) and getting them to play within those constraints to make new things. One thing I wanted to emphasize here is that it's okay to try out different rules, but being consistent once you've decided how you want things to work matters a lot.

For a great introduction to polyominoes, I can't think of anything better than the original Martin Gardner article about them. You can find this in the collected volumes of his work (which are unbeatable) published by the AMA. Alternatively, many places online have nice articles about these - try Wolfram or for some pointers.

Constructing a Hexagon

Link to the PSet

This is sort of the beta version of Bespoke Mathematics. Before my daughter wanted math homework in 1st grade, one of her best friends who is a few years older wanted math homework in 1st grade. I've always really liked compass and straightedge constructions, so this is just a short walkthrough of how to construct a hexagon. This is the only Bespoke Math assignment that doesn't have an answer key because it really does take you through the whole process.

If you want more cool stuff to do with constructions like this, I'd recommend checking out Robert Dixon's "Mathographics." You'll find lots of neat stuff there about how to draw an egg with a compass and straightedge, how to do string drawings, and other such things.


Welcome to Bespoke Mathematics! Here's the deal: My 1st-grader tells me shortly after the beginning of the school year that she would really like some more homework. In particular, she'd be very excited if she could finally have some math homework. If the math homework could also be less about counting and adding small numbers together, that would also be good.

The result is what you see here. This is a (growing) collection of short and hopefully fun homework assignments that I thought my daughter would like. Each one has about 3 main questions, which range from the purely fun and speculative to more sophisticated challenges. In each case, I've tried to introduce some fun piece of mathematics that kids are unlikely to see in a standard grade-school curriculum. Each homework assignment has an answer key (often with a few extra questions for fun) and I'll also try to include links to interesting supporting material as I'm able.

Please feel free to share these with anyone who may enjoy them! I'd also love to hear comments, suggestions, or ideas for homework topics. Finally, please feel free to point out any errors in the text, particular difficulties reading my somewhat spindly handwriting, or other issues with the problem sets.