Systematic lists and the product rule · Higher
Introduced| English | Meaning |
|---|---|
| systematic list/ˌsɪstəˈmætɪk lɪst/ | An ordered list made using a consistent method so that all required possibilities are included without repetition. |
| product rule/ˈprɒdʌkt ruːl/ | If one choice has m options and another has n, together there are m × n options. |
43 quintillion positions
- Ernő Rubik built his cube in 1974. It can be twisted into about $4.3 \times 10^{19}$ different positions, yet any one can be solved in 20 moves or fewer.
- Numbers that large come from multiplying choices, not from listing them.
From lists to a rule
- A systematic list 系统列表 shows the pattern: 2 drinks × 3 fruits = 6 meals.
- The product rule 乘法原理: if one choice can be made in $m$ ways and a second in $n$ ways, together there are $m \times n$ ways.
A menu has 4 starters, 6 mains and 3 desserts. How many three-course meals are possible?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$4 \times 6 \times 3 = 72$.
Arrangements without repeats
- Each choice uses up one option: 5 runners can finish 1st, 2nd and 3rd in $5 \times 4 \times 3 = 60$ ways.
- With repeats allowed, the options stay the same: a 3-digit code from 0–9 has $10^3 = 1000$ choices.
In how many ways can gold, silver and bronze be given to 8 runners?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$8 \times 7 \times 6 = 336$.
How many 4-digit PINs use the digits 0–9 with repeats allowed?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$10^4$.
Worked example: codes with a rule
A 4-character code is two letters (A–Z) then two digits (0–9). The digits must be different.
- Letters: $26 \times 26 = 676$.
- Digits: $10 \times 9 = 90$, because the second digit cannot repeat the first.
- Total: $676 \times 90 = 60\,840$ codes.
Systematic lists and the product rule
Fix one first choice and list every permitted second choice before moving to the next first choice
Compare the model with the worked case and explain one change.
When order does not matter
- Choosing 2 people from 6 for a team: $6 \times 5 = 30$ ordered pairs, but each team is counted twice (AB and BA).
- So there are $\dfrac{30}{2} = 15$ teams.
How many different pairs can be chosen from 10 students?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\dfrac{10 \times 9}{2} = 45$.
Restrictions first
- Fill the restricted position first. Odd 3-digit numbers from 1–6, no repeats: last digit 3 ways (1, 3, 5), then $5 \times 4$ for the others: $3 \times 5 \times 4 = 60$.
- "At least one" is often easier as total minus "none".
How many 3-digit even numbers can be made from 1, 2, 3, 4, 5 without repeats?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Last digit 2 ways (2 or 4), then $4 \times 3$: $2 \times 4 \times 3 = 24$.
Do not add when you should multiply. 3 shirts and 4 trousers give $3 \times 4 = 12$ outfits, not 7. Add only when the choices are alternatives ("a shirt or a jacket").
5 hats and 3 scarves give 8 hat-and-scarf combinations.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$5 \times 3 = 15$.
Multiply the number of options at each stage. Reduce the options when repeats are not allowed, handle restricted positions first, and divide out repeats when order does not matter.
A password is 3 different letters from A–E followed by one digit from 0–9. How many passwords are there? How many start with A?
Product rule with a restriction.