Some problems in mathematics are easy to state and maddeningly difficult to solve. A classic example is the problem of partitions , which asks: given a number of objects, how many different ways can you divide those objects into groups?
For example with 4 stones, I could divide them into groups of 4, 3 and 1, 2 and 2, 2 and 1 and 1, or 1 & 1 & 1 & 1.
This problem of finding a method to count the ways of partitioning numbers seems like it should be simple — it’s just addition! And yet, the solution eluded mathematicians for centuries. Euler worked on it in the 18th century, and Ramanujan and Hardy tackled it in the early 20th century. But the problem wasn’t solved until 2011, when Ken Ono and Jan Bruinier put forth a solution using high-powered modern mathematical techniques, well and truly beyond the grouping of stones. To me, there’s something beautiful about that counterpoint: simple question, elusive solution.
For today’s puzzle, I’d like to share some simpler partition puzzles. A general hint: these can usually be solved by simplifying the problem and organising your results to look for patterns, and there will be many beautiful patterns to find. Also, in all the puzzles today, order matters . That means we’ll count 5 + 3 as distinct from 3 + 5.
Puzzle 1
There are 3 ways to write 3 as the sum of 1s and 2s:
3 = 1 + 2
3 = 2 + 1
3 = 1 + 1 + 1
How many ways are there to write 8 as a sum of 1s and 2s?
Puzzle 2
There are 7 ways to write 8 as a sum of two positive integers:
8 = 1 + 7, 2 + 6, 3 + 5, 4 + 4, 5 + 3, 6 + 2, 7 + 1
How many ways can you write 8 as a sum of three positive integers?
Puzzle 3
There are 4 ways to write 3 as a sum of any number of positive integers:
3, 1+2, 2 + 1, 1 + 1 + 1
How many ways can you write 8 as a sum of any number of positive integers?
Research Question: If you substitute any other number for 8 in the puzzles above, can you find a general method that will allow you to solve the puzzles?
You can write to Dan Finkel ( dan@mathforlove.com ) with your responses to the Research Questions [subject: 10Play].
***********
Puzzle 1
There are 34 ways to write 8 as a sum of 1s and 2s. To see why, let’s start simple and see if we can get a handle on what’s happening.
1: 1 (1 way)
2: 1 + 1, 2 (2 ways)
3: 1 + 1 + 1, 2 + 1, 1 + 2 (3 ways)
4: 1 + 1+ 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2 (5 ways)
Starting small allows us to look for some labour-saving insight. What if we want to break 5 up into 1s and 2s. The start will be either 5 = 1 + … or 5 = 2 + …
But this reduces the problem to a simpler situation! More specifically we have 5 = 1 + [some way to make 4 with 1s and 2s] or 5 = 2 + [some way to make 3 with 1s and 2s]. We know that there are 5 ways to make 4 and 3 ways to make 3, so there must be 5 + 3 = 8 ways to make 5.
5: (8 ways)
And now we can see what’s happening. The number of ways to make each subsequent number on the list is the sum of the number of ways to make each of the previous two. So the list will continue
6: (13 ways)
7: (21 ways)
8: (34 ways)
These are Fibonacci numbers! It may be a surprise, but each Fibonacci number is the sum of the previous two, and that’s precisely how our partitions work too.
Puzzle 2
There are 21 ways to write 8 as a sum of three positive integers. Here’s one beautiful structure that emerges when we try to write all the ways out, putting each sum that starts with a given number on its own line:
6 + 1 + 1
5 + 2 + 1 5 + 1 + 2
4 + 3 + 1 4 + 2 + 2 4 + 1 + 3
3 + 4 + 1 3 + 3 + 2 3 + 2 + 3 3 + 1 + 4
2 + 5 + 1 2 + 4 + 2 2 + 3 + 3 2 + 2 + 4 2 + 1 + 5
1 + 6 + 1 1 + 5 + 2 1 + 4 + 3 1 + 3 + 4 1 + 2 + 5 1 + 1 + 6
It’s a triangle! And there are a triangle number of ways to write 8 as a the sum of 3 positive integers: 1 + 2 + 3 + 4 + 5 + 6 = 21 ways in all.
Puzzle 3
There are 128 ways to write 8 as a sum of positive integers. Let’s imagine 8 objects that we’ll literally partition into groups. For example, here’s 1 + 3 + 1 + 1 + 2
It’s clear that each partition corresponds to a way of, well, partitioning the dots. So how many ways can we do this? There could be a partition between any two dots, so that gives us 7 places we could draw in a barrier.
In any sum, each partition is either there or it isn’t. There are two choices for each, so we double the number of options for our sum when we consider each possible line between dots. That means there must be 2 x 2 x 2 x 2 x 2 x 2 x 2 = 2 = 128 ways to write 8 as a sum of positive integers.
Three puzzles, three different approaches. I encourage you to look further: there are many more ways to approach all these puzzles, and much more waiting to be discovered.
Happy puzzling!
Published - January 22, 2018 12:13 pm IST
