Tag Archives: combinatorics

Stomachion, Toilet Math, and Domino Computer Returns!

Welcome to this week’s Math Munch!

I recently ran across a very ancient puzzle with a very modern solution– and a very funny name. It’s called the Stomachion, and it looks like this:

Stomachion_850So, what do you do? The puzzle is made up of these fourteen pieces carved out of a 12 by 12 square– and the challenge is to make as many different squares as possible using all of the pieces. No one is totally sure who invented the Stomachion puzzle, but it’s definite that Archimedes, one of the most famous Ancient Greek mathematicians, had a lot of fun working on it.

StomaAnimSometimes Archimedes used the Stomachion pieces to make fun shapes, like elephants and flying birds. (If you think that sounds like fun, check out this page of Stomachion critters to try making and this lesson about the Stomachion puzzle from NCTM.) But his favorite thing to do with the Stomachion pieces was to arrange them into squares!

It’s clear that you can arrange the Stomachion pieces into a square in at least one way– because that’s how they start before you cut them out. But is there another way to do it? And, if there’s a second way, is there a third? How about a fourth? Because Archimedes was wondering about how many ways there are to make a square with Stomachion pieces, some mathematicians give him credit for being an inventor of combinatorics, the branch of math that studies counting things.

Ostomachion536Solutions_850It turns out that there are many, many ways to make squares (the picture above shows all of them– click on it for greater detail)– and Archimedes didn’t find them all. But someone else did, over 2,000 years later! He used a computer to solve the problem– something Archimedes could never have done– but mathematician Bill Cutler found that there are 536 ways to make a square with Stomachion pieces! That’s a lot! If you’ve tried to make squares with the pieces, you might be particularly surprised– it’s pretty tricky to arrange them into one unique square, let alone 536. This finding was such a big deal that it made it into the New York Times. (Though you may notice that the number reported in the article is different– that’s how many ways there are to make a square if you include all of the solutions that are symmetrically the same.)

Other mathematicians have worked on finding the number of ways to arrange the Stomachion pieces into other shapes– such as triangles and diamonds. Given that it took until 2003 for someone to find the solution for squares, there are many, many open questions about the Stomachion puzzle just waiting to be solved! Who knows– if you play with the Stomachion long enough, maybe you’ll discover something new!

Next up, the mathematicians over at Numberphile have worked out a solution to a problem that plagued me a few weeks ago while I was camping– choosing the best outdoor toilet to use without checking all of them for grossness first. Is there a way to ensure that you won’t end up using the most disgusting toilet without having to look in every single one of them? Turns out there is! Watch this video to learn how:

Finally, a little blast from the past. Almost two years ago I share with you a video of something really awesome– a computer made entirely out of dominoes! Well, this year, some students and I finally got the chance to make one of our own! It very challenging and completely exhausting, but well worth the effort. Our domino computer recently made its debut on the mathematical internet, so I thought I’d share it with all of you! Enjoy!

Bon appetit!

Light Bulbs, Lanterns, and Lights Out

Welcome to this week’s Math Munch!

thomas-edison

Edison with his light bulb.

On this day in 1880, Thomas Edison was given a patent for his most famous bright idea—the light bulb.

Edison once said, “Genius is one per cent inspiration, ninety-nine per cent perspiration”—a good reminder that putting in some work is important both in math and in life. He also said, “We don’t know a millionth of one percent about anything.” A humbling thought. Also, based on that quote, it sounds like Edison might have had a use for permilles or even permyraids in addition to percents!

Mike's octahedron.

Mike’s octahedron-in-a-light-buld.

In celebration of this illustrious anniversary, I’d like to share some light mathematical fare relating to, well, light bulbs. For starters, J. Mike Rollins of North Carolina has created each of the Platonic solids inside of light bulbs, ship-in-a-bottle style. Getting just the cube to work took him the better part of twelve hours! Talk about perspiration. Mike has also made a number of lovely Escher-inspired woodcuts. Check ’em out!

Evelyn's Schwartz lantern.

