Combinatorial Games, Redistricting Game, and Graph Music

Welcome to this week’s Math Munch!

Have you ever played tic-tac-toe? If so, maybe you’ve noticed that unless you or your opponent makes a bad move, the game always ends in a tie! (Oops– spoiler alert!) Why is that? And what makes tic-tac-toe different from other games that have unpredictable outcomes, like Monopoly or the card game War?

strategy-for-x

We wrote about tic-tac-toe in this post! Click to learn more.

Tic-tac-toe is similar to other kinds of game that mathematicians call combinatorial games— or games where there is no chance involved in the outcome and neither player has information that the other one doesn’t. This means that depending on who starts, where they go, and where each player decides to go next, the outcome is completely predictable and everyone playing could know what it is before it even happens. No surprises!

Now, this might also sound like NO FUN to you (why play the game at all if everyone knows what’s going to happen?) but I think it introduces a new kind of fun– figuring out what the outcomes could be! One of my favorite combinatorial games is the game NIM.

NIM 1

Here’s an example of a starting NIM board. If you go first, can you win? (Assuming your opponent never makes a mistake.)

NIM is a two-player game. You start with several piles or rows of objects (here they’re matches). On each turn, a player removes some objects from a pile– any number they want. BUT the player who’s forced to remove the last match loses!

 

There’s no chance in NIM– no dice determining how many matches you can remove, for example. Also both players know the rules and how many matches are in the piles at all times. That means that if you thought about it for a while, you could figure out who should win or lose any game of NIM. Maybe playing the game NIM isn’t super fun– but thinking about it like a puzzle is!

More versions of online NIM can be found here and here. And to read about combinatorial games we’ve written about in the past, check out this interview with mathematician Elwyn Berlekamp!

Next up, it’s presidential election time here again in the U.S.! Did you know that there’s a lot of mathematics behind what makes elections work? Four years ago, before the last presidential election, we shared a great series of YouTube videos about the math of elections.

redistricting game

A map in the redistricting game.

A big way that math gets involved in elections is through how politicians decide to draw districts, or regions of states that get to elect their own representative to the House of Representatives and elector to the Electoral College. The math behind drawing districts ranges from simple arithmetic to graph theory, or the field of math that deals with how parts of a shape or diagram are connected. To learn more about drawing election districts and the math behind it, check out the Re-Districting Game! In this game, you play the part of a map maker who works with the Congress, governor of your state, and courts to make a district map that meets everyone’s needs.

Finally, I recently ran across a series of graph music videos! What’s that? Videos in which a graph (made on Desmos) dances along to music, much like people would in a regular music video. Here’s one of my favorites:

The equations on the left-hand side of the screen create the images you see and the rhythm of the animation. Want to make your own graph music video? Share it with us!

Bon appetit!

Halving-Fun, Self-Tiling Tile Sets, and Doodal

This post comes to us all the way from June of 2014! Enjoy this blast from the past!

Welcome to this week’s Math Munch!

Print out two copies of this pattern, cut them out, and fold each along the dotted lines, making two identical solids. Then fit these two pieces together to make a regular tetrahedron.

Print out two copies of this pattern, cut them out, and fold each along the dotted lines, making two identical solids. Then fit these two pieces together to make a regular tetrahedron.

Our first bit of fun comes from a blog called Futility Closet (previously featured). It’s a neat little cut-and-fold puzzle. The shape to the right can be folded up to make a solid with 5 sides. Two of them can be combined to make a solid with only 4 sides, the regular tetrahedron. If you’d like, you can use our printable version, which has two copies on one sheet.

What do you know, I also found our second item on Futility Closet! Check out the cool family of tiles below. What do you notice?

A family of self-tiling tiles

A family of self-tiling tiles

Did you notice that the four shapes in the middle are the same as the four larger shapes on the outside? The four tiles in the middle can combine to create larger versions of themselves! They can make any and all of the original four!!

Lee Sallows

Recreational Mathematician, Lee Sallows

Naturally, I was reminded of the geomagic squares we featured a while back (more at geomagicsquares.com), and then I came to realize they were designed by the same person, the incredible Lee Sallows! (For another amazing one of Lee Sallows creations, give this incredible sentence a read.) You can also visit his website, leesallows.com.

reptile3

A family of 6 self-tiling tiles

For more self-tiling tiles (and there are many more amazing sets) click here. I have to point out one more in particular. It’s like a geomagic square, but not quite. It’s just wonderful. Maybe it ought to be called a “self-tiling latin square.”

