Combinatorics in Year 8 Mathematics
Explore combinatorics concepts in Year 8 mathematics through systematic counting methods, including examples of counting right-angled triangles, frog hop sequences, and combinations of starters and main courses. Practice exercises included to enhance understanding of problem-solving strategies in combinatorics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Year 8: Combinatorics Dr J Frost (jfrost@tiffin.kingston.sch.uk) www.drfrostmaths.com Last modified: 29th December 2015
PART 1 :: Systematic Counting Sometimes the easiest way to count things is to explicitly list out every possibility! The key is listing the possibilities in some systematic way that avoids missing out cases or duplicates. Starter [JMC 2005 Q17] The figure shows rectangle ???? and line ??, which divides the rectangle into two squares. How many right-angled triangles can be drawn using any three of the points ?,?,?,?,?,? as corners? Hint: Perhaps consider each possible shape of triangle and how many there are of each? 4 ? 2 8 14 possibilities. By breaking the problem down into types of triangle, it made it much easier for us to count without missing out any possibilities. It also prevented us having to draw out similar cases.
Further Example A frog has 6 lily pads in front of him in a line. He can either hop (H) to the next lily pad, or skip one and go to the next (S). List out (using sequences of S and H) all the ways for the frog to get to the final lily pad. e.g. HSSH. Easiest when we break down into different numbers of skips: 0 skips: HHHHHH (1 way) 1 skip: SHHHH, HSHHH, HHSHH, HHHSH, HHHHS (5 ways) 2 skips: SSHH, SHSH, SHHS, HSSH, HSHS, HHSS (6 ways) 3 skips: SSS (1 way) To ensure I got all the possibilities here, I gradually moved the second S right one, before moving the left S right and repeating: SSHH HSSH HHSS SHSH HSHS SHHS ? 13 ways. In summary, break the problem down into smaller problemswhere it s easy to count within each one, e.g. types of triangles, team sizes, number of skips, etc.
Exercise 1 Exercises on provided sheet. 4 [SMC 2001 Q3] The diagram shows a regular hexagon divided up into six equilateral triangles. How many quadrilaterals are there in the diagram? A 6 B 8 D 12 E 14 Solution: D ? At a restaurant, there is a choice of Avocado (A), Beans (B) or Cauliflower (C) for starter, and a choice of Dog (D), Escalopes (E) and Frog Legs (F) for main course. List out all the nine possible combinations of starter and main course (e.g. BF ). 1 C 10 ? Solution: AD, AE, AF, BD, BE, BF, CD, CE, CF. [JMC 2006 Q4] How many triangles of any size are there in this diagram? A 8 B 10 D 14 E 16 2 C 12 [JMC 2006 Q17] In how many different ways can a row of five on/off switches be set so that no two adjacent switches are in the off position? A 5 B 10 D 13 E 15 Solution: D ? 5 ? Solution: C [JMC 2013 Q12] How many hexagons are there in the diagram? A 4 B 6 D 10 E 12 3 C 11 C 8 ? Solution: E
Exercise 1 Exercises on provided sheet. [Kangaroo Pink 2005 Q8] In the diagram there are 7 squares. What is the difference between the number of triangles and the number of squares in the diagram? A 0 B 1 C 2 D 3 E 4 Solution: D ? 9[TMC Final 2012 Q6] Find the number of squares formed by the lines of this 5 by 7 rectangular grid of squares. 6 7 [JMO 2011 A6] The diagram shows a grid of 16 identical equilateral triangles. How many different rhombuses are there made up of two adjacent small triangles? Solution: 85 ? [JMO 1997 A8] Given a cube, each selection of three vertices ?, ?, ? produces a triangle. How many of these triangles are right-angled triangles? (Triangles may only be on the faces of the cube) Solution: 24 ? 10 Solution: 18 ? [TMC Regional 2008 Q3] In total how many triangles of any size are there in the diagram? Solution: 35 ? 8
Exercise 1 Exercises on provided sheet. [TMC Regional 2014 Q4] Every day Keith has a breakfast, a lunch and a dinner. The options for each meal are: Each hour a pirate ship can either sail 1km West (W), 1km East (E), 1km North (N) or 1km South (S). It must always be moving. List all the ways in which the ship can end up 2km North after 4 hours (e.g. NNWE ) and count the number of possible journeys. (Hint: it may help to break the problem down possible sets of four movements, e.g. a N, N, W and E, and then considering the possible orderings of each possible set). 12 11 One day Keith eats four items. In how many different ways can he do this? Solution: 12 ? [JMO 2004 A10] The Famous Five have been given 20 sweets as a reward for solving a tricky crime. They have agreed that the oldest of them must receive more than the next oldest, who must receive more than the next oldest, and so on. Assuming that each of the five gets at least one sweet, in how many different ways can they share the sweets? Solution: 7 ? 13 Solution: NNWE, NNEW, NWNE, NENW, NWEN, NEWN, WNNE, ENNW, WNEN, ENWN, WENN, EWNN, ? SNNN, NSNN, NNSN, NNNS (16 ways).
Exercise 1 Exercises on provided sheet. 14 [Cayley 2007 Q4] How many right-angled triangles can be made by joining three vertices of a cube? (This time triangles formed may also go inside the cube) Solution: 48 (In a previous question we found 24 triangles on the faces. A further 24 triangles can be formed, 2 for each face diagonal where the triangle will pass inside the cube, e.g:). 15 [IMC 2009 Q22] A square is divided into eight congruent triangles, as shown. Two of these triangles are selected at random and shaded black. What is the probability that the resulting figure has at least one axis of symmetry? A 1 4 D 5 7 E 1 Solution: D ? ? B 4 C 1 7 2 There are 5 people in a room. How many ways are there of forming two teams of people, where each team must have at least one person. Solution: 15 teams. (5 teams where the teams are split 1 and 5. 10 teams where the teams are split 2 and 3) ? 14
PART 2 :: Counting by Multiplying Starter: Suppose the alphabet was limited to just A, B, C, D. Fold your provided piece of paper into 16 parts. Put A 4 times, B 4 times, C 4 times and D 4 times, before cutting. Use these cards (or otherwise) to answer the following questions: Note: a word is any possible sequence of characters; it need not be in a dictionary. Question 2 Question 1 Question 3 The number of possible 2 letter words where the letters are unrestricted. The number of possible 2 letter words where the letters are different. The number of possible 3 letter words where each letter cannot be the same as the previous letter, but is otherwise unrestricted. ? 4 possibilities for first letter, 4 for the second. ? ? = ?? 4 possibilities for first letter, 3 for the second. ? ? = ?? ? ? ? ? ? = ?? Question Question Question 4 The number of 4 letters words using each of the letters A, B, C, D exactly once. ? The number of 5 letter words using the letters AABCD, each exactly once. The number of 10 letter words using the letters AAAAAABBCD each once. ??! ?!?!= ???? ? ? ? ? ? ? ? = ?? ? ? ? ? = ??
Multiplying and Factorial Function If the number of choices for each thing are independent of each other, then we can multiply them together to get the total number of combinations. ABCDEFGHIJKLMNOPQRSTUVWXYZ For a full alphabet of 26 letters: a) How many possible 3 letter words are there? There are 26 choices for each letter. b) How many possible 3 letter words are there, where all letters are different? Each time there is one less choice. c) How many possible ways are there of arranging the letters of the word MATHS? There are 5 choices for the first letter, then 4 for the next, and so on. ?? ?? ?? ?? ??? ? ? ?? ?? ?? ? ? ? ? ? ? 5! = 5 4 3 2 1is said 5 factorial . ?! means the number of ways of arranging ? distinct objects in a line.
Examples I throw 4 dice. How many possible outcomes are there? ? ? ? ? ?? ?? Q ? Q I throw 10 coins. How many possible outcomes are there? ???= ???? ? Q I have a 10 kittens. I pick up 4 kittens and put them in a line. How many possibilities are there? ?? ? ? ? = ???? Note that the ordering of kittens in the line matters in this scenario (the number of possibilities would be less if we only cared about what kittens were selected) ?
A Few More Examples Q I have 6 different coloured balls in a line. How many ways of arranging them? ?! = ??? ? 3 boys and 4 girls go to a cinema. How many ways of arranging them such that the boys all come before the girls? ?! ?! = ??? Q ? How many ways of arranging the letters in the word BANANA? If the letters were all different there would be ?! = ??? ways. However, ???????? for example would count as the same as ???????? because the N s aren t distinguishable. So we need to divide by 2 to avoid duplicates. Similarly there are ?! = ?ways the A s could have been arranged which would lead to the same possibility. Thus: ?! ?!?!= ?? Q ?
Test Your Understanding A pack of cards contains 52 cards, 13 of each of four suits (Hearts, Spades, Clubs, Diamonds). In each suit we have the cards: Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King. Determine the number of possibilities when: a b 1 ? ?? ?? ?? I deal out 3 cards and put them in a line: I deal out Ace, 2, 3 and 4 of Diamonds, them arrange them in a line. I put 6 cards in a line, the first three Jack, Queen and King of Clubs, and the second three Jack, Queen and King of Spades. I deal out all the spades them arrange them in a line. I deal out all the cards and put them all together, but ensure the cards in each suit are kept together. There are ??! ways or arranging the clubs, ??! ways of arranging the spades, etc. But there s also 4! ways of arranging the four blocks of cards. ??! ??! ??! ??! ?! = ? ??? ?????? ? ?! = ?? c ? ?! ?! = ?? d ??! = ? ??? ??? ??? ? e ? How many ways of arranging the letters of: PLUM ?! = ?? APPLE ?! ? = ?? RASPBERRY ?! ?! = ?? ??? 2 ??? a b c
Exercise 2 Exercises on provided sheet. How many ways are there of arranging the letters in the words: a. SMURF ?! = ??? b. BOTTLE ?! ?! = ??? c. CABBAGE ?! ?!?! = ???? d. TITILLATION ??! ?!?!?! = ?????? A queue in the post office consists of a cat, a dog and a llama. How many possible orderings are there of animals in the line? Solution: ?! = ? ? 4 1 ? ?? ? A bag contains 8 different coloured balls. I pick 4 of them and put them in a line. How many ways are there of doing this? Solution: ? ? ? ? = ???? ? 2 [TMC Regional 2009 Q1] A tile is fixed to a wall and then painted with four different colours, one for each quarter. One way of doing this is 5 I have cards with the number 1, 2, 3, 4 on them. I have a plentiful supply of each. How many ways are there of: a. Putting four numbers in a line where all numbers must be different. ?! = ?? b. Putting four numbers in a line where we are unrestricted in choices of numbers. ??= ??? c. Putting four numbers in a line where each number must not be the same as the one immediately before. ? ??= ??? d. Forming a four digit number starting with 3. 3 In how many otherways may the tile be painted??! ? = ?? ? ? [JMO 1999 A5] UKMT, TMUK and KTUM are all different arrangements of the letters U, K, M and T. If the number of all the different arrangements of these four letters is ? and the number of all the different arrangements of the letters ?,?,?,? and ? is ?, what is the value of ? ? ? Solution: ?! 6 ? ? ? ??= ?? ?!=? ?! ? = ? ?!
Exercise 2 Exercises on provided sheet. [TMC Regional 2013 Q8] Claire, David, Jean and Richard are queuing for the bus. In how many different ways can they line up in single file, one behind the other, without Jean being last? [JMC 2013 Q25] For Beatrix s latest art installation, she has fixed a 2 2 square sheet of steel to a wall. She has two 1 2 magnetic tiles, both which she attaches to the steel sheet, in any orientation, so that none of the sheet is visible and the line separating the two tiles cannot be seen. As shown alongside, one tile has one black cell and one grey cell; the other tile has one black cell and one spotted cell. How many different looking 2 2 installations can Beatrix obtain? A 4 B 8 C 12 D 14 E 24 8 7 ? Solution: Starting from the back ? ? ? ? = ?? [Kangaroo Pink 2015 Q18] Petra has three different dictionaries and two different novels on a shelf. How many ways are there to arrange the books if she wants to keep the dictionaries together and the novels together? A 12 B 24 D 60 E 120 Solution: B (Can either have books- novels or novels-book, giving 2 lots of ?! ?!) 9 Solution: C C 30 The dotted tile can go in 4 positions. This leaves 3 positions for the grey tile. The rest are filled with black (with no choice involved). ? ? = ?? ? ?
Exercise 2 Exercises on provided sheet. [IMC 2015 Q20] A voucher code is made up of four characters. The first is a letter: V, X or P. The second and third are different digits. The fourth is the units digit of the sum of the second and third digits. How many different voucher codes like this are there? A 180 B 243 C 270 D 300 E 2700 [IMC 2008 Q23] Beatrix has a 24-hour digital clock on a glass table-top next to her desk. When she looked at the clock at 13:08, she noticed that the reflected display also read 13:08, as shown. How many times in a 24-hour period do the display and its reflection give the same time? A 12 B 36 D 72 E 96 10 11 C 48 Solution: C. 3 choices for first character. 10 choices for second character and 9 for third (since a different digit). There is no element of choice for the fourth character as it is determined by the second and third. Solution: E. First note that 0, 1, 3 and 8 reflect. ? ? ? ? ? = ?? ? ? ?? ? = ???
Exercise 2 Exercises on provided sheet. [Kangaroo Grey 2006 Q16/Pink 2006 Q19] A train consists of five carriages: I, II, III, IV and V. In how many ways can the carriages be arranged so that carriage I is nearer to the locomotive than carriage II is? A 120 B 60 C 48 D 30 E 10 12 Solution: B Long way: I is in 1st position: ?! = ?? ways of arranging remaining carriages. I is in 2nd position: ? ?! = ?? ways ? I is in 3rd position: ? ? ? = ?? ways I is in 4th position: ?! = ? ways ?? + ?? + ?? + ? = ?? ways Really Short way: In half of the ?! = ??? ways of arranging the five carriages, I will appear before II. ??? ? = ??
The Choose Function ?1 ?2 ?3 ?4 ?5 How many ways are there of selecting 2 balls from the 5? (such that the order of the balls in my selection does not matter) There are 5 balls for our first choice. There are then 4 balls to choose from. This initially gives 20 possibilities. ? However, ?1?4 for example would represent the same choice as ?4?1. We therefore have to divide by 2 to avoid duplicates. There are 10 possible selections. ??? (often written ? choosing ? items from ? without duplicates, such that order does not matter. ? ? ?! ? ? ! ?), said ? choose ? , is the number of ways of ?! =
Practise using the formula (and your calculator) 10! 1!9!= 10 9! 10 1 9 3 ? ? = = 3!6!= 84 Broculator Tip: Use the ??? button on your calculator (SHIFT ) to calculate directly. What would we expect this to be? (The number of ways of choosing 1 item from 10) 4! 4 0 ? = 0!1!= 1 Note that no selection is itself a choice! Bro Side Note: The choose formula only works if 0! = 1 What would we expect this to be? (The number of ways of choosing 0 items from 4)
Examples Q In the UK National Lottery, you pick 6 numbers out of 59. How many possible lottery tickets are there? ?? ? = ?? ??? ??? ? Q Bob the Teacher needs to form a maths team for a competition. He needs 3 boys and 3 girls for the team. He has 10 boys and 10 girls to choose from. How many possible teams are there? ?? ? ?? = ?? ??? ? ?
Test Your Understanding A Bob the Football Manager needs to select 11 players from his squad of 15 players. How many possible selections are there? ?? ?? = ???? ? B I have a bowl of 5 pieces of fruit, containing an orange, apple, banana, grapefruit and kiwi. I also have in my cupboard 4 chocolate bars: a Kit Kat, Snickers, Mars Bar and Twix. If I want two pieces of fruit and two chocolate bars for my lunch, how many possible selections are there? ? ? ? = ?? ? ? In this grid of 16 squares, I choose 4 to colour red followed by 4 to colour yellow. Determine the number of possible colourings. ?? ? ?? = ?????? ? ?
Exercise 2 Exercises on provided sheet. I am building a car park and need to choose 2 of the 20 spaces to be disabled parking spaces. How many ways are there of doing this? Solution: 190 ? Alice is asked to think of 3 different numbers between 1 and 8, and Bob is asked to do the same. How many total possible combinations are there for Alice and Bob s selection combined? Solution: ?? ?? = ???? ? 1 5 In a lottery I can choose 4 distinct numbers between 1 and 20. How many possible lottery tickets are there? Solution: 4845 2 ? As part of winning a car, I have to choose 4 numbers between 1 and 15 and throw three dice. How many total possible outcomes are there? Solution: ???? ??= ?????? ? 6 Of 9 balls in a line, 5 need to be painted red (and those not chosen will be painted blue). How many ways are there of doing this? Solution: 126 ? 3 Of 9 balls in a line, 4 need to be painted blue (and those not chosen will be painted red). a. How many ways are there of doing this? Solution: 126 b. Hence, what other choose will have the same value as 50 4 I choose 4 distinct numbers between 1 and 8. How many possibilities are there where the numbers in my selection add to give an even number? ? 7 ? 20? Sln: ?? ?? ? Solution: It will be half of them. 35
Exercise 2 Use your calculator to write 0 Exercises on provided sheet. A beaver travels from the bottom-left hand corner to the top-right corner of a 4 4 grid, each time only making up or right movements. One possible paths is as pictured. a. How many possible paths are there? Solution: Of the 8 moves 4 need to be right moves. ? 0 on a 8 9 row in your book. On the next row write 1 1. On the next row write 2 0 this pattern for a few more rows, where the top number increases by 1 for each row, and the bottom number varies between 0 and the top number. a. What do you notice about the numbers you get in your structure? You get Pascal s Triangle! b. Add up the numbers in each row (your first two totals should be 1 and 2). What do you notice? You get powers of 2! 0 and 1 ,2 1 and 2 2. Continue ? = ?? ? (Hint: write a few possible paths as a sequence of arrows, e.g. . What s always the same about such valid sequences of moves?) b. If the beaver is travelling across a ? ? grid, write an expression for the total number of paths in terms of ?. Solution:?? ? ? ? Finish ? Start
Exercise 2 Exercises on provided sheet. I choose 5 numbers between 1 and 20. How many choices are there such that the range of the numbers in my selection is 6? Solution: Suppose the smallest number was 1 and the largest 7. Then the remaining three numbers can be chosen between 2 and 6, giving ? ? We ll have the same number of possibilities where the smallest and largest numbers are 2 and 8, and so on, up to 14 and 20. = ?? possibilities. ? That s ?? ?? = ??? possibilities.
Levelled Activity (Teacher Note: See printout) Level 3 Level 2 Level 1 Instructions: You may work in pairs. Start on the Level 1 problems provided, recording your answer on this sheet. Answers to Level 1 questions are at the front of the class. Once you ve checked your answers, go to your teacher and ask for Level 2. You will need to ask the teacher to check your answers to Level 2 and beyond. Solutions are on the next slides.
Level 1 Solutions How many possible 3 letters words are there using letters from the English alphabet. Solution: ???= ????? ? How many ways can I arrange 6 books on a shelf? Solution: ?! = ??? ? 1 5 How many ways can you arrange the letters of the word CATTLE? Solution: ?! ?!= ??? ? 6 I take 4 items from 7 and put them in a line. How many possibilities are there? Solution: ? ? ? ? = ??? ? 2 [JMC 2000 Q11] The digits of this year, 2000 A.D., add up to 2. In how many other years since 1 A.D. has this happened? Solution: 9 7 From 9 people I choose 4 people to form a team. How many possible teams are there? 3 Solution: ? ? ? = ??? ? How many squares of any size are in this diagram? Solution: ?? + ? + ? + ? = ?? ? [JMC 2007 Q7] The equilateral triangle ??? is fixed in position. Two of the four small triangles are to be painted black and the other two are to be painted white. In how many different ways can this be done? Solution: ? ? ? 8 4 = ?
Level 2 Solutions How many possible combinations of outcomes are there from the throw of three dice and five coins? Solution: ?? ??= ???? ? [TMC Regional 2012 Q9] In how many ways can you split your team of 4 people into two separate teams, so that there is at least one person in each team? Solution: 7 ways ? 1 4 [JMO 2006 A4] An equilateral triangle is drawn on a sheet of white card and divided into three identical regions as shown. Then each region is painted red or yellow or blue. More than one region may be painted in the same colour. How many different painted triangles can be made in this way? (Rotating a triangle does not make it different.) Solution: 11 ? 2 [Kangaroo Grey 2009 Q16] How many ten-digit numbers are there which contain only the digits 1, 2 or 3, and in which any pair of adjacent digits differs by 1? A 16 B 32 D 80 E 100 Solution: C. 5 C 64 If the number starts with 2, the next is 1 or 3, the next is 2, and so on. When we don t have a 2 we have two choices, so ??= ??. But we could had 2 second, giving another 32 possibilities. ? [JMO 2008 A4] How many three-digit numbers have the product of their digits equal to 6? Solution: 9 ? 3
Level 3 Solutions [Cayley 2008 Q1] How many four-digit multiples of 9 consist of four different odd digits? Solution: 24. Digits have to add up to multiple of 9: only possibility for digits is 1359. There s 4! ways of arranging these. ? [SMC 2005 Q16] A hockey team consists of 1 goalkeeper, 4 defenders, 4 midfielders and 2 forwards. There are 4 substitutes: 1 goalkeeper, 1 defender, 1 midfielders and 1 forward. A substitute may only replace a player of the same category, e.g. midfielder for midfielders. Given that a maximum of 3 substitutes may be used and that there are still 11 players on the pitch at the end, how many different teams could finish the game? A 110 B 118 D 125 E 132 1 3 [IMC 2010 Q24] A new taxi firm needs a memorable phone number. They want a number which has a maximum of two different digits. Their phone number must start with the digit 3 and be six digits long. How many such numbers are possible? A 288 B 280 C 279 D 226 E 225 If other digit is different 0, then there are 2 choices for each of the 5 other digits, giving ??= ?? possibilities. However, we want to exclude the case where they re all 3s (for the moment), giving 31 possibilities There s 9 numbers this other digit could be giving ? ?? = ???. Then we count the one possibility where all the digits are 3, giving 280. 2 C 121 ? ? Solution: B
Level 3 Solutions [Kangaroo Pink 2007 Q24] At a party, five girls give each other gifts in such a way that everybody gives one gift and everybody receives one (though of course nobody receives their own gift). How many possible ways are there for this to happen? A 5 B 10 D 50 E 120 Solution: C. Suppose the girls are ABCDE. Then to avoid giving themselves a present, we either have to have a cycle of 3 and 2 (e.g. ABC give each other presents, and DE give each other one) or a cycle of 5. There are ? ? 6 4 [JMO 2004 A10] The Famous Five have been given 20 sweets as a reward for solving a tricky crime. They have agreed that the oldest of them must receive more than the next oldest, who must receive more than the next oldest, and so on. Assuming that each of the five gets at least one sweet, in how many different ways can they share the sweets? Solution: 7 ? C 44 [JMO 2002 B1] A number like 4679 is called an ascending number because each digit in the number is larger than the preceding one. (i) How many ascending numbers are there between 1000 and 2000? (ii) How many ascending numbers are there between 1000 and 10000? 5 = ?? ? possible groupings for 2-3 cycles, where for each there s only 2 possible giving of presents, giving 20 possibilities. If the cycle is 5, then there s ?! = ?? possibilities (as A had 4 people he can give his present to, then B has 3, etc.) ? Solution: 56 and 126
Level 3 Solutions [SMC 2001 Q21] A postman s sack contains five letters, one each for the five houses in Cayley Close. Mischievously, he posts one letter through each door without looking to see if it is the correct address. In how many different ways could he do this so that exactly two of the five houses receive the correct letters? A 5 B 10 C 20 7 D 30 E 60 There are ? = ?? ways in which we could choose 2 houses to receive the correct ? letter. Then of the remaining 3 houses, there are only 2 ways in which they could receive the wrong letter (if the houses are ABC, then the letters could be BCA or CAB). ? That gives ?? ? = ?? ways.
