Problem Set 3.6: Combinatorics

These problems are about finding more effective ways of counting, which is part of a branch of Maths called ‘combinatorics’. Combinatorics is an interesting subject because it can be used to help solve problems for lots of different types of problems involving lots of other mathematics.

For each question, there is a usually very long way of working it out, but the aim to look for patterns and find a more systematic way of working it out. You will use the strategies make it easier and wishful thinking quite often.

Question 1

Hint: Work systematically to find them all. Is there any way of making finding the number of routes easier?

Going further: Draw your own grids and look for routes through them.

Question 2

Hint: This is quite easy; which types of number have one zero?

Going further: What fraction of these numbers is divisible by 5?

How many numbers between 99 and 999 contain an even digit?

How many numbers between 99 and 999 are multiples of 5? How many are multiples of 7? How many are either a multiple of 5, or a multiple of 7, but not both?

Question 3

Hint: Try some wishful thinking – suppose it was only one row, or perhaps that you were also given where the other two As were. How many ways would there be then? Then think about the different ways of placing the As.

Question 4

Hint: One way is to find how many arrangements there are, then look at how many of these have Angie and Carlos opposite each other. But can you think of a quicker way? Suppose Angie was sat in a seat, what is the chance Carlos is sat opposite?

Going further: Could you answer this question for any number of people?

Question 5

Hint: Again, you could just try and count them all, or you could consider different types of diagonal and see how many there are of each, or you could consider each vertex, or face, or …

Going further: Could you answer this question for other polyhedra, for example each Platonic solid?

Question 6

Hint: This is really the same as the number of solutions to the equation x + y + z = 6, where x, y and z are positive integers. Or you could think of it as the number of ways of breaking a chocolate bar containing 6 chunks (a Yorkie?) into 3 different parts.

Going further: Can you solve this problem for any number of pencils?

Question 7

Hint: Can you find an efficient way to count them? Note that distinct here just means triangles with different vertices.

Going further: How many different (non-congruent) triangles are there, if we say that triangles that are reflections of each other are the same?

Question 8

Hint: Consider different combinations of ‘corner’ vertices (SRT) and ‘edge’ vertices (XYZ).

Going further: if the distance between each dot is 1, can you find the area of each of the different triangles?

Question 9

Hint: can you find an efficient way of counting them? Can you use a method similar to the one you used for question 8 in some way?