Evelyn’s Schwartz lantern.

Next up is a far-out example from calculus that’s also a good idea for an art project. It’s called the Schwartz lantern. I found out about this amazing object last fall when Evelyn Lamb tweeted and blogged about it.

The big idea of calculus is that we can find exact answers to tough problems by setting up a pattern of approximations that get better and better and then—zoop! take the process to its logical conclusion at infinity. But there’s a catch: you have to be careful about how you set up your pattern!

A "nicely" triangulated cylinder.

A “nicely” triangulated cylinder.

For example, if you take a cylinder and approximate its surface with a bunch of triangles carefully, you’ll end up with a surface that matches the cylinder in shape and size. But if you go about the process in a different way, you can end up with a surface that stays right near the cylinder but that has infinite area. That’s the Schwartz lantern, first proposed by Karl Hermann Amandus Schwarz of Cauchy-Schwartz fame. The infinite area happens because of all the crinkles that this devilish pattern creates. For some delightful technical details about the lantern’s construction, check out Evelyn’s post and this article by Conan Wu.

Maybe you’ll try folding a Schwartz lantern of your own. There’s a template and instructions on Conan’s blog to get you started. You’ll be glowing when you finish it up—especially if you submit a photo of it to our Readers’ Gallery. Even better, how about a video? You could make the internet’s first Schwartz lantern short film!

Robert Torrence and his Lights Out puzzle.

Robert and his Lights Out puzzle.

At the MOVES Conference last fall, Bruce Torrence of Randolf-Macon College gave a talk about the math of Lights Out. Lights Out is a puzzle—a close relative of Ray Ray—that’s played on a square grid. When you push one of the buttons in the grid it switches on or off, and its neighbors do, too. Bruce and his son Robert created an extension of this puzzle to some non-grid graphs. Here’s an article about their work and here’s an applet on the New York Times website where you can play Lights Out on the Peterson graph, among others. You can even create a Lights Out puzzle of your own! If it’s more your style, you can try a version of the original game called All Out on Miniclip.

The original Lights Out handheld game from 1995.

The original Lights Out handheld game from 1995.

There’s a huge collection of Lights Out resources on Jaap’s Puzzle Page (previously), including solution strategies, variations, and some great counting problems. Lights Out and Ray Ray are both examples of what’s called a “sigma-plus game” in the mathematical literature. Just as a bonus, there’s this totally other game called Light Up. I haven’t solved a single puzzle yet, but my limitations shouldn’t stop you from trying. Perspiration!

All this great math work might make you hungry, so…bon appetit!

Partial Cubes, Open Cubes, and Spidrons

Welcome to this week’s Math Munch!

Recently the videos that Paul and I made about the Yoshimoto Cube got shared around a bit on the web. That got me to thinking again about splitting cubes apart, because the Yoshimoto Cube is made up of two pieces that are each half of a cube.

A part of Wall Drawing #601 by Sol LeWitt

A part of Wall Drawing #601
by Sol LeWitt

A friend of mine once shared with me some drawings of cubes by the artist Sol LeWitt. The cubes were drawn as solid objects, but parts of them were cut away and removed. It was fun trying to figure out what fraction of a cube remained.

On the web, I found a beautiful image that Sol made called Wall Drawing #601. In the clipping of it to the left, I see 7/8 of a cube and 3/4 of a cube. Do you? You can view the whole of this piece by Sol on the website of the Greater Des Moines Public Art Foundation.

The Cube Vinco by Vaclav Obsivac.

The Cube Vinco by Vaclav Obsivac.

There are other kinds of objects that break a cube into pieces in this way, like this tricky puzzle by Vaclav Obsivac and this “shaved” Rubik’s cube modification. Maybe you’ll design a cube dissection of your own!

As I further researched Sol LeWitt’s art, I found that he had investigated partial cubes in other ways, too. My favorite of Sol’s tinkerings is the sculpture installation called “Variations of Incomplete Cubes“. You can check out this piece of artwork on the SFMOMA site, as well as in the video below.