And for a final item this week, we have a powerful drawing tool. It’s a website that reminds me a lot of recursive drawing, but it’s got a different feel and some excellent features. It’s called Doodal. Basically, whatever you draw inside of the big orange frame will be copied into the blue frames.  So if there’s a blue frame inside of an orange frame, that blue frame gets copied inside of itself… and then that copy gets copied… and then that copy…!!!

To start, why don’t you check out this amazing video showing off some examples of what you can create. They go fast, so it’s not really a tutorial, but it made me want to figure more things out about the program.

I like to use the “delete frame” button to start off with just one frame. It’s easier for me to understand if its simpler. You can also find instructions on the bottom. Oh, and try using the shift key when you move the blue frames. If you make something you like, save it, email it to us, and we’ll add it to our readers’ gallery.

Start doodaling!

Make something you love. Bon appetit!

A fractal Math Munch Doodal

A fractal Math Munch Doodal

SET, Ptolemy, and Malin Christersson

Welcome to this week’s Math Munch!

To set up the punchline: if you haven’t played the card game SET before, do yourself a favor and go try it out now!

(Or if you prefer, here’s a video tutorial.)

ThereAreNoSetsHere

Are there any sets to be found here?

(And even if you have played before, go ahead and indulge yourself with a round. You deserve a SET break.🙂 )

Now, we’ve shared about SET before, but recently there has been some very big SET-related news. Although things have been quieter around Georgia Tech since summer has started, there has been a buzz both here and around the internet about a big breakthrough by Vsevolod Lev, Péter Pál Pach, and Georgia Tech professor Ernie Croot. Together they have discovered a new approach to estimate how big a SET-less collection of SET cards can be.

In SET there are a total of 81 cards, since each card expresses one combination of four different characteristics (shape, color, filling, number) for which there are three possibilities each. That makes 3^4=81 combinations of characteristics. Of these 81 cards, what do you think is the most cards we could lay out without a SET appearing? This is not an easy problem, but it turns out the answer is 20. An even harder problem, though, is asking the same question but for bigger decks where there are five or ten or seventy characteristics—and so 3^5 or 3^10 or 3^70 cards. Finding the exact answer to these larger problems would be very, very hard, and so it would be nice if we could at least estimate how big of a collection of SET-less cards we could make in each case. This is called the cap set problem, and Vsevolod, Péter, and Ernie found a much, much better way to estimate the answers than what was previously known.

To find out more on the background of the cap set problem, check out this “low threshold, high ceiling” article by Michigan grad student Charlotte Chan. And I definitely encourage you to check out this article by Erica Klarreich in Quanta Magazine for more details about the breakthrough and for reactions from the mathematical community. Here’s a choice quote:

Now, however, mathematicians have solved the cap set problem using an entirely different method — and in only a few pages of fairly elementary mathematics. “One of the delightful aspects of the whole story to me is that I could just sit down, and in half an hour I had understood the proof,” Gowers said.

(For further wonderful math articles, you’ll want to visit Erica’s website.)

 Vsevolod  Peter  Ernie
 Charlotte  Erica  Marsha

These are photos of Vsevolod, Péter, Ernie, Charlotte, Erica, and the creator of SET, geneticist Marsha Jean Falco.

Ready for more? Earlier this week, I ran across this animation:

tumblr_o0k7mkhNSN1uk13a5o1_500

It shows two ways of modeling the motions of the sun and the planets in the sky. On the left is a heliocentric model, which means the sun is at the center. On the right is a geocentric model, which means the earth is at the center.

suntriangle

Around 250 BC, Aristarchus calculated the size of the sun, and decided it was too big to revolve around the earth!

Now, I’m sure you’ve heard that the sun is at the center of the solar system, and that the earth and the planets revolve around the sun. (After all, we call it a “solar system”, don’t we?) But it took a long time for human beings to decide that this is so.

I have to confess: I have a soft spot for the geocentric model. I ran across the animation in a Facebook group of some graduates of St. John’s College, where I studied as an undergrad. We spent a semester or so reading Ptolemy’s Almagest—literally, the “Great Work”—on the geocentric model of the heavens. It is an incredible work of mathematics and of natural science. Ptolemy calculated the most accurate table of chords—a variation on a table of the sine function—that existed in his time and also proved intricate facts about circular motion. For example, here’s a video that shows that the eccentric and epicyclic models of solar motion are equivalent. What’s really remarkable is that not only does Ptolemy’s system account for the motions of the heavenly bodies, it actually gave better predictions of the locations of the planets than Copernicus’s heliocentric system when the latter first debuted in the 1500s. Not bad for something that was “wrong”!

Here are Ptolemy and Copernicus’s ways of explaining how Mars appears to move in the sky:

ptolemy Copernicus_Mars

Maybe you would like to learn more about the history of models of the cosmos? Or maybe you would like tinker with a world-system of your own? You might notice that the circles-on-circles of Ptolemy’s model are just like a spirograph or a roulette. I wonder what would happen if we made the orbit circles in much different proportions?

Malin

Malin, tiled hyperbolically.

Now, I was very glad to take this stroll down memory lane back to my college studies, but little did I know that I was taking a second stroll as well: the person who created this great animation, I had run across several other pieces of her work before! Her name is Malin Christersson and she’s a PhD student in math education in Sweden. She is also a computer scientist who previously taught high school and also teaches many people about creating math in GeoGebra. You can try out her many GeoGebra applets here. Malin also has a Tumblr where she posts gifs from the applets she creates.

About a year ago I happened across an applet that lets you create art in the style of artist (and superellipse creator) Piet Mondrian. But it also inverts your art—reflects it across a circle—so that you can view your own work from a totally different perspective. Then just a few months later I delighted in finding another applet where you can tile the hyperbolic plane with an image of your choice. (I used one tiling I produced as my Twitter photo for a while.)

Mondrian

Mondrainverted.

tiling (4)

Me, tiled hyperbolically.

And now come to find out these were both made by Malin, just like the astronomy animation above! And Malin doesn’t stop there, no, no. You should see her fractal applets depicting Julia sets. And her Rolling Hypocycloids and Epicycloids are can’t-miss. (Echoes of Ptolemy there, yes?!)

And please don’t miss out on Malin’s porfolio of applets made in the programming language Processing.

It’s a good feeling to finally put the pieces together and to have a new mathematician, artist, and teacher who inspires me!

I hope you’ll find some inspiration, too. Bon appetit!

Wordless Videos, isthisprime, and Fan Chung Graham

Welcome to this week’s Math Munch! For the final Thursday of May, we’ll be looking back at some of this month’s posts from our Facebook page. We’ll see some wordless videos by The Global Math Project, look at a prime number quiz game, and meet Fan Chung Graham, one of the world’s leading mathematicians.

I don’t know much about The Global Math Project, but I know James Tanton is involved, and that is always a good thing. (Remember his Exploding Dots?) Well, they’ve posted a couple of wonderful videos featuring Tanton’s “math without words.” Need I say more? See for yourself.

If you like those, here are some more math without words from Tanton’s website.

Up next is a neat little thing by Christian Lawson-Perfect from The Aperiodical. Christian bought isthisprime.com and set up a little quiz game. Click over and see for yourself how it goes… I’ll wait… click below…

Screen Shot 2016-05-25 at 8.52.14 PM

It’s good practice for divisibility tests and getting your prime recognition up, but I suppose it’s not all that mathematical, is it? But Christian did something interesting. He recorded data from all the games played, and he wrote a summary of the results. I love all the charts and graphs in there. The one below shows how likely a number is to be missed by players.

Screen Shot 2016-05-25 at 9.01.48 PM

Finally, I hadn’t heard of Fan Chung-Graham until I found an interview of her posted on Facebook. She is one of the world’s leading mathematicians in several fields, and though she recently retired, she still conducts some research. The interview is a little academic, but it’s still nice to get to know such a talented mathematician.

fan1

Well that wraps up the week and month. I hope you’ve found some tasty math.  Have a great week and bon appetite!

Forest Fires, Scrubbing Calculator, and Bongard Problems

Welcome to this week’s Math Munch!

Last summer where I live, in California, there were a lot of forest fires. We’re having a big drought, and that made fires started for lots accidental of reasons– lightning, downed power lines, things like that– get much bigger than usual. I thought I’d learn a little about forest fires so that I can be a more responsible resident of my state.

And I found this great website with an awesome computer simulation that you can manipulate to experiment with the factors that lead to forest fires!

Forest fire.png

My forest fire, just starting to burn. Click on this picture to play with the simulation! (Note: It doesn’t work as well in certain browsers. I recommend Firefox.)

 

