The Lumenary · Grades 3–5

Systematic listing and counting

Name: ______________________

Date: ______________________

You will learn to

List all the possibilities in small problems, such as outfits, routes and meals, using an organised list, a table or a tree diagram
Explain how a system guarantees that no possibility is missed and none is repeated
Discover and explain the rule that m first choices and n second choices give m × n combined choices
Find all the ways to arrange three or four objects in a row
Count handshakes without counting any handshake twice

1.
Kwame has 4 shirts and 3 pairs of shorts, all different. How many different outfits (one shirt and one pair of shorts) can he make?
2.
From Farida's village there are 3 paths down to the river, and from the river 4 roads to the market. A route is one path followed by one road. How many different routes are there from the village to the market?
3.
A canteen offers 2 soups, 3 main dishes and 2 drinks. A meal is one soup, one main dish and one drink. How many different meals are there?
4.
Lerato has red, blue and yellow T-shirts and black and brown trousers. She calls out: red–black, blue–brown, red–brown, yellow–black, blue–black. Then she says, "I can't think of any more, so that's all of them." What is the best reply?
- A.She is right: if she can't think of more, there are no more.
- B.Go T-shirt by T-shirt: red has both, blue has both, but yellow is missing brown. There are 6.
- C.There should be 5, because 3 + 2 = 5, so she has them all.
5.
Using the digit cards 1, 5 and 7 (each card at most once), list every two-digit number you can make. Write them separated by commas, like {12, 34}.
6.
Mei has 4 different books to put in a row on a shelf. In how many different orders can she arrange them?
7.
Six friends meet, and every two of them shake hands exactly once. How many handshakes are there?
8.
In a chess club in Nairobi, 8 players each play every other player exactly once. How many games are played?
9.
In Lean, pairs as bs is the organised list of all pairs from a list as of first choices and a list bs of second choices. Which Lean statement says the product rule?
- A.(pairs as bs).length = as.length * bs.length
- B.(pairs as bs).length = as.length + bs.length
- C.(pairs as bs).length = as.length
- D.(a, b) ∈ pairs as bs ↔ a ∈ as ∧ b ∈ bs
10.
Complete outfits(tops, bottoms) so that it returns a list of every pair (top, bottom), each exactly once. Use the system from the lesson: one loop for the tops, and inside it a loop for the bottoms.
Computational — Practice

Answer key — Systematic listing and counting

1.
Each of the 4 shirts goes with each of the 3 pairs of shorts. A table has 4 rows and 3 columns, so there are $4 \times 3 =$ 12 outfits.
2.
For each of the 3 paths there are 4 roads to choose next. The tree has $3 \times 4 =$ 12 paths from start to end, so there are 12 routes.
3.
There are $2 \times 3 = 6$ ways to choose a soup and a main dish, and each can go with 2 drinks: $6 \times 2 =$ 12 meals. A tree diagram with three levels has 2, then 6, then 12 branches.
4.
The product rule gives $3 \times 2 = 6$ outfits, and she has 5. Going T-shirt by T-shirt: red–black ✓ red–brown ✓, blue–black ✓ blue–brown ✓, yellow–black ✓ yellow–brown ✗. The missing outfit is yellow–brown. A system finds it; "I can't think of any more" does not.
5.
Fix the tens digit and run through the ones digits that are left:
- tens digit 1: 15, 17
- tens digit 5: 51, 57
- tens digit 7: 71, 75
That is $3 \times 2 = 6$ numbers: 3 choices for the tens digit, then 2 cards left for the ones digit.
6.
Fill the places from left to right: 4 choices for the first place, then 3, then 2, then 1. By the product rule there are $4 \times 3 \times 2 \times 1 =$ 24 orders.
7.
Listing each handshake once: $5 + 4 + 3 + 2 + 1 = 15$ . Or count each person's handshakes, $6 \times 5 = 30$ , and halve, because every handshake was counted twice: $30 \div 2 =$ 15.
8.
Each of the 8 players plays 7 games, which gives $8 \times 7 = 56$ — but each game has two players, so it was counted twice. There are $56 \div 2 =$ 28 games. (Check by listing: $7 + 6 + 5 + 4 + 3 + 2 + 1 = 28$ .)
9.
The product rule says the number of combined choices is the product of the numbers of choices: in Lean, (pairs as bs).length = as.length * bs.length. The statement with ↔ is the companion theorem saying a pair is on the list exactly when both parts are allowed choices.
10.
Hold each top still and run through all the bottoms:
```
def outfits(tops, bottoms):
    result = []
    for top in tops:
        for bottom in bottoms:
            result.append((top, bottom))
    return result
```
The outer loop is the first level of the tree diagram and the inner loop is the second, so the list has len(tops) * len(bottoms) pairs, each exactly once.