In the video, a diagram appears that Sol made of all of the incomplete open cubes. He carefully listed out and arranged these pictures to make sure that he had found them all—a very mathematical task. It reminds me of the list of rectangle subdivisions I wrote about in this post.

sollewitt_variationsonincompleteopencubes_1974

Sol’s diagram got me to thinking and making: what other shapes might have interesting “incomplete open” variations? I started working on tetrahedra. I think I might try to find and make them all. How about you?

Two open tetrahedra I made. Can you find some more?

Two open tetrahedra I made. Can you find some more?

Finally, as I browsed Google Images for “half cube”, one image in particular jumped out at me.

half-cube-newnweb

What are those?!?!

Dániel's original spidron from 1979

Dániel’s original spidron from 1979

These lovely rose-shaped objects are called spidrons—or more precisely, they appear to be half-cubes built out of fold-up spidrons. What are spidrons? I had never heard of them, but there’s one pictured to the right and they have their own Wikipedia article.

The first person who modeled a spidron was Dániel Erdély, a Hungarian designer and artist. Dániel started to work with spidrons as a part of a homework assignment from Ernő Rubik—that’s right, the man who invented the Rubik’s cube.

A cube with spidron faces.

A cube with spidron faces.

Two halves of an icosahedron.

Two halves of an icosahedron.

A hornflake.

A hornflake.

Here are two how-to videos that can help you to make a 3D spidron—the first step to making lovely shapes like those pictured above. The first video shows how to get set up with a template, and the second is brought to you by Dániel himself! Watching these folded spidrons spiral and spring is amazing. There’s more to see and read about spidrons in this Science News article and on Dániel’s website.

And how about a sphidron? Or a hornflake—perhaps a cousin to the flowsnake? So many cool shapes!

To my delight, I found that Dániel has created a video called Yoshimoto Spidronised—bringing my cube splitting adventure back around full circle. You’ll find it below. Bon appetit!

Reflection Sheet – Partial Cubes, Open Cubes, and Spidrons

Polyominoes, Clock Calculator, and Nine Bells

Welcome to this week’s Math Munch!

pentominoes!The first thing I have to share with you comes with a story. One day several years ago, I discovered these cool little shapes made of five squares. Maybe you’ve seen these guys before, but I’d never thought about how many different shapes I could make out of five squares. I was trying to decide if I had all the possible shapes made with five squares and what to call them, when along came Justin. He said, “Oh yeah, pentominoes. There’s so much stuff about those.”

Justin proceeded to show me that I wasn’t alone in discovering pentominoes – or any of their cousins, the polyominoes, made of any number of squares. I spent four happy years learning lots of things about polyominoes. Until one day… one of my students asked an unexpected question. Why squares? What if we used triangles? Or hexagons?

pentahexesWe drew what we called polyhexes (using hexagons) and polygles (using triangles). We were so excited about our discoveries! But were we alone in discovering them? I thought so, until…

whoa square

A square made with all polyominoes up to heptominoes (seven), involving as many internal squares as possible.

… I found the Poly Pages. This is the polyform site to end all polyform sites. You’ll find information about all kinds of polyforms — whether it be a run-of-the-mill polyomino or an exotic polybolo — on this site. Want to know how many polyominoes have a perimeter of 14? You can find the answer here. Were you wondering if polyominoes made from half-squares are interesting? Read all about polyares.

I’m so excited to have found this site. Even though I have to share credit for my discovery with other people, now I can use my new knowledge to ask even more interesting questions.

Next up, check out this clock arithmetic calculator. This calculator does addition, subtraction, multiplication, and division, and even more exotic things like square roots, on a clock.

clock calculatorWhat does that mean? Well, a clock only uses the whole numbers 1 through 12. Saying “15 o’clock” doesn’t make a lot of sense (unless you use military time) – but you can figure out what time “15 o’clock” is by determining how much more 15 is than 12. 15 o’clock is 3 hours after 12 – so 15 o’clock is actually 3 o’clock. You can use a similar process to figure out the value of any positive or negative counting number on a 12 clock, or on a clock of any size. This process (called modular arithmetic) can get a bit time consuming (pun time!) – so, give this clock calculator a try!