This site was built by Nicky Case, who studies things that mathematicians and scientists call complex systems. Basically, a complex system is some phenomenon that has a simple set of causes but unpredictable results. An environment with forest fires is a good example– a simple lightning strike in a drought-ridden forest can cause a wildfire to spread in patterns that firefighters struggle to predict. It turns out that simulations are perfect for modeling complex systems. With just a few simple program rules we can create a huge number of situations to study. Even better, we can change the rules to see what will happen if, say, the weather changes or people are more careful about where and when they set fires.

Forest fire what if

What do you think? Click the picture to see Nicky’s simulation.

You can use Nicky’s program to change the probability that trees grow, a burning tree sets its neighbors on fire, and many other factors. You can even invent your own and model them with emojis. What if there were two kinds of trees and one was more flammable than the other? What if trees grew quickly but lightning was common? As Nicky shows, simulations are useful for exploring what-if questions in complex systems. Use your imagination and explore!

Next up, have you ever heard of a scrubbing calculator? No, it’s not a calculator that doubles as a sponge. It’s a calculator that helps you solve for unknowns in equations by “scrubbing,” or approximating, the answer until you find a number that works.

Scrubbing calculator equation

Here’s how it works: Say you’re trying to solve for an unknown, like the x in the equation above (maybe for some practical reason or just because you’re doing your homework). You could do some pretty complicated algebraic manipulations so that the x alone equals some number. But what if you could make a guess and change it until the equation worked?

Scrubbing calculator

Click on this image to see a scrubbing calculator in action!

If your guess was too big, you’d know because the expression wouldn’t equal 768 anymore– it would equal something larger. And if you had a calculator that instantly told you the solution based on your guess, you could do this guessing and checking pretty quickly.

Well, lucky for you I found a scrubbing calculator that you can use online! It’s very simple– just type in your equation and your guess, and click on the number you want to change (most likely the guess) to make it larger or smaller. It’s useful for solving equations, like I said. But I actually find it most interesting to watch how the whole expression changes as you change one of the numbers in it. For instance, check out the Pythagorean triple calculator I built. What do you notice as you gradually change one of the numbers in the expression?

https://www.cruncher.io/?/embed/xiY1IjwUJS

Finally, I’m excited to share with you one of my favorite kinds of puzzles– Bongard problems!
Bongard 1A Bongard problem has two sets of pictures, with six pictures in each set. All of the pictures on the left have something in common that the pictures on the right do not. The challenge is to figure out what distinguishes the two groups of pictures.

Bongard 2

This problem was made by Douglas Hofstadter, who introduced Bongard problems to the U.S. I haven’t figured it out yet. Can you?

I got the Bongard problems shown above from a collection of problems put together by cognitive scientist Harry Foundalis. He has almost 300 of them, some made by Mikhail Bongard himself, who developed these problems while studying how to train computers to recognize patterns.

Harry also has guidelines for how to develop your own Bongard problems. He encourages people to send their problems to him and says he might even put them up on his site!

Bon appetit!

Slides and Twists, Life in Life, and Star Art

Happy second Thursday, and get your engines star-ted! We hope you’ll enjoy this throwback post from May 2012. Bon appetit!

Math Munch

Welcome to this week’s Math Munch!

I ran across the most wonderful compendium of slidey and twisty puzzles this past week when sharing the famous 15-puzzle with one of my classes.  It’s called Jaap’s Puzzle Page and it’s run by a software engineer from the Netherlands named Jaap Scherphuis. Jaap has been running his Puzzle Page since 1999.


Jaap Scherphuis
and some of his many puzzles

Jaap first encountered hands-on mathematical puzzles when he was given a Rubik’s Cube as a present when he was 8 or 9. He now owns over 700 different puzzles!

Jaap’s catalogue of slidey and twisty puzzles is immense and diverse. Each puzzle is accompanied by a picture, a description, a mathematical analysis, and–SPOILER ALERT–an algorithm that you can use to solve it!

On top of this, all of the puzzles in Jaap’s list with asterisks (*) next to them have playable Java applets on…

View original post 365 more words

Solomon Golomb, Rulers, and 52 Master Pieces

Welcome to this week’s Math Munch.

I was saddened to learn this week of the passing of Solomon Golomb.

Solomon Golomb.

Solomon Golomb.

Can you imagine the world without Tetris? What about the world without GPS or cell phones?

