This post is about Pascal’s Triangle related puzzles and the value of re-framing problems in multiple different ways in order to draw our attention to alternative solutions.
I’ve seen multiple Pascal’s Triangle related puzzles that look something like this. You have a 6 by 6 square grid and a counter. The counter can start in either of the ‘off-grid’ positions indicated below, and with each move it can either go vertically down any number of spaces (up to 6), or horizontally right any number of spaces (up to 6). How many different ways are there that the counter could travel to the bottom right hand corner?
If we start in the top left corner and record how many paths there are to each square (in the squares themselves) we get something that looks familiar:
Surprise, surprise…it’s Pascal’s triangle!
And we can see why: to get to any square we can either come from above, or from the left. So, the number of ways of getting to that square is the number of ways of getting to the square above it plus the number of ways of getting to the square to its left. When Pascal’s Triangle is in its usual orientation the two cells being summed are those above the cell we are trying to find.
The value in the bottom right corner can be found by continuing this pattern. But we could solve this problem using another commonly referenced property of Pascal’s Triangle – its link to nCr. There are 10C5 ways of getting to the bottom right square. From the first square (it doesn’t matter how we get there) we need to move a total of five spaces right, and five spaces down, and 10C5 gives us the number of ways of choosing which of those ten moves are the five to the right.
Recently I was shown a similar ‘how many ways?’ puzzle that drew my attention to a less commonly referenced Pascal’s pattern. It excited me!
Imagine you are standing at one end of a footpath made of ten paving stones. You are standing before the first paving stone (the 0th stone if you like) and your aim is to end up on the tenth and final stone. You can make steps of different sizes. You could make the journey by stepping one stone at a time, or by stepping straight to the tenth stone in one step, or by a combination of different integer-sized steps. How many different ways are there of getting to the tenth stone?
We could start by considering how many ways there are of getting to the earlier stones. There is clearly just one way of getting to the first stone, and below I have written out all the different ways of getting to second, third and fourth stone.
Each row represents a journey, and the numbers in the row represent the stones that are stepped on in that journey. For example, the final journey in each list represents stepping on all the stones.
We can see that these totals are powers of two (there are 2n-1 ways for n stones). This makes sense; n-1 stones (all stones apart from the final stone) can be in one of two different states – they can either be stepped on in the journey, or not stepped on.
We can use this formula to find how many ways there are of getting to the tenth stone and solve the puzzle. But this is not the only interesting pattern we can find in our results. Let’s consider where these different ‘ways’ are coming from. The table below breaks down how many of these journeys took two steps, or three steps, etc.
And surprise, surprise…it’s Pascal’s Triangle!
This also explains the powers of two – the sum of the cells in each row of Pascal’s Triangle add up to successive powers of two. But why does this problem result in Pascal’s Triangle?
Does it make sense that summing two cells will give the result in the cell below them (as in the diagram below)? Unlike the previous puzzle, it did not seem immediately* obvious to me why this would be the case. It was a different connection between different cases in the problem that helped me understand why this puzzle resulted in Pascal’s Triangle.
Let’s consider how to get to the fifth stone in three steps. Our first two steps must get us to either the fourth, the third or the second stone. Thus, if we sum the number of ways of getting to each of these stones in two steps (the cells that are circled in the diagram below) then we have all the possible ways of getting to the fifth stone in three steps (the cell with the triangle).
This is the Hockey Stick identity! It looks more like a hockey stick when Pascal’s Triangle is in its usual presentation (below).
The Hockey Stick identity tells us that to find the value of any cell we can sum all the cells in the diagonal before it, up to the cell in the row before it.
We can show that if the Hockey Stick identity is true then the ‘two above sum to the one below’ rule must also hold. In the diagram below we know the first two circled cells add to give the square cell (by the Hockey Stick identity). Therefore, summing all three circled cells is the same as adding the two cells above the triangular cell (the square cell and the bottom circled cell). And this works for any length or position of hockey stick! It was pleasing to think about it this way around.
As with all good puzzles there are multiple ways of solving it. There is also an explanation for the appearance of Pascal’s Triangle from combinatorics.
Let’s imagine we are trying to find the number of ways of getting to the fifth stone in three steps. Our first two steps must have been taken over the first four stones. We landed on exactly two stones between stone 1 and 4. And there are 4C2 ways of choosing which two of the four stones to step on, so there are 4C2 ways of getting to the fifth stone in three steps. Generally, there are p-1Cs-1 ways of getting to the pth stone in s steps. This matches up with the values Pascal’s Triangle gives us (shown below).
*It wasn’t until later on, having found these two other ‘explanations’ for why we end up with Pascal’s Triangle, that an explanation for the ‘two cells above sum to the one below’ pattern dawned on me. I’m glad I didn’t spot it immediately as I may not have had the fun of unexpectedly stumbling upon the Hockey Stick pattern.
Interestingly, it didn’t become clear to me why this is the case until the problem was re-framed. Imagine instead you are a frog on one side of a pond, and you are trying to reach the other side, by stepping on some, all or none of the n lily pads on the way. (Having n lily pads is equivalent to having n+1 stones in the problem above.) And if we want to increase the number of lily pads (to make the 3-lily pad case become the 4-lily pad case, for example) we imagine adding another lily pad in between the two banks.
The difference is that in this representation the nth thing (lily pad) that is being added is not also the destination (the bank). In the ‘stone’ version I was imagining that the nth stone that is being added then becomes the destination. My explanation for the ‘two above add to the one below’ pattern hangs on that idea that the additional lily pad or stone does not have to be stood on. It’s easier to come to this idea if we imagine that the additional thing is not the destination; by its nature the destination has to be stood on.
Let’s imagine we want to find the number of ways of crossing the four lily pad pond in three jumps. The fourth lily pad that has just been added in can be jumped on to, or not. The number of ways of getting to the other side in three jumps if the fourth lily pad is NOT used, is equal to the number of ways of crossing the three lily pad pond in three jumps (we’ve just made the final jump a bit longer). And the number of ways of getting to the other side if the fourth lily pad is used is equal to the number of ways of crossing the three lily pad pond in two jumps (the second jump becomes the second and third jump when it is broken by the frog landing on the fourth lily pad). These two values that we need to sum are the two cells above the one we are looking for in Pascal’s Triangle!
And there we have it. Sometimes the framing of the puzzle allows us to more easily see particular solutions. For me the ‘stone’ representation of this puzzle lent itself to the hockey stick pattern. Whereas the ‘frog’ representation allowed me to see why the ‘two above sum to the one below’ pattern applied.
Much of the fun of maths comes from finding different ways to reach the same conclusion. And puzzles like these are full of opportunities for that!
I have discovered good posts right here.
I love the way you describe. So excellent!