Finally, here is some wonderful mathemusic by composer Tom Johnson. Tom writes music with underlying mathematics. In this piece (which is almost a dance as well as a piece of music), Tom explores the possible paths between nine bells, hung in a three-by-three square. I think this is an example of mathematical art at its best – it’s interesting both mathematically and artistically. Observe him traveling all of the different paths while listening to the way he uses rhythm and pauses between the phrases to shape the music. Enjoy!

Bon appetit!

We Use Math, Integermania, and Best-of-Seven

Welcome to this week’s Math Munch!

astronaut“When will I use math?” Have you ever asked this question? Well, then you are in for a treat, because the good people of We Use Math have some answers for you! This site was created by the Math Department at Brigham Young University to help share information about career paths that are opened up by studying mathematics. Here’s their introductory video:

The We Use Math site shares write-ups about a wide range of career opportunities that involve doing mathematics. I was glad to learn more about less-familiar mathy careers like technical writing and cost estimation. Also, my brother has studied some operations management in college, so it was great to read the overview of that line of work. In addition, the We Use Math site has pages about recent math discoveries and about unsolved math problems. Check them out!

Next up is one of my long-time favorite websites: Integermania!

Perhaps you’ve heard of the four 4’s problem before. Using four 4’s and some arithmetic operations, can you make the numbers from 1 to 20? Or even higher? Some numbers are easy to make, like 16. It’s 4+4+4+4. Some are sneakier, like 1. One way it can be created is (4+4)/(4+4). But what about 7? Or 19? This is a very common type of problem in mathematics—which math objects of a certain type can be built with limited tools?

swilson21-e1315080873212

Steven J. Wilson

Integermania is a website where people from around the world have submitted number creations made of four small numbers and operations. It’s run by Steven J. Wilson, a math professor at Johnson County Community College in Kansas. (Steven has even more great math resources at his website Milefoot.com)

There are many challenges at Integermania: four 4’s, the first four prime numbers, the first four odds, and even the digits of Ramanujan’s famous taxicab number (1729).

Here are some number creations made of the first four prime numbers. Can you make some of your own?

Here are some number creations made of the first four prime numbers.
Can you make some of your own?

One of my favorite aspects of Integermania is the way it rates number creations by “exquisiteness level“. If a number creation is made using only simple operations—like addition or multiplication—then it’s regarded as more exquisite than if it uses operations like square roots or percentages. I also love how Integermania provides an opportunity for anyone to make their mark in the big world of mathematical research—it’s like scrawling a mathematical “I wuz here!” After years of visiting the site, I just submitted for the first time some number creations of my own. I’ll let you know how it goes, and I’d love to hear about it if you decide to submit, too.

Here are recaps of all the World Series since 1903 from MLB.com

Here are recaps of all the World Series since 1903 from MLB.com

Now coming to the plate: my final link of the week! Monday was the first day of the new Major League Baseball season. I want to share with you a New York Times article from last December. It’s called Keeping Score: Over in Four About a Fifth of the Time. The article digs into the outcomes of all of the World Series championships—not so much who won as how they won. It takes four victories to win a seven-game series, and there are 35 different ways that a best-of-seven series can play out, put in terms of wins and losses for the overall winner. For instance, a clean sweep would go WWWW, while another sequence would be WWLLWW. The article examines which of these win-loss sequences have been the most common in the World Series.

(Can you figure out why there are 35 possible win-loss sequences in a seven-game series? What about for a best-of-five series? And what if we tried to model the outcome of a series by assuming each team has a fixed chance of winning each game?)

worldseriesstats

A clip of the stats that are displayed in the Times article. Click through to see it all.