Here at Math Munch we are big fans of pentominoes and polyominoes—we’ve written about them often and enjoy sharing them and tinkering with them. While collections of glued-together squares have been around since ancient times, Solomon invented the term “polyominoes” in 1953, investigated them, wrote about them—including this book—and popularized them with puzzle enthusiasts. But one of Solomon’s outstanding qualities as a mathematician is that he pursued a range of projects that blurred the easy and often-used distinction between “pure” and “applied” mathematics. While polyominoes might seem like just a cute plaything, Solomon’s work with discrete structures helped to pave the way for our digital world. Solomon compiled the first book on digital communications and his work led to such technologies as radio telescopes. You can hear him talk about the applications that came from his work and more in this video:

Here is another video, one that surveys Solomon’s work and life. It’s fast-paced and charming and features Solomon in a USC Trojan football uniform! Here is a wonderful short biography of Solomon written by Elwyn Berlekamp. And how about a tutorial on a 16-bit Fibonacci linear feedback shift register—which Solomon mentions as the work he’s most proud of—in Minecraft!

Another kind of mathematical object that Solomon invented is a Golomb ruler. If you think about it, an ordinary 12-inch ruler is kind of inefficient. I mean, do we really need all of those markings? It seems like we could just do away with the 7″ mark, since if we wanted to measure something 7 inches long, we could just measure from the 1″ mark to the 8″ mark. (Or from 2″ to 9″.) So what would happen if we got rid of redundancies of this kind? How many marks do you actually need in order to measure every length from 1″ to 12″?

An optimal Golomb ruler of order 4.

An optimal Golomb ruler of order 4.

Portrait of Solomon by Ken Knowlton.

Portrait of Solomon by Ken Knowlton.

I was pleased to find that there’s actually a distributed computing project at distributed.net to help find new Golomb Rulers, just like the GIMPS project to find new Mersenne primes. It’s called OGR for “Optimal Golomb Ruler.” Maybe signing up to participate would be a nice way to honor Solomon’s memory. It’s hard to know what to do when someone passionate and talented and inspiring dies. Impossible, even. We can hope, though, to keep a great person’s memory and spirit alive and to help continue their good work. Maybe this week you’ll share a pentomino puzzle with a friend, or check out the sequences on the OEIS that have Solomon’s name attached to them, or host a Tetris or Blokus party—whatever you’re moved to do.

Thinking about Golomb rulers got me to wondering about what other kinds of nifty rulers might exist. Not long ago, at Gathering for Gardner, Matt Parker spoke about a kind of ruler that foresters use to measure the diameter of tree. Now, that sounds like quite the trick—seeing how the diameter is inside of the tree! But the ruler has a clever work-around: marking things off in multiples of pi! You can read more about this kind of ruler in a blog post by Dave Richeson. I love how Dave got inspired and took this “roundabout ruler” idea to the next level to make rulers that can measure area and volume as well. Generalizing—it’s what mathematicians do!

 img_3975  measuringtapes1

I was also intrigued by an image that popped up as I was poking around for interesting rulers. It’s called a seam allowance curve ruler. Some patterns for clothing don’t have a little extra material planned out around the edges so that the clothes can be sewn up. (Bummer, right?) To pad the edges of the pattern is easy along straight parts, but what about curved parts like armholes? Wouldn’t it be nice to have a curved ruler? Ta-da!

A seam allowance curve ruler.

A seam allowance curve ruler.

David Cohen

David Cohen

Speaking of Gathering for Gardner: it was announced recently that G4G is helping to sponsor an online puzzle challenge called 52 Master Pieces. It’s an “armchair puzzle hunt” created by David Cohen, a physician in Atlanta. It will all happen online and it’s free to participate. There will be lots of puzzle to solve, and each one is built around the theme of a “master” of some occupation, like an architect or a physician. Here are a couple of examples:

MedicinePuzzle
 ArchitectPuzzle

Notice that both of these puzzles involve pentominoes!

The official start date to the contest hasn’t been announced yet, but you can get a sneak peek of the site—for a price! What’s the price, you ask? You have to solve a puzzle, of course! Actually, you have your choice of two, and each one is a maze. Which one will you pick to solve? Head on over and give it a go!

Maze A

Maze A

Maze B

Maze B

And one last thing before I go: if you’re intrigued by that medicine puzzle, you might really like checking out 100 different ways this shape can be 1/4 shaded. They were designed by David Butler, who teaches in the Maths Learning Centre at the University of Adelaide. Which one do you like best? Can you figure out why each one is a quarter shaded? It’s like art and a puzzle all at once! Can you come up with some quarter-shaded creations of your own? If you do, send them our way! We’d love to see them.

Six ways to quarter the cross pentomino. 94 more await you!

Eight ways to quarter the cross pentomino. 92 more await you!

Bon appetit!