Graph puzzles to sharpen your skills

In today’s post, Occupy Math will show you a family of puzzles that help you sharpen your logic skills. These puzzles are Occupy Math’s expanded version of some wonderful exercises developed by Peter Harrison called Bovine Math. Dr. Harrison’s exercises are a bridge from arithmetic to algebra, trying to ease the mental transition from concrete numbers to the abstraction of having variables. If you are a teacher unfamiliar with bovine math, definitely follow the link. Occupy Math notices that these wonderful exercises could be formalized as graph theory and found a family of puzzles. This is not Occupy Math’s first foray into educational puzzles that use graph theory. The puzzles in this post are for grades 2 and up, unless you learn to add before that. The larger the puzzle, the harder it is.

The left hand picture shows a puzzle as it is posed, the right hand picture shows a solved puzzle. Here are the rules.

1. Start with a blank graph, like the 4-cycle above.
2. The player puts positive whole numbers on each vertex of the graph. The player’s number are shown in black in the solution.
3. The player labels the edges of the graph with the sums of the numbers placed at their ends, these are shown in green in the solution.
4. All the numbers, both on vertices and edges, must be different from one another.
5. The goal is to make the sum of all the numbers as small as possible.

We call a solution perfect if the numbers are a complete counting sequence from 1 up to the largest number. The example solution shown above is perfect because the labels are 1, 2, 3, 4, 5, 6, 7, and 8. Keep in mind that the labels do not have to appear in any particular order. If you find a perfect solution to one of these puzzles you cannot do better — there is no place for a smaller number to show up! To put it another way, if you have labels that form a sequence with no gaps, starting with one, they must have the smallest possible total. Occupy Math made up a PDF of blank boards.

Stars

The graph above is called the 5-Star. The solution given is another perfect one with the numbers being 1,2,…,11. It turns out that every star graph has a perfect solution, which you can probably figure out by looking at the 5-star solution. Star puzzles are a good place to start because the solution is pretty easy to find. They are good for grades 2-4.

Paths

A path is a chain of vertices. The example above uses the 10-path, with ten vertices and nine edges. It presents a perfect solution. Occupy Math has found perfect solutions for the 2, 3, 4, 5, 7, 8, 9, and 10 paths. it seems likely that there are perfect solutions for all finite path lengths, as the amount of freedom you have to rearrange things goes up as more vertices are added. Paths work for grade 3-10, with the longer paths being for higher grades. The next example shows that this is really not a sure thing.

Cycles

The first example at the top of the post is a 4-cycle and the one above is a 7-cycle. Occupy Math is using his computation evolution technique to find the solutions to larger graphs, like the 10-path and 7-cycle. While it is not conclusive, the evolving software cannot find a perfect solution for the 5-cycle! Here is the best (lowest total) solution that Occupy Math’s Darwinian assistant found. It totals 57 where a perfect solution would total 55. The solution replaces 10 with 12, making it two points too large.

Occupy Math, or his code, has found perfect solutions for the 3, 4, 6, and 7 cycles. Cycles are harder than paths and even the evolutionary code would take a while to do the 8-cycle. It might be faster to solve by hand. Cycles work for grade 3-10 with larger cycles being for higher grades.

Complete bi-partite graphs

A complete bi-partite graph has two sets of vertices and all possible connection between them. Here is a perfect solution for the complete bi-partite graph with three and three vertices in its two sets.

If the two sets of vertices are the same size, then the complete bi-partite graph always has a perfect solution — Occupy Math has a proof — and the example above has the labels placed to give a giant hint as to why you can always find a perfect solution for this sort of graph. Notice that the numbers on the left start with one and count up by ones. The numbers on the right are multiples of the last number on the left, plus one. This means the edge labels are 1, 2, or 3 plus 4 AND 1, 2, or 3 plus 8, AND 1, 2, or 3 plus 12. This means that the labels count smoothly from 1 to 15. This pattern expands to larger examples. Complete bi-partite graphs are probably appropriate for 7-12 grade students or university students studying graph theory.

What does this post teach?

The advantage of these graph labelling puzzles, inspired by Dr. Harrison’s wonderful bovine math exercises, is that they have only the ability to add as a prerequisite, but they require fairly deep pre-algebraic thinking. The solution can be found by trial and error for the smaller puzzles, but thinking about the constraints your earlier choices make on your later ones encourages planning and strategic thinking. These puzzles are also scalable: there are really simple instances like the two-path, scaling up as much as you like.

An important detail is that the solutions are often not unique. You can put the values on the left or right side of a complete bi-partite graph in any order without changing the validity of the solution. The paths of length 9 and 10 have distinct perfect solutions in which the numbers on the vertices are different — this is part of what Occupy Math was talking about when he said longer paths have more freedom.

The PDF linked near the top of the post contains blank boards for the graphs used in the post and several others. These puzzles can be used for enrichment and distraction, but they also support other possible activities. Here are some suggestions.

• Path race! Pit teams of students against one another, solving the path graphs in order 3, 4, 5, …, ?. The instructor should pick the last path in the race consistent with the time available and the level of their students.
• Solve them all! This exercise asks students, individually or in teams, to find perfect solutions to the star graphs — all of them, with any number of leaves. This requires noting the pattern: number the non-central vertices in order, put the next number in the center, and the edge-labels come out in the laundry.
• Mysterious 5! Have students, again individually or in teams, find the best possible solutions for cycles with 3, 4, 5, 6, and maybe 7 vertices. The fact that 5 does not have a perfect solution should annoy people. You may want to give the idea of a perfect solution, or you may want the students to come up with the idea on their own.
• Dealer’s choice! Make up your own graph, not too many vertices, and have a competition. As students find valid (all numbers different) solutions with lower and lower totals of all the numbers, have them put their finding on the board. Be sure to vet your graph, or use one that Occupy Math has found to have a perfect solution.

Occupy Math hopes you find this activity post interesting. If you find other activities based on these puzzles — or a really good graph — please let us know in the comments! It may be worth mentioning that Occupy Math has an index of activities and informative posts for teachers and parents. As always, suggestion for future posts are welcome, via e-mail to dashlock@uoguelph.ca or in the comments.

I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics

Advertisement