I was curious to know if the same results held true in other competitions. Are certain win-loss sequences rare across different sports? Are “sweeps” the most common outcome? After sifting through Wikipedia for a while, I was able to compile the statistics about win-loss sequences for hockey’s Stanley Cup Finals. This has been a best-of-seven series since 1939, and it has been played 73 times since then. (It didn’t happen in 2005 because of a lockout.) You can see the results of my research in this document. Two takeaways: sweeps are also the most common result in hockey, but baseball more frequently requires the full seven games to determine a winner.

It could be a fun project to look at other best-of-seven series, like the MLB’s League Championship Series or basketball’s NBA Finals. If you pull that data together, let us know in the comments!

Batter up, and bon appetit!

******

UPDATE (4/4/13): My first set of five number creations was accepted and are now posted on the Ramanujan challenge page. Here are the three small ones! Can you find a more exquisite way of writing 47 than I did?

myintegermania

Pixel Art, Gothic Circle Patterns, and First Past the Post

Welcome to this week’s Math Munch!

Guess what? Today is Math Munch’s one-year anniversary!

We’re so grateful to everyone who has made this year so much fun: our students and readers; everyone who has spread the word about Math Munch; and especially all the people who do and make the cool mathy things that we so love to find and share.

Speaking of which…

Mathematicians have studied the popular puzzle called Sudoku in numerous ways. They’ve counted the number of solutions. They’ve investigated how few given numbers are required to force a unique solution. But Tiffany C. Inglis came at this puzzle craze from another angle—as a way to encode pixel art!

Tiffany studies computer graphics at the University of Waterloo in Ontario, Canada. She’s a PhD candidate at the Computer Graphics Lab (which seems like an amazing place to work and study—would you check out these mazes!?)

Tiffany C. Inglis, hoisting a buckyball

Tiffany tried to find shading schemes for Sudoku puzzles so that pictures would emerge—like the classic mushroom pictured above. Sudoku puzzles are a pretty restrictive structure, but Tiffany and her collaborators had some success—and even more when they loosened the rules a bit. You can read about (and see!) some of their results on this rad poster and in their paper.

Thinking about making pictures with Sudoku puzzles got Tiffany interested in pixel art more generally. “I did some research on how to create pixel art from generic images such as photographs and realized that it’s an unexplored area of research, which was very exciting!” Soon she started building computer programs—algorithms—to automatically convert smooth line art into blockier pixel art without losing the flavor of the original. You can read more about Tiffany’s pixelization research on this page of her website. You should definitely check out another incredible poster Tiffany made about this research!

To read more of my interview with Tiffany, you can click here.

Cartoon Tiffany explains what makes a good pixelization. Check out the full comic!

I met Tiffany this past summer at Bridges, where she both exhibited her artwork and gave an awesome talk about circle patterns in Gothic architecture. You may be familiar with Apollonian gaskets; Gothic circle patterns have a similar circle-packing feel to them, but they have some different restrictions. Circles don’t just squeeze in one at a time, but come in rings. It’s especially nice when all of the tangencies—the places where the circles touch—coincide throughout the different layers of the pattern. Tiffany worked on the problem of when this happens and discovered that only a small family has this property. Even so, the less regular circle patterns can still produce pleasing effects. She wrote about this and more in her paper on Gothic circle patterns.

I’m really inspired by how Tiffany finds new ideas in so many place, and how she pursues them and then shares them in amazing ways. I hope you’re inspired, too!

A rose window at the Milan Cathedral, with circle designs highlighted.

A mathematical model similar to the window, which Tiffany created.

An original design by Tiffany. All of these images are from her paper.

Here’s another of Tiffany’s designs. Now try making one of your own!

Using the Mathematica code that Tiffany wrote to build her diagrams, I made an applet where you can try making some circle designs of your own. Check it out! If you make one you really like—and maybe color it in—we’d love to see it! You can send it to us at MathMunchTeam@gmail.com.

(You’ll may have to download a plug-in to view the applet; it’s the same plug-in required to use the Wolfram Demonstrations Project.)

Finally, with Election Day right around the corner, how about a dose of the mathematics of voting?

