Cutting Boards

It's tough coming up with a good activity that deals with numbers or geometry in a continuous way, since it usually requires a good amount of prerequisite knowledge. Today's activity is a set of discrete puzzles inspired by a continuous result colloquially known as the ham sandwich theorem.


Setup

While the premise of this activity will be cutting, it's probably best done with pen and paper. I'll suggest printing these puzzles and using dry erase markers and sleeves. Something like these would be great:

Each puzzle is a rectangular array of colored squares that must be cut into two pieces that have the same number of each color on each side. A cut can only be along grid lines or along the diagonal of a grid square. If a square is cut into two triangles along its diagonal, we count the triangles as half squares. We'll consider a cut that creates more than two pieces illegal, so no carving the \(n \times n\) board up into \(2n^2\) half squares and sorting them into piles!

Example 1

Example 2

Example 3

Challenges

A collection of puzzles in two and three colors can be found here. (They're not particularly well sorted by difficulty!)


Notes

  • Since the only fraction denomination involved is \(1/2\), this could be a good activity for early fraction learners. This activity also presents an opportunity to highlight something many people find paradoxical: If A has one more than B and gives one to B, now B has one more than A!

  • If there are an odd number of squares of any one color, a square of that color must be split. If there are only a handful of that color, this can lead to some forced cuts.

  • If a puzzle has reflectional symmetry, there is a solution via cutting down the line of symmetry. This works easily if the line of symmetry is a diagonal or if the line of symmetry is a horizontal or vertical bisector and the puzzle is \(n \times n\) with \(n\) even. If \(n\) is odd, we can create a zig zag cut down the line of symmetry:

    (Note that each square zigzagged through contributes half its area to the left and half to the right.)

    If the puzzle has \(180^\circ\) rotational symmetry, then cutting down a diagonal gives a solution.

  • Any solution to a puzzle must have the same area on each side of the cut, since balancing squares within their color buckets leads to a balance of squares.

    Conversely, if there is the same area on each side of the cut, we may not have a solution but can possibly still say something. For example, if cutting a puzzle with two colors into pieces A and B of equal areas leaves \(k\) more red squares on piece A than piece B, then piece B will have \(k\) more blue squares than piece A.

  • If the puzzle only uses two colors, there is always a solution. The continuous way to think about this is to start with a guess that leaves both sides with equal area (e.g., a diagonal cut). Either this is a solution or there will be \(k > 0\) more red squares on one side of the diagonal than the other. If we think about rotating this diagonal line about the center of the puzzle and studying the differential of red squares (originally red-abundant side minus red-deficient side), by the time the diagonal has rotated \(180^\circ\), a surplus of \(k\) red squares will have turned into a deficit of \(k\) red squares. By the intermediate value theorem, somewhere during that rotation the red squares on either side must have been balanced.

    However, the line at the point of balance likely cuts the puzzle in an illegal way, so we'll create a discrete analogue of rotating the diagonal. What we'll do is iteratively alter the cut so that at each stage each side of the cut loses \(1/2\) a square to the other side and gains \(1/2\) a square from the other while maintaining \(180^\circ\) rotational symmetry of the cut. Here are the first few stages of discretely "rotating" a diagonal on a \(4 \times 4\) puzzle clockwise, but it's more likely than not that you would come up with a different sequence than I did if trying it:

    Since we must see the red square differential morph from \(k\) to \(-k\) on our way from the diagonal to its \(180^\circ\) rotation, and red square differential changes by \(1/2\), \(0\), or \(-1/2\) each step, at some point we must have a red square differential of \(0\). This is a solution to our puzzle.

    While puzzles will likely have other solutions, this provides a good way to drum up a solution from a good initial guess by tweaking it. Area swapping tweaks can be useful to massage near-solutions into solutions and don't require the cut to be rotationally symmetric. (Rotational symmetry about the center is just a nice way to keep the areas across the cut equal.)

  • A random \(3\)-color puzzle may not have a solution!


Extra Challenges

  • Students might enjoy making their own puzzles and trying to solve them. Making a random puzzle by flipping a coin and making a square blue for heads and red for tails could be an interesting way to generate a tough puzzle. I haven't worked on large puzzles, but my suspicion is that they don't get super challenging in the 2-color case, so continuing to investigate small puzzles (say, no larger than \(10 \times 10\)) is probably the way to go. As noted, a random \(3\)-color puzzle might not be solvable. Students might enjoy trying to craft a small unsolvable \(3\)-color puzzle, which isn't too challenging. Proving that a specific large \(3\)-color puzzle is impossible is pretty tough, though!

  • If we define the length of a cut to be the total number of edges and diagonals it runs along, you might note that the length of the cut is \(3\) in each of the examples given in the Setup section. Is it always possible to solve a \(3 \times 3\) puzzle with a length-\(3\) cut? Or an \(n \times n\) puzzle with a length-\(n\) cut? Given a puzzle, what's the shortest cut that solves it?

  • If a \(3\)-color puzzle is unsolvable, is it possible to solve it for a pair of its colors, ignoring the third? Which pairs does this work for, if any? (This is perhaps a little closer to the ham sandwich theorem, treating the third color as ambient space.)


This post was sponsored by the Julia Robinson Mathematics Festival

Comments

Post a Comment

Popular posts from this blog

Modular Origami with Sonobe Units

The other month, I volunteered at Seattle Universal Math Museum's corner of Free First Thursdays at the Museum of Flight. Part of this was helping kids make origami paper airplanes, which reminded me of some origami challenges I used to give students. I'll present one of my favorite arcs here.
Read more

Instant Insanity

Today we'll look at an old puzzle that has gone by many names over the centuries, my favorite name being "The Great Tantalizer." The most popular recent iteration was Parker Brothers' "Instant Insanity," so that's what most people call it. We'll look at some variations that let students explore how this puzzle might be easy (or at least easier ), hard, or impossible.
Read more