Sets and Counting · applications

Applications: Sets and Counting

10 question types · Pre-University · each worked step by step with a figure that follows the steps

O-Level · H2

01

A Survey of Three Languages, Where the Students Taking All Three Are Found from the Totals

methodWrite the Union by Inclusion-Exclusion, Solve for the Center, Then Fill the Venn Diagram from the Middle Outwards

A school surveyed 120 students about the languages they study. 50 study French, 40 study German and 45 study Spanish. 15 study both French and German, 18 study both French and Spanish, and 12 study both German and Spanish. 24 students study none of the three languages. (a) How many students study all three languages? (b) How many students study exactly one of the three languages?

FrenchGermanSpanish120 studentsnone 24at least one language: 120 − 24 = 96
The students who study at least one language are n(F ∪ G ∪ S) = 120 − 24 = 96.
Let x = n(F ∩ G ∩ S), the number who study all three languages. The students who study at least one language are n(F ∪ G ∪ S) = 120 − 24 = 96.
step 1 of 6

Let F, G and S be the sets of students who study French, German and Spanish. The three single totals count a student in two sets twice and a student in all three sets three times. Inclusion-exclusion corrects that: n(F ∪ G ∪ S) = n(F) + n(G) + n(S) − n(F ∩ G) − n(F ∩ S) − n(G ∩ S) + n(F ∩ G ∩ S). The union is known from the students who study none, so the one unknown, the center of the Venn diagram, can be found. Every other region then follows from the center.

  1. Let x = n(F ∩ G ∩ S), the number who study all three languages. The students who study at least one language are n(F ∪ G ∪ S) = 120 − 24 = 96.
  2. Write the union by inclusion-exclusion: 96 = 50 + 40 + 45 − 15 − 18 − 12 + x.
  3. Simplify the right-hand side: 96 = 135 − 45 + x = 90 + x, so x = 6. (a) 6 students study all three languages.
  4. Put 6 in the center of the Venn diagram. Each pair total includes the center, so the regions for exactly two languages are 15 − 6 = 9 (French and German), 18 − 6 = 12 (French and Spanish) and 12 − 6 = 6 (German and Spanish).
  5. Take everything else in each circle away from its total. French only: 50 − 9 − 12 − 6 = 23. German only: 40 − 9 − 6 − 6 = 19. Spanish only: 45 − 12 − 6 − 6 = 21.
  6. (b) Exactly one language: 23 + 19 + 21 = 63 students. Check: the seven regions add up to 63 + 9 + 12 + 6 + 6 = 96, the number who study at least one language.

answer(a) 6 students; (b) 63 students

techniqueVenn Diagrams · Counting a Union · Set Notation

examsO-Level · GCSE Higher · H2

Common pitfalls

  • Adding the three totals and taking off the three pair totals, 135 − 45 = 90, and stopping there. The students in all three sets were counted three times and then taken off three times, so they are not counted at all; the +x puts them back.
  • Writing 15 in the French and German region of the diagram. The 15 students who study French and German include the 6 who also study Spanish, so the region for those two languages only holds 15 − 6 = 9.
02

Two Mailing Lists Merged, So That No Customer Receives the Same Email Twice

methodAdd the Two Lists and Take Off the Addresses on Both Once, Then Subtract the Union from the Universal Set

