06 Counting by exhaustion
Combinatorial problems are popular in challenges because they can be less dependent on classroom knowledge and therefore be fair ways of identifying potential problem solvers, where they can use intuitive methods. Counting, or enumeration is a popular source of such problems. Counting problems, properly set, can be solved in the time allocated and they have the advantage of challenging the student later to try to generalize, to enable similar problems to be solved from an algorithm.This latter idea will be the subject of Chapter 10.
A good example is the derangement class of problems, of which the following Examples 6.1 and 6.2 from the AMC are good accessible examples. (A derangement is a re-arrangement of a set so that each member of the set is in the wrong place).
Example 6.1
In how many ways can a careless office boy place four letters in four envelopes so that no one gets the right letter?
Discussion
It is possible for a junior high school student to list and count all the cases. This would be an example of the cases method discussed elsewhere, but it is necessary to be sure one has exhausted the cases.
Solution 6.1
If we consider the 24 arrangements of the numbers 1, 2, 3, 4 and cross off all those with 1 in the first place (i.e. the first letter in its proper envelope), 2 in the second place, 3 in the third place, or 4 in the fourth place, we have left these nine arrangements:
(Note how to be sure we cover all cases we list in order of the first possible digit, next the next digit, etc until we have finished those commencing with 4.)
Therefore there are nine different ways.
Discussion
It is natural for a student to wonder what the answer is if there are 5, 6 or more letters, and whether there is a formula, or how rapidly does the answer grow. In Chapter 10 we will answer this question.
There are variations of derangement problems in which some number of members of the set are in the right place and all the others are in the wrong place. The following is an example.
Example 6.2
In the school band, five children each own their own trumpet. In how many ways can exactly three of the children take home the wrong trumpet, while the other two take home the right trumpet?
Discussion
This is a variation of the derangement problem in which some matchings are correct and others incorrect. It is possible again for students to count the cases, making sure one has exhaustively covered them all.
Solution 6.2
Suppose the students taking home the wrong trumpet are called A, B and C. These can take the wrong trumpets in two ways, e.g. A takes trumpet B, B takes trumpet C and C takes trumpet A, or A takes trumpet C, B takes trumpet A and C takes trumpet B.
We need also to know how many ways A, B and C can be chosen from the five. This is the same as the number of ways in which the two with the right trumpets can be chosen, this being ten (e.g. if the students are called A, B, C, D and E these are
A and B, A and C, A and D, A and E,
B and C, B and D, B and E,
C and D, C and E, and
D and E.
or a student familiar with combinatorics would know the number of ways of choosing 2 objects from 5 is
5C2=5!/(2!(5-2)!)=5!/(2!.3!)=120/(2)(6)=10.
Thus the answer is 10 x 2 = 20.
Discussion
This lends itself to generalisation also and will be followed up in Chapter 10. The generalisation involves being able to have any finite number of children and different breakdowns among them of how many take the right trumpet and how many who don't.
We now move on to another which doesn't have such obvious parameter for generalising, but nevertheless requires very careful and systematic counting to make sure you find every case, and every case once. I submitted this problem to the AMC and it appeard in 2014 as Junior 29 and Upper Primary 30. In each case only 1% of students got the right answer, but it is not too difficult as long as one is systematic.
Example 6.3
How many 3-digit numbers are there in which one of the digits is the sum of the other two?
Discussion
This can look rather intimidatory and blurry at first sight, and in this competition there is a fairly tight time constraint, but basically in my solution I go through all the numbers from 1 to 9 as first digit, subdividing each time into two cases, one when the first digit is the sum, and then when it contributes to the sum, and it is not too bad going through the cases.
Solution 6.3
Since the numbers are 3-digit we restrict our interest to those from 100 to 999.
The numbers are listed below. For each first digit, the first set will be those in which the first digit is the sum. The second will be one in which this first digit is the difference of the other two.
101, 110.
112, 121, 123. 132, 134, 143, 145, 154, 156, 165, 167, 176, 178, 187, 189, 198. (18)
202, 211, 220.
213, 231, 224, 242, 235, 253, 246, 264, 257, 275, 268, 286, 279, 297. (17)
303, 312, 321, 330.
314, 341, 325, 352, 336, 363, 347, 374, 358, 385, 369, 396. (16)
404, 413, 422, 431, 440.
415, 451, 426, 462, 437, 473, 448, 484, 459, 495. (15)
505, 514, 523, 532, 541, 550.
516, 561, 527, 572, 538, 583, 549, 594. (14)
606, 615, 624, 633, 642, 651, 660.
617, 671, 628, 682, 639, 693. (13)
707, 716, 725, 734, 743, 752, 761, 770.
718, 781, 729, 792. (12)
808, 817, 826, 835, 844, 853, 862, 871, 880.
819, 891.(11)
909, 918, 927, 936, 945, 954, 963, 972, 981, 990. (10)
We note 18+17+16+15+14+13+12+11+10=126, so the answer is 126.
Discussion
We now move to another problem where we can count all the cases (if we can safely recognise them all). This is from the T Shirt I designed in 2000 for the AMT featuring George Polya. The solution is more or less shown on the T Shirt.
Example 6.4
How many necklaces of 5 beads can be made with beads of 3 colours, assuming there is an infinite supply of each colour and necklaces are not changed just by rotating?
Solution 6.4
We have to find all the cases. Let us call the colours 1, 2 and 3 in decreasing order of use. If only one colour is used there are 3 ways of choosing it. If more than one colour is used (as in all cases except the first below) there are 6 examples as there are 3 ways of choosing the first colour and 2 of choosing the next.
Five colours of one, none of the others (5-0-0). 1-1-1-1-1- (3)
4-1-0. Just one case, 1-1-1-1-2-. It doesn't matter where colour 2 is. (6)
3-2-0. Either 1-1-1-2-2- (second coloured beads together (6 cases) or 1-1-2-1-2- (the two of the second colour separated) (6 more cases).
3-1-1. Same as above. Either 1-1-1-2-3-, the two single colours together (6 cases) or 1-1-2-1-3-, separated by 2 (6 more cases).
Finally 2-2-1. This is more complicated, but there are 4 different appearances. If the two of colour 1 are together the third can be isolated 1-1-2-3-2- (6 cases) or adjacent (1-1-3-2-2-) leaving the two of colour 2 together (6 more cases). If the two of colour 1 are separated, the third colour can be between them, 1-3-1-2-2- (6 cases) or one of colour 2 is (1-2-1-2-3) giving 6 more cases.
The total is 3+6+6+6+6+6+6+6+6=51.
Discussion
We will take this up for a discussion on possible generalisations in Chapter 10.
We now go on to a further problem of this type. It was composed for the AMC by ANU mathematician Bob Bryce and is one of the famous two AMC problems referred to in Chapter 3 under the home section of this site.
Example 6.5
I have four pairs of socks to be hung out side by side on a straight clothes line. The socks in each pair are identical but the pairs themselves have different colours. How many different colour patterns can be made if no sock is allowed to be next to its mate?
Discussion
I was the Chairman of the Problems Committee at this time and Bob was not happy about the solution he proposed. I felt that to be sure we needed a solution which a student well organised with strategy could solve in the time period, and came up with the following solution, which I was satisfied made the problem feasible.
Solution 6.5
Call the socks aa, bb, cc, dd.
There are 4 x 3 x 2=24 ways of selecting the first three as abc (i.e. the first three different).
These can be arranged systematically as shown:
So there are 24 x 30=720 patterns commencing with abc.
There are 4 x 3=12 ways of selecting the first three as aba.
These can also be systematically arranged as shown:
So there are 12 x 12=144 patterns commencing with aba.
Finally, 720+144=864. The answer is 864.
Discussion
This lends itself to generalisation also and will be followed up in Chapter 10. We will find a formula for the answer which will work when the number of pairs of socks is large enough to make the above exhaustive counting method too cumbersome.