The Lumenary · Grades 6–8

Check digits and error detection

Name: ______________________

Date: ______________________

You will learn to

Compute and verify ISBN-10 and ISBN-13 check digits
Prove that ISBN-10 detects every single-digit error and every swap of two neighbouring digits
Explain why ISBN-13 detects every single-digit error but misses swaps of neighbouring digits that differ by 5
Add a parity bit to binary data and prove that it detects any odd number of flipped bits and no even number
Explain why a single check digit can detect an error but cannot correct it

1.
The first nine digits of an ISBN-10 are $9\text{-}97150\text{-}213$ . What is the check digit? (If it is X, answer $10$ .)
2.
Exactly one of these is a valid ISBN-13. Which one?
- A.978-9966-25-118-3
- B.978-9966-25-181-3
- C.978-9966-52-118-3
- D.978-9966-25-118-8
3.
Find the check digit $d_{13}$ of the ISBN-13 that begins $978\text{-}9966\text{-}25\text{-}118$ .
4.
What parity bit should be added to the message $1101011$ so that the total number of 1s is even? (Answer $0$ or $1$ .)
5.
Which swap of two neighbouring digits can go undetected in an ISBN-13?
- A. $\ldots 16 \ldots \to \ldots 61 \ldots$
- B. $\ldots 23 \ldots \to \ldots 32 \ldots$
- C. $\ldots 48 \ldots \to \ldots 84 \ldots$
- D. $\ldots 90 \ldots \to \ldots 09 \ldots$
6.
In the proof that ISBN-10 catches every swap of neighbours, $x$ is in position $k$ and $y$ in position $k + 1$ . By how much does the swap change the check sum?
- A.By $y - x$ (up to sign)
- B.By $k(y - x)$
- C.By $2(y - x)$
- D.By $0$ — the sum does not change
7.
One digit of a valid ISBN-10 is smudged: $3\text{-}16\text{-}14\,?\,410\text{-}X$ . The smudged digit is in position $6$ . Find it. (Hint: you will need a partner modulo $11$ .)
8.
A received ISBN-10 fails the check. Which statement is true?
- A.At least one digit is wrong, but in general we cannot tell which one.
- B.The computer can find and fix the wrong digit using the check digit.
- C.The check digit itself must be the wrong digit.
- D.Exactly one digit is wrong.
9.
In Lean, a code number is a list of digits and pre ++ x :: post is the list pre, then the digit x, then the list post. Which statement says that ISBN-10 detects every single-digit error?
- A.ValidISBN10 (pre ++ x :: post) → ValidISBN10 (pre ++ y :: post) → x = y (for digits x, y ≤ 10)
- B.ValidISBN10 (pre ++ x :: post) → ¬ ValidISBN10 (pre ++ y :: post)
- C.ValidISBN10 (pre ++ x :: y :: post) → ValidISBN10 (pre ++ y :: x :: post) → x = y
- D.x ≠ y → ValidISBN10 (pre ++ x :: post)
10.
Write luhn_valid(number), where number is a string of digits, returning True if it passes the Luhn test: from the right, keep the 1st, 3rd, 5th, … digits as they are; double the 2nd, 4th, … digits, subtracting $9$ when the double is more than $9$ ; the total must be a multiple of $10$ . Then check the blind spot: 1099 and 1909 differ by a $09 \leftrightarrow 90$ swap.
Computational — Practice

Answer key — Check digits and error detection

1.
$1 \cdot 9 + 2 \cdot 9 + 3 \cdot 7 + 4 \cdot 1 + 5 \cdot 5 + 6 \cdot 0 + 7 \cdot 2 + 8 \cdot 1 + 9 \cdot 3 = 126$ , and $126 = 11 \cdot 11 + 5$ . The check digit is $5$ : the ISBN is 9-97150-213-5. Check: $126 + 10 \cdot 5 = 176 = 16 \cdot 11$ . ✓
2.
Only 978-9966-25-118-3 is valid: its weighted sum is $140$ . The others are this number with one error each — two neighbour swaps (of digits differing by $7$ and by $3$ ) and a changed check digit — and Theorems 3 and 4 say all three errors are caught.
3.
$9 + 3 \cdot 7 + 8 + 3 \cdot 9 + 9 + 3 \cdot 6 + 6 + 3 \cdot 2 + 5 + 3 \cdot 1 + 1 + 3 \cdot 8 = 137$ . The last digit has weight $1$ , so we need $137 + d_{13} \equiv 0 \pmod{10}$ : $d_{13} = 3$ .
4.
$1101011$ has five 1s, an odd number, so the parity bit is $1$ and the word sent is $11010111$ , with six 1s.
5.
Swapping neighbours $a, b$ changes the sum by $\pm 2(a - b)$ , which is a multiple of $10$ exactly when $a - b$ is a multiple of $5$ . Among the options only $1$ and $6$ differ by $5$ .
6.
Before the swap the two positions contribute $kx + (k+1)y$ ; after it, $ky + (k+1)x$ . The difference is $y - x$ . Since $x \ne y$ are digits from $0$ to $10$ , $1 \le |y - x| \le 10$ , which is not a multiple of $11$ , so the swapped number fails the test.
7.
Known digits: $1 \cdot 3 + 2 \cdot 1 + 3 \cdot 6 + 4 \cdot 1 + 5 \cdot 4 + 7 \cdot 4 + 8 \cdot 1 + 9 \cdot 0 + 10 \cdot 10 = 183 \equiv 7 \pmod{11}$ . We need $7 + 6 \cdot ? \equiv 0$ , so $6 \cdot ? \equiv 4 \pmod{11}$ . Multiply by $2$ , the partner of $6$ : $? \equiv 8 \pmod{11}$ . The digit is $8$ , and the ISBN is 3-16-148410-X. Theorem 1 guarantees the answer is unique: two different digits in that position cannot both give a valid ISBN.
8.
Only (a) is true. Failing the test proves that the number is not a valid ISBN, so at least one digit is wrong. But a damaged number is typically at distance 1 from several valid ISBNs (for 3-26-148410-X, both 3-16-148410-X and 1-26-148410-X), so a single check digit cannot correct errors.
9.
The precise form is (a): if both pre ++ x :: post and pre ++ y :: post are valid ISBN-10s, then x = y. Contrapositively, if x ≠ y (a real error), at least one of them fails the test. Option (b) is false when x = y, (c) is the swap theorem, and (d) is nonsense.
10.
```
def luhn_valid(number):
    total = 0
    for i, ch in enumerate(reversed(number)):
        d = int(ch)
        if i % 2 == 1:
            d = 2 * d
            if d > 9:
                d -= 9
        total += d
    return total % 10 == 0
```
Subtracting $9$ is the same as adding the two digits of a number from $10$ to $18$ (for example $16 \to 1 + 6 = 7 = 16 - 9$ ). Both 1099 and 1909 pass, because $0 + D(9) = 9 = 9 + D(0)$ , where $D$ is the doubling step: this is the one neighbour swap Luhn cannot see.