A shop has 2500 customers on its records. 1240 of them are on the newsletter list A and 860 are on the events list B. 310 customers are on both lists. The shop sends one email to every customer on at least one list, and no customer receives it twice. (a) How many emails does the shop send? (b) Find n((A ∪ B)'), the number of customers who receive no email.

A newsletterB events2500 customers310n(A) = 1240, n(B) = 860, n(A ∩ B) = 310
The universal set is the 2500 customers, and the 310 on both lists go in the overlap.
In set notation, n(ξ) = 2500, n(A) = 1240, n(B) = 860 and n(A ∩ B) = 310.
step 1 of 5

The universal set ξ is the 2500 customers. Adding n(A) and n(B) counts every customer in A ∩ B twice, so the overlap is taken off once: n(A ∪ B) = n(A) + n(B) − n(A ∩ B). The customers on neither list are the complement of the union, everything in ξ outside A ∪ B.

  1. In set notation, n(ξ) = 2500, n(A) = 1240, n(B) = 860 and n(A ∩ B) = 310.
  2. Fill the Venn diagram from the overlap outwards. Newsletter only: n(A ∩ B') = 1240 − 310 = 930. Events only: n(A' ∩ B) = 860 − 310 = 550.
  3. (a) The shop sends one email to each customer in A ∪ B: n(A ∪ B) = 1240 + 860 − 310 = 1790 emails.
  4. Check with the regions: 930 + 310 + 550 = 1790.
  5. (b) The customers outside both circles are n((A ∪ B)') = 2500 − 1790 = 710.

answer(a) 1790 emails; (b) 710 customers

techniqueCounting a Union · Set Notation · Complements and Subsets

examsO-Level

Common pitfalls

  • Sending 1240 + 860 = 2100 emails. The 310 customers on both lists are counted in both totals, so that plan emails each of them twice.
  • Answering (b) with 2500 − 1240 − 860 = 400. Taking both lists away removes the 310 customers on both lists twice; the union, 1790, must be taken away once.
03

Late Trains on Wet and Dry Days, and How Many Times as Likely a Delay Is on a Wet Day

methodLet the Given Weather Choose the Row, Use That Row's Total as the Denominator, and Compare the Two Conditional Probabilities

A rail company recorded 200 journeys on one line. 60 of them were on wet days, and 24 of those were late. The other 140 were on dry days, and 14 of those were late. (a) A journey on a wet day is chosen at random. Find the probability that it was late. (b) How many times as likely is a journey to be late on a wet day as on a dry day?

LateOn timeTotalWet243660Dry14126140Total3816220060 − 24 = 36 and 140 − 14 = 12624 + 14 = 38 and 36 + 126 = 162
Complete the table: 36 and 126 journeys were on time, and the columns total 38 and 162.
Complete the two-way table. On wet days 60 − 24 = 36 journeys were on time, and on dry days 140 − 14 = 126. The Late column totals 24 + 14 = 38 and the On time column 36 + 126 = 162.
step 1 of 5

Let L be the event that a journey was late and R the event that it was on a wet day. P(L | R) is the probability of a late journey given a wet day: the condition picks out the Wet row of the two-way table, and that row's total is the denominator. Comparing P(L | R) with P(L | R') shows how much the weather changes the chance of a delay.

  1. Complete the two-way table. On wet days 60 − 24 = 36 journeys were on time, and on dry days 140 − 14 = 126. The Late column totals 24 + 14 = 38 and the On time column 36 + 126 = 162.
  2. (a) Given a wet day, the whole is the Wet row, 60 journeys, and 24 of them were late: P(L | R) = 2460 = 25.
  3. Given a dry day, the whole is the Dry row, 140 journeys: P(L | R') = 14140 = 110.
  4. (b) Divide one conditional probability by the other: 25 ÷ 110 = 25 × 10 = 4. A journey is 4 times as likely to be late on a wet day.
  5. Check: over all 200 journeys, P(L) = 38200 = 19100. That is not equal to P(L | R) = 25, so lateness and the weather are not independent, which agrees with (b).

answer(a) 25; (b) 4 times as likely

techniqueConditional Probability from Tables · Probability in Set Notation

examsSAT · GCSE Higher · H2

Common pitfalls

  • Answering (a) with 24200. That is P(L ∩ R), the probability that a journey chosen from all 200 was both wet and late. Given a wet day, only the 60 wet journeys can be chosen.
  • Comparing the counts 24 and 14 and saying a wet day is less than twice as likely to bring a delay. There were far fewer wet journeys, so the counts must first be divided by their own row totals.
04

Six Friends in a Row for a Photograph, Where Two of Them Must Stand Together

methodTie the Two Who Must Be Together into One Block, Arrange the Blocks, Then Arrange Inside the Block; Take the Answer from All Orders for Apart

Six friends, including Amir and Bea, stand in a row for a photograph. (a) In how many different orders can they stand if Amir and Bea must stand next to each other? (b) In how many orders are Amir and Bea not next to each other?

the block AB and 4 friends: 5 placesAB543215 × 4 × 3 × 2 × 1 = 5! = 120
Tie Amir and Bea into one block: the block and the other 4 friends stand in 5! = 120 orders.
Tie Amir and Bea into one block. The block and the other 4 friends are 5 items, which stand in a row in 5! = 5 × 4 × 3 × 2 × 1 = 120 orders.
step 1 of 5

n different people can stand in a row in n! = n × (n − 1) × … × 1 orders. When two people must be together, treat them as one block: the block and the other four friends are 5 items. The two inside the block can then stand in 2! orders. For (b), every order has the pair either together or apart, so apart is all the orders minus together.

  1. Tie Amir and Bea into one block. The block and the other 4 friends are 5 items, which stand in a row in 5! = 5 × 4 × 3 × 2 × 1 = 120 orders.
  2. Inside the block, Amir can stand on the left or on the right: 2! = 2 orders.
  3. (a) Multiply the two choices: 2 × 120 = 240 orders with Amir and Bea together.
  4. Without any rule, the six friends stand in 6! = 720 orders.
  5. (b) Every order has the two either together or apart, so apart is 720 − 240 = 480 orders. Check: 240720 = 13, and of the 62 = 15 pairs of places the two can take, 5 are side by side, which is also 13.

answer(a) 240 orders; (b) 480 orders

techniqueRepeats and Restrictions · Factorials · Permutations

examsH2

Common pitfalls

  • Forgetting the order inside the block and answering 120. Amir then Bea and Bea then Amir are different photographs, so the 5! orders of the blocks are doubled.
  • Counting (b) as 4! or 6! − 5!. The together case is 2 × 5! = 240, and only that number is taken from 6!.
05

A Residents' Committee of Four Chosen from Seven Women and Five Men

methodChoose from Each Group Separately and Multiply; for At Least One, Take the Committees with None from All the Committees

A residents' association chooses a committee of 4 from 7 women and 5 men who have volunteered. (a) How many different committees have exactly 2 women and 2 men? (b) How many different committees include at least one man?

7 women: choose 25 men: choose 27C2 = 21 and 5C2 = 10
(a) Choose 2 of the 7 women, 72 = 21 ways, and 2 of the 5 men, 52 = 10 ways.
(a) Choose 2 of the 7 women: 72 = 7 × 62 × 1 = 21 ways. Choose 2 of the 5 men: 52 = 5 × 42 × 1 = 10 ways.
step 1 of 5

A committee is a selection, so the order does not matter: r people can be chosen from n in nr = n!r!(n − r)! ways. Choosing the women and choosing the men are two steps in a row, so their counts multiply. At least one man covers four cases; its complement, no man at all, is one case, so it is quicker to count that and subtract.

  1. (a) Choose 2 of the 7 women: 72 = 7 × 62 × 1 = 21 ways. Choose 2 of the 5 men: 52 = 5 × 42 × 1 = 10 ways.
  2. Each choice of women goes with each choice of men, so multiply: 21 × 10 = 210 committees.
  3. All committees of 4 from the 12 volunteers: 124 = 12 × 11 × 10 × 94 × 3 × 2 × 1 = 495.
  4. The committees with no man are chosen from the women only: 74 = 7 × 6 × 5 × 44 × 3 × 2 × 1 = 35.
  5. (b) At least one man is the complement of no man: 495 − 35 = 460 committees. Check by cases: 7351 + 210 + 7153 + 54 = 175 + 210 + 70 + 5 = 460.

answer(a) 210 committees; (b) 460 committees

techniqueCombinations · Adding and Multiplying Choices · Complements and Subsets

examsO-Level · H2

Common pitfalls

  • Adding 21 + 10 in (a). Choosing the women and choosing the men both happen for every committee, so the counts multiply; adding is for alternatives, one or the other.
  • Counting (b) as 5 × 113 = 825: one man first, then any three others. A committee with two men is then counted once for each of its men, so the total is too large.
06

Letter Tiles Spelling SUCCESS, Where Repeated Letters Make Many Orders Look the Same

methodArrange the Letters as if All Were Different, Then Divide by the Swaps of Each Repeated Letter That Cannot Be Seen

In a word game, a player has the seven tiles S, U, C, C, E, S, S. (a) How many different seven-letter arrangements of the tiles can be made? (b) In how many of these arrangements are the three S tiles next to each other?

seven tilesSUCCESSif all different: 7! = 5040
If the seven tiles were all different, they would have 7! = 5040 orders.
If the seven tiles were all different, they could be arranged in 7! = 5040 orders.
step 1 of 5

If the seven tiles were all different there would be 7! orders. Swapping the three S tiles among themselves, 3! ways, gives an arrangement that looks the same, and so does swapping the two C tiles, 2! ways. So each different-looking arrangement was counted 3! × 2! times, and dividing by that removes the repeats.

  1. If the seven tiles were all different, they could be arranged in 7! = 5040 orders.
  2. The three S tiles can be swapped among themselves in 3! = 6 ways and the two C tiles in 2! = 2 ways, and none of these swaps changes what the word looks like.
  3. (a) Each different arrangement was counted 6 × 2 = 12 times, so there are 504012 = 420 different arrangements.
  4. For (b), treat SSS as one tile. The tiles are then SSS, U, C, C and E: 5 tiles with the C repeated twice, so there are 5!2! = 1202 = 60 arrangements.
  5. (b) 60 of the 420 arrangements have the three S tiles together. Check: 60420 = 17. The three S tiles take 3 of the 7 places in 73 = 35 ways, and 5 of those are side by side: 535 = 17.

answer(a) 420 arrangements; (b) 60 arrangements

techniqueRepeats and Restrictions · Factorials

examsH2

Common pitfalls

  • Dividing by 3! + 2! = 8 instead of 3! × 2! = 12. Every swap of the S tiles can be combined with every swap of the C tiles, so the numbers of swaps multiply.
  • Multiplying the 60 in (b) by 3! for the orders inside the SSS block, as for two people who stand together. The three S tiles look the same, so their orders inside the block give only one arrangement.
07

A Four-Digit Door Code, With and Without a Repeated Digit

methodDraw One Slot per Digit, Write the Number of Choices Under Each and Multiply; Count At Least One Repeat as All Codes Minus None

An office door is opened by a four-digit code, and each digit can be any of 0 to 9. (a) How many codes have four different digits? (b) How many codes have at least one digit repeated?

any digit in each place1010101010 × 10 × 10 × 10 = 10000 codes
With no rule, each slot has 10 choices: 10 × 10 × 10 × 10 = 10000 codes.
With no rule, each of the four slots has 10 choices, so there are 10 × 10 × 10 × 10 = 10000 codes.
step 1 of 4

The multiplication principle: when a choice is made in steps, one after another, the numbers of choices at each step multiply. Draw a slot for each digit and write under it how many digits are still allowed there. At least one repeat is the complement of all different, so it is every code minus the codes with no repeat.

  1. With no rule, each of the four slots has 10 choices, so there are 10 × 10 × 10 × 10 = 10000 codes.
  2. With four different digits, the first slot has 10 choices. The second cannot repeat the first, so it has 9; the third has 8 and the fourth 7.
  3. (a) Multiply the choices: 10 × 9 × 8 × 7 = 5040 codes. This is the number of permutations of 4 digits from 10, 10P4 = 10!6!.
  4. (b) Every code either has four different digits or repeats at least one digit, so at least one repeat is 10000 − 5040 = 4960 codes. Check: 5040 + 4960 = 10000.

answer(a) 5040 codes; (b) 4960 codes

techniqueAdding and Multiplying Choices · Permutations · Complements and Subsets

examsGCSE Higher · H2

Common pitfalls

  • Counting four different digits as 104 = 210. The code 1234 and the code 4321 open different doors, so the order matters and the count is a permutation, not a combination.
  • Counting (b) directly as a single case, such as 10 × 1 × 10 × 10 for a first digit repeated. Repeats can happen in many places and more than once, so the complement is the reliable count.
08

Every Pizza a Shop Can Make from Eight Toppings

methodEach Topping Is In or Out, So a Set of 8 Has 2 to the Power 8 Subsets; Take Off the Subsets with Too Few Toppings

A pizza shop offers 8 different toppings, and a customer may choose any selection of them, including none at all for a plain cheese pizza. Each topping is used at most once. (a) How many different pizzas can be ordered? (b) How many of these pizzas have at least two toppings?

8 toppings, each on or off123456782 choices for each topping
Each of the 8 toppings is on the pizza or off it: 2 choices each.
For each of the 8 toppings there are 2 choices: put it on or leave it off.
step 1 of 4

A pizza is a subset of the set of 8 toppings. For each topping there are two choices, in or out, and the eight choices are made one after another, so they multiply: a set of n things has 2n subsets. That count includes the empty set, the plain pizza, and the set itself, every topping at once.

  1. For each of the 8 toppings there are 2 choices: put it on or leave it off.
  2. (a) The choices multiply: 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 28 = 256 different pizzas, counting the plain one.
  3. The pizzas with fewer than two toppings are the plain pizza, 1, and the pizzas with exactly one topping, 81 = 8.
  4. (b) At least two toppings: 256 − 1 − 8 = 247 pizzas. Check by adding the sizes: 82 + 83 + … + 88 = 28 + 56 + 70 + 56 + 28 + 8 + 1 = 247.

answer(a) 256 pizzas; (b) 247 pizzas

techniqueComplements and Subsets · Adding and Multiplying Choices · Combinations

examsO-Level

Common pitfalls

  • Answering (a) with 8! = 40320. That counts the orders in which the toppings could be put on, but a pizza with ham then olives is the same pizza as one with olives then ham.
  • Answering (a) with 28 − 1 = 255. The question counts the plain cheese pizza, which is the empty subset, so all 256 subsets are pizzas here.
09

Ropes and Triangles Between Twelve Posts in a Park, Five of Them Along a Straight Fence

methodEvery Pair of Points Makes a Line and Every Three Make a Triangle; Correct for the Points That Lie on One Line

A park designer has put up 12 posts. Five of them stand along a straight fence, none of the other seven stands on the fence's line, and no three of the other posts, or any two of them with a fence post, lie in a straight line. A straight rope can be stretched through any two posts. (a) How many different straight lines can the ropes follow? (b) How many triangles have three of the posts as their corners?

fenceevery pair: 12C2 = 66
If no three posts were in a line, each of the 122 = 66 pairs would give its own line.
If no three posts were in a line, every pair would give a different line: 122 = 12 × 112 = 66 lines.
step 1 of 5

Two points fix one line, and three points not in a line fix one triangle, so both counts start as combinations: 122 pairs and 123 threes. The five fence posts break this. Their 52 pairs all give the same line, the fence, so they count as one line; and any three of them are in a line, so they make no triangle.

  1. If no three posts were in a line, every pair would give a different line: 122 = 12 × 112 = 66 lines.
  2. The five fence posts give 52 = 5 × 42 = 10 pairs, but all ten lie on one line, the fence.
  3. (a) Take the 10 off and count the fence once: 66 − 10 + 1 = 57 different lines.
  4. Any three posts give a triangle unless they are in a line: 123 = 12 × 11 × 103 × 2 × 1 = 220 choices of three posts.
  5. (b) The choices of three fence posts, 53 = 10, lie on the fence and make no triangle: 220 − 10 = 210 triangles.

answer(a) 57 lines; (b) 210 triangles

techniqueCounting with Geometry · Combinations

examsO-Level · H2

Common pitfalls

  • Answering (a) with 66 − 10 = 56. The fence posts do give a line, the fence itself; it must be counted once, not removed.
  • Taking off only 5 in (b), one for each fence post. It is every choice of three posts along the fence that fails to make a triangle, and there are 53 = 10 of those.
10

An Inspector Tests Three Bulbs from a Box of Twelve, Four of Which Are Faulty

methodCount the Equally Likely Selections by Combinations, Count the Ones That Match, and Divide

A box holds 12 light bulbs, and 4 of them are faulty. An inspector takes 3 bulbs from the box at random, all at once. (a) Find the probability that none of the three bulbs is faulty. (b) Find the probability that exactly one of the three bulbs is faulty.

4 faulty and 8 good bulbs12C3 = 220 selections
Every set of 3 bulbs is equally likely, and there are 123 = 220 of them.
The number of equally likely selections of 3 bulbs from 12 is 123 = 12 × 11 × 103 × 2 × 1 = 220.
step 1 of 5

Taking three bulbs at once is a selection, so every one of the 123 sets of three bulbs is equally likely. The probability of an event is the number of those sets in it divided by the number of all sets. A set with exactly one faulty bulb is one faulty bulb from 4 and two good bulbs from 8, and those two choices multiply.

  1. The number of equally likely selections of 3 bulbs from 12 is 123 = 12 × 11 × 103 × 2 × 1 = 220.
  2. No faulty bulb means all three come from the 8 good bulbs: 83 = 8 × 7 × 63 × 2 × 1 = 56 selections.
  3. (a) P(none faulty) = 56220 = 1455.
  4. Exactly one faulty: choose the faulty bulb, 41 = 4 ways, and two good bulbs, 82 = 28 ways, giving 4 × 28 = 112 selections.
  5. (b) P(exactly one faulty) = 112220 = 2855. Check: two or three faulty is 4281 + 43 = 48 + 4 = 52 selections, and 56 + 112 + 52 = 220.

answer(a) 1455; (b) 2855

techniqueCombinations · Probability in Set Notation

examsO-Level · H2

Common pitfalls

  • Working (a) as (812)3, as if each bulb were put back before the next was taken. The bulbs are taken without replacement, so after one good bulb only 7 of the 11 left are good.
  • Forgetting the 41 in (b) and counting 28 selections. Each of the 4 faulty bulbs can be the one in the set, and each gives 28 different sets.
Mr. Chalk Read the guide