Check Code Sensitivity
You are given the method used for assigning certain check codes and
you have to find out if an error in a single digit can be
identified.
Age
14 to 16
Challenge level
Problem
Image
Check codes are designed to pick up common errors such as transposing two digits or miscopying a single digit. A person types the code number into a machine which decides whether it is a valid code or not. If someone types in a US Postal Service Money Order number and makes a single error, just one mistake in one digit, will the machine pick up every error of this type? Will a machine always pick up an error in a single digit for an airline ticket number?
US Postal Service Money Order: This is an eleven digit number using digits 1,2,...9 where the sum of the first ten digits is congruent to the eleventh digit modulo 9. That is $a_1a_2\cdots a_{11}$ where $a_1+ \cdots +a_{10} \equiv a_{11}$ mod $9$.
Airline tickets: This number can be any length. It uses the digits 0 to 9 and the last digit is a check digit. The number formed by omitting the check digit must be congruent to the check digit modulo 7.
That is $a_1\cdots a_na_{n+1}$ where $a_1a_2\cdots a_n \equiv a_{n+1}$ mod 7.
Getting Started
Remember that to show that a result is not true, or that a method
fails, you only have to find one counterexample, that is one case
where it fails. To prove that a result is always true you need a
completely general argument. No matter how many cases you give
where the result is true that does not prove that it is
always true.
Student Solutions
Well done Andrei Lazanu, age 14, School No. 205, Bucharest, Romania and Robert Goudie, age 17, Madras College, Fife, Scotland for these solutions.
I worked the problem considering two distinct possible errors: miscopying a single digit, and transposing two adjacent digits.
1. Miscopying a single digit
For a US Postal Service Money Order the condition for a valid number is:
$$a_1 + a_2 + . . . + a_{10} = a_{11} \ {\rm mod\ 9}.$$
Let's say the operator changes $a_n$ to $a_{n'}$ where these are any positive integers between 0 and 9. The condition the machine doesn't find the error is that the new number is also a valid money order number. So $a_n - a_{n'}\equiv 0 \hbox{ mod 9}$. This can happen only when the operator changes 0 with 9 or 9 with 0 for any digit including the first one (which could be 0). In all other cases the error will be found. Now I'll examine separately the case of the check digit. The same rule holds for it too, because I must look at the congruence mod 9, i.e. if there is an error in the check digit it is not detected by the machine if 0 is replaced by 9 or 9 by 0.
For an Airline Ticket, in order the machine does not find the error, the difference between the numbers obtained omitting the check digit, in the correct and in the miscopied form, must be a multiple of 7. But, if the difference of two numbers differing only in one digit is a multiple of 7, the numbers must differ by 7, 70, 700, 7000 ... and this means the difference of the two digits must be 7. The machine will not find the error if the operator changes 0 with 7, 1 with 8 or 2 with 9, or 7 with 0, 8 with 1, 9 with 2. The same is valid for the check digit too.
2. Transposing two adjacent digits
For the US Postal Service Money Order numbers the machine won't find the error except transposing the check digit. The machine doesn't find it because the addition is commutative.
For Airline Ticket numbers I work on the number omitting the check digit. The miscopied number goes undetected when the remainders after division of the numbers by 7 are the same that is when the difference of the two numbers is a multiple of 7. Let the two adjacent digits be a and b so the difference between the two numbers is a power of 10 times 9(a - b). If this is a multiple of 7 then (a - b) is a multiple of 7. The error will be undetected if the adjacent digits transposed are 0 and 7 or 1 and 8 or 2 and 9.