I’m a fan of this series of videos about voting theory by C.G.P. Grey. Who could resist the charm of learning about the alternative vote from a wallaby, or about gerrymandering from a weasel? Below you’ll find the first video in his series, entitled “The Problems with First Past the Post Voting Explained.” Majority rule isn’t as simple of a concept as you might think, and math can help to explain why. As can jungle animals, of course.

Thanks again for being a part of our Math Munch fun this past year. Here’s to a great second course! Bon appetit!


PS I linked to a bunch of papers in this post. After all, that’s the traditional first anniversary gift!

Rectangles, Explosions, and Surreals

Welcome to this week’s Math Munch!

What is 3 x 4?   3 x 4 is 12.

Well, yes. That’s true. But something that’s wonderful about mathematics is that seemingly simple objects and problems can contain immense and surprising wonders.

How many squares can you find in this diagram?

As I’ve mentioned before, the part of mathematics that works on counting problems is called combinatorics. Here are a few examples for you to chew on: How many ways can you scramble up the letters of SILENT? (LISTEN?) How many ways can you place two rooks on a chessboard so that they don’t attack each other? And how many squares can you count in a 3×4 grid?

Here’s one combinatorics problem that I ran across a while ago that results in some wonderful images. Instead of asking about squares in a 3×4 grid, a team at the Dubberly Design Office in San Francisco investigated the question: how many of ways can a 3×4 grid can be partitioned—or broken up—into rectangles? Here are a few examples:

How many different ways to do this do you think there are? Here’s the poster that they designed to show the answer that they found! You can also check out this video of their solution.

In their explanation of their project, the team states that “Design tools are becoming more computation-based; designers are working more closely with programmers; and designers are taking up programming.” Designing the layout of a magazine or website requires both structural and creative thinking. It’s useful to have an idea of what all the possible layouts are so that you can pick just the right one—and math can help you to do it!

If you’d like to try creating a few 3×4 rectangle partitions of your own, you can check out www.3x4grid.com. [Sadly, this page no longer works. See an archive of it here. -JL, 10/2016]

Next up, explosions! I could tell you about the math of the game Minesweeper (you can play it here), or about exploding dice. But the kind of explosion I want to share with you today is what’s called a “combinatorial explosion.” Sometimes a problem that appears to be an only slightly harder variation of an easy problem turns out to be way, way harder. Just how BIG and complicated even simple combinatorics problems can get is the subject of this compelling and also somewhat haunting video.

Donald Knuth

Finally, all of this counting got me thinking about big numbers. Previously we’ve linked to Math Cats, and Wendy has a page where you can learn how to say some really big numbers. But thinking about counting also made me remember an experience I had in middle school where I found out just how big numbers could be! I was in seventh grade when I read this article from the December 1995 issue of Discover Magazine. It’s called “Infinity Plus One, and Other Surreal Numbers” and was written by Polly Shulman. I remember my mind being blown by all of the talk of infinitely-spined aliens and up-arrow notation for naming numbers. Here’s an excerpt:

Mathematicians and precocious five-year-olds have long been fascinated by the endlessness of numbers, and they’ve named the endlessness infinity. Infinity isn’t a number like 1, 2, or 3; it’s hard to say what it is, exactly. It’s even harder to imagine what would happen if you tried to manipulate it using the arithmetic operations that work on numbers. For example, what if you divide it in half? What if you multiply it by 2? Is 1 plus infinity greater than, less than, or the same size as infinity plus 1? What happens if you subtract 1 from it?

After I read this article, John Conway and Donald Knuth became heros of mine. (In college, I had the amazing fortune to have breakfast with Conway one day when he was visiting to give a lecture!) Knuth has a book about surreals that’s the friendliest introduction to the surreal numbers that I know of, and in this video, Vi Hart briefly touches on surreal numbers in discussing proofs that .9 = 1. Boy, would I love to see a great video or online resource that simply and beautifully lays out the surreal numbers in all their glory!

It was fun for me to remember that Discover article. I hope that you, too, run across some mathematics that leaves a seventeen-year impression on you!

Bon appetit!