Skip to content

Codes and locks

Counting and combinations · level 2, lesson 4 of 6

A question to start

Max has a little lock on his toy box. It has 2 dials, and each dial shows a digit from 0 to 9. His sister wants to open it, and she tries one code every 2 seconds: 00, 01, 02, and so on. What is the longest it could take her?

And what if Max buys a lock with 3 dials instead? Does it take one and a half times as long? Twice as long? The answer is much more surprising than that, and it is the reason real locks and passwords work. Let's find out.

The idea

A code is a line-up where repeats are allowed

A code is a list of symbols in order, like 3 then 7. Order matters: the code 37 is not the code 73 (try opening a lock with the digits the wrong way round!). So a code is like a tower or a line-up from level 1.

But there is one big difference from lining up friends. A friend can only stand in one place in a line. A digit can be used again: the code 55 is fine. We say repeats are allowed.

Two dials: 100 codes

Use the multiplication rule. The first dial can show any of 10 digits. Whatever it shows, the second dial can also show any of 10 digits, because repeats are allowed, so no digit gets used up. Every branch splits into 10:

10 × 10 = 100 codes.

Here they all are, in a box: a row for each first digit and a column for each second digit.

012345678901234567893700010203040506070809 firstdigitsecond digit10 rows of 10: 100 codes

The box has 10 rows of 10, so 100 squares, and every code has its own square. The code 37 is in row 3, column 7.

There is another way to see it, and it is a lovely check. The codes 00, 01, 02, ..., 99 are just the numbers from 0 to 99, written with two digits each (a 0 in front of the small ones). How many numbers are there from 0 to 99? From 1 to 99 there are 99, and with 0 that makes 100. ✓ Two completely different ways, the same answer.

So Max's sister needs at most 100 tries. At 2 seconds each, that is 200 seconds: 3 minutes and 20 seconds.

Three dials: 1000 codes

With 3 dials, there is one more step, and again every branch splits into 10:

10 × 10 × 10 = 1000 codes, from 000 to 999.

At 2 seconds a try, that is 2000 seconds, which is more than 33 minutes. One extra dial did not add a little bit of time: it made the job ten times as long. Every new dial multiplies the number of codes by 10:

dials 1 2 3 4 5
codes 10 100 1000 10 000 100 000

A 4-dial bike lock has 10 000 codes: at 2 seconds a try, that is over 5 and a half hours. This is why longer codes and passwords are much safer: each extra symbol multiplies the work for anyone trying to guess.

Codes with letters

Now let's make three-letter "words" from the letters A, B and C. They don't have to be real words, and letters may repeat, so AAA and ABA are allowed.

  • First letter: 3 choices.
  • Second letter: 3 choices (repeats are allowed, so nothing is used up).
  • Third letter: 3 choices.

3 × 3 × 3 = 27 words.

Let's check with a tidy list. Fix the first letter A. Then the last two letters are a two-letter word from A, B, C, and there are 3 × 3 = 9 of those:

AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC.

That is 9 words starting with A. There are also 9 starting with B and 9 starting with C. 9 + 9 + 9 = 27. ✓

When repeats are not allowed

What if each letter can be used only once? Then a letter gets used up at every step:

  • First letter: 3 choices.
  • Second letter: only the 2 letters not used yet.
  • Third letter: only the 1 letter left.

3 × 2 × 1 = 6 words: ABC, ACB, BAC, BCA, CAB, CBA. These are the line-ups of three friends again, with letters instead of names!

So the same three letters can make 27 words with repeats, or 6 words without. Before counting a code, always ask: can a symbol be used again?

  • Repeats allowed: the number of choices stays the same at every step.
  • No repeats: the number of choices goes down by one at every step.

Worked examples

1. A small lock. A lock has 2 dials, each showing 1, 2, 3 or 4. How many codes?

4 × 4 = 16. Tidy list by first digit: 11, 12, 13, 14; 21, 22, 23, 24; 31, ...; 41, ..., 44. Four rows of 4.

2. Two different digits. How many two-dial codes (digits 0 to 9) use two different digits?

First digit: 10 choices. Second: anything except the first, so 9. 10 × 9 = 90.

Check another way: of all 100 codes, the ones with the same digit twice are 00, 11, 22, ..., 99. That is 10 of them. 100 − 10 = 90. ✓ (Those 10 codes are the slanting line of squares from the top-left corner of the box to the bottom-right corner.)

3. Letters A to E. Two-letter words from A, B, C, D, E.

  • With repeats: 5 × 5 = 25.
  • Without repeats: 5 × 4 = 20.
  • The 5 "missing" words are AA, BB, CC, DD, EE. 25 − 5 = 20. ✓

4. Starting with B. How many of the 27 three-letter words from A, B, C start with B? The first letter is fixed (1 choice), the other two have 3 choices each: 1 × 3 × 3 = 9.

Try it

  1. A lock has 2 dials, each showing 1, 2 or 3. List all the codes. How many are there?
  2. A lock has 3 dials, each showing 0 or 1. How many codes? List them. (Have you seen this list before?)
  3. How many two-letter "words" can you make from the 26 letters of the alphabet, repeats allowed?
  4. How many three-dial codes (digits 0 to 9) have three different digits?
  5. A secret knock is a list of 4 knocks, each loud or soft. How many secret knocks are there?
  6. A lock has 3 dials showing 0 to 9. How many codes start with 7?
  7. How many of the 100 two-dial codes have at least one 5 in them? (Hint: count the codes with no 5 first.)
Answers
  1. 11, 12, 13, 21, 22, 23, 31, 32, 33. 3 × 3 = 9 codes.
  2. 2 × 2 × 2 = 8: 000, 001, 010, 011, 100, 101, 110, 111. It is the same as the 8 towers of orange and blue blocks in level 1, with 0 for orange and 1 for blue, and the 8 results of tossing a coin three times.
  3. 26 × 26. Work it out: 26 × 20 = 520 and 26 × 6 = 156, so 520 + 156 = 676.
  4. 10 × 9 × 8. 10 × 9 = 90 and 90 × 8 = 720.
  5. 2 × 2 × 2 × 2 = 16.
  6. The first dial is 7 (1 way), the other two have 10 each: 1 × 10 × 10 = 100. (They are 700 to 799.)
  7. Codes with no 5: each dial has 9 choices (any digit but 5), so 9 × 9 = 81. The rest have at least one 5: 100 − 81 = 19. Check by listing: 05, 15, 25, 35, 45, 55, 65, 75, 85, 95 (10 codes with 5 second) and 50, 51, 52, 53, 54, 56, 57, 58, 59 (9 more with 5 first, not counting 55 again): 10 + 9 = 19. ✓

Common mistake

Using up digits when repeats are allowed. On a lock, a dial does not care what the other dials show, so every dial has all 10 digits. Writing 10 × 9 for a lock forgets codes like 33 and 77.

Adding the dials. "Two dials of 10, so 20 codes" adds instead of multiplying. The two dials work together, one digit and another digit, so multiply.

Where it leads