This blog gives is accompanied by Problem Set 5.1, which extends the ideas further. The problems there and here are probably most suitable for KS5 but could be accessed by some KS4 students. I would recommend going through this blog before attempting the problems there, but it's up to you.
Let's start with a classic problem: What is the sum the numbers from 1 to 100? You will probably have seen this question before, and its solution, so it will be an exercise not a problem for most.
You can make the job easier by listing the numbers 1 to 100 forwards and backwards like this:
This exercise is not that interesting in itself, but I am interested in the way it uses kind of symmetry to solve the problem, and in the fact that it is connected to other areas of maths.
Of relevance to this post about counting, the sum of the counting numbers 1 to n is also the number of ways of choosing 2 items from n+1 items, written:
A nice way of explaining this is look at this diagram for (say) x + y + z = 5, which corresponds to the solution 1 + 2 + 2 = 5.
Can we extend the problem further and learn some more? Let's introduce another variable:
How did you start? I went for the make it easier strategy. Starting with a smaller polygon and looking for patterns...
If you like this problem, or just want to find out the answer, have a look at the counting chickens investigation.
Here's a beautiful way of solving this problem. Consider the following diagram:
Working systematically, we have the numbers 1 to 9 (so there are 9 increasing 1-digit numbers), then 12 to 19, then 23 to 29, and so on. You can see that the number of strictly increasing 2-digit numbers is 8 + 7 + ... + 2 + 1 = 9C2. Extending this to 3-digit numbers, starting with 1, we have 123 to 129, then 134 to 139 and so on giving 7 + 6 + ... = 8C2.
Carrying this on systematically, we will have increasing 3-digit numbers 8C2 + 7C2 + ... + 3C2 + 2C2. What is this sum? It turns out that summing nC2 numbers gives (n+1)C3, so this sum is 9C3. You should convince yourself that this valuable result is true, perhaps with some examples, or perhaps by looking at Pascal's triangle:
Let's reflect on this result. We discovered and used this important result (which generalises), which we will use again.
Making it easier might work - what would the problem be like for 3-digits? Will this help us solve the 4-digit problem? I'm not sure it will, but try and see. It will give us a feeling of the sort of problem we are dealing with anyway... Try it for yourself before reading on.
OK. Deep breath. Let's think back to the last problem we solved above involving increasing numbers. In our reflection, we saw that we could have considered each combination of digits. Will this approach work here? Let's consider any 4 digits: How many ways are there of choosing 4 distinct digits? And how many of these are snakelike?
Well, there are 9C4 different ways of choosing 4 distinct digits from 1 to 9 (let's ignore zeroes for now as they give some integers <1000 so are a bit different). Given a set of 4 distinct digits, how many orderings are snakelike? WLOG, let's look at 1234. The snakelike integers are 1324, 1423, 2314, 2413 and 3412. So there are 5 snakelike integers for each set of 4 digits, giving a total of 9C4 x 5.
Let's now consider the numbers containing a zero. The choice of one of the numbers is fixed to be 0, so we have 9C3 ways of getting a number containing a 0. Let's suppose this number is 0123, then we have 3 snakelike integers: 1203, 1302 and 2301, so we have 9C3 x 3 snakelike integers containing a 0, plus 9C4 x 5 integers without a zero.
Not too bad after all. We are learning all the time. And even if you didn't think of doing it this way, you might do next time!
Now try and use these techniques and strategies to solve these two interesting AMC10 problems (solutions to follow later), from the combinatorics problem set: