Transposition Fix
Suppose an operator types a US Bank check code into a machine and transposes two adjacent digits will the machine pick up every error of this type? Does the same apply to ISBN numbers; will a machine detect transposition errors in these numbers?
Age
14 to 16
Challenge level
Image
Suppose an operator types a US Bank check code into a machine and transposes two adjacent digits (i.e. swaps the order of two adjacent digits) for example the operator types $a_3a_2$ instead of $a_2a_3$, will the machine pick up every error of this type? Does the same apply to ISBN numbers; will a machine detect transposition errors in these numbers?
US
Bank check codes are nine digit identification numbers
$a_1a_2\cdots a_{9}$ using the digits 0 to 9 where
$7a_1 + 3a_2 + 9a_3 + 7a_4 + 3a_5 + 9a_6 + 7a_7 + 3a_8 \equiv a_9$
mod 10.
ISBN
Numbers have ten digits $a_1\cdots a_{10}$ using the digits
0 to 9 where
$10a_1+9a_2+8a_3+\cdots +3a_8+2a_9+a_{10} \equiv 0$ mod 11.
Look for a case where it fails and if you can't find one try to
find a general proof.
Suppose an operator types a US Bank Check Code into a machine and transposes two adjacent digits (i.e. swops the order of two adjacent digits) will the machine pick up every error of this type? Does the same apply to ISBN numbers, will a machine detect transposition errors in these numbers?
Congratulations Andrei Lazanu, age 14, School No. 205, Bucharest, Romania and Robert Goudie, age 17, Madras College, Fife, Scotland for your solutions.
For the transposition in an ISBN number to go undetected, the sum from the two digits that swap must remain the same, or change by a multiple of 11, because then the check will give the same remainder when divided by 11, and so will still yield the check number.
Let $x$ and $y$ be any adjacent digits in the ISBN. To check whether the ISBN is valid, the first digit is multiplied by 10 and the next by 9, all the way through to the second last digit which is multiplied by 1. These are then summed.
So if $r$ is the number that $x$ is multiplied by, then $y$ is multiplied by $(r - 1)$. If $x$ and $y$ are transposed, then $y$ will be multiplied by $r$ and $x$ will be multiplied by $(r-1)$.
So for the check sum from the two digits to remain unchanged
$$\eqalign{ rx + (r-1)y &= ry + (r-1)x\cr rx - (r-1)x &= ry - (r-1)y\cr rx - rx + x &= ry - ry + y\cr x &= y}.$$
Therefore, for the error to be undetected these digits must be the same (which, in a way, means the digits have not been transposed).
If the sum of the two digits increases by 11 then
$$\eqalign{ rx + (r-1)y &= ry + (r-1)x + 11\cr rx - (r-1)x &= ry - (r-1)y + 11\cr rx - rx + x &= ry - ry + y + 11\cr x &= y + 11}.$$
This, however, is impossible, since $x$ and $y$ must be between 0 and 9 inclusive. Therefore, it is impossible to transpose two numbers in an ISBN without the check digit spotting it, unless the numbers are the same, in which case the numbers have not really been transposed.
The argument for US Bank numbers is the same, except that the coefficients in the check sum are 7, 3, 9, 7, 3, 9, 7, 3 and the check sum must be equivalent to the ninth digit mod 10. The coefficients here do not decrease by 1, the difference could be 4, 6 or 2, so let the difference in coefficients be $k$. Therefore
$$\eqalign{ rx + (r-k)y &= (r-k)x + ry\cr rx - (r-k)x &= ry - (r-k)y\cr kx&= ky \cr x&=y}.$$
Once again, the digits transposed must be equal for the check sum to remain the same. For the check sum to change by 10 would give $kx=ky \pm 10$. As these are whole numbers the only possibility is for $k=2$ when $x$ and $y$ differ by 5. For example 123856788 is a valid US Bank identification number with check sum 238 congruent to 8 mod 10 but the error in transposing the third and fourth digits to give 128356788 will go undetected because here the check sum is 248.