Telephone Number Checksum Problem

Question

I am having difficulty solving this problem. Could someone please help me? Thanks

"The telephone numbers in town run from 00000 to 99999; a common error in dialling on a standard keypad is to punch in a digit horizontally adjacent to the intended one. So on a standard dialling keypad, 4 could erroneously be entered as 5 (but not as 1, 2, 7, or 8). No other kinds of errors are made.

It has been decided that a sixth digit will be added to each phone number $abcde$. There are three different proposals for the choice of $X$:

Code 1: $a + b + c + d +e + X$ $\equiv 0\pmod{2}$

Code 2: $6a + 5b + 4c + 3d + 2e + X$ $\equiv 0\pmod{6}$

Code 3: $6a + 5b + 4c + 3d + 2e + X$ $\equiv 0\pmod{10}$

Out of the three codes given, choose one that can detect a horizontal error and one that cannot detect a horizontal error. "

Answer 1

You want to know if it can handle finding one horizontal error.

What does a horizontal error entail? Any given number $x$ can only be replaced by either $x-1$ or $x+1$; sometimes, only one or the other (for instance, 4 can only be replaced by 5, not by 3).

In Code 1, $X$ is just the "parity" of the numbers - all it tells you is whether their sum is even or odd. Since a shift in any one spot can only by a shift by 1, it will change the parity - so that a horizontal error will yield $$ a+b+c+d+e+X\pm 1\equiv (a+b+c+d+e+X)+1\equiv1\pmod{2}. $$ So, single horizontal shift errors are always detected.

In Code 2, the value of $a$ has no impact on the checksum - for any valid $a$, $6a\equiv0\mod 6$. So, for instance, if $a=4$, and you accidentally press $5$ instead, then $$ 6\cdot5+5b+4c+3d+2e+X\equiv 6\cdot4+5b+4c+3d+2e+X\equiv0\pmod{6}, $$ and the error is not detected. So, we cannot guarantee that code 2 detects a horizontal error.

In code 3, the situation is better: an error in $a$ will lead to the checksum being congruent to $6$ or $-6\equiv4\pmod{10}$; an error in $b$ will lead to the checksum being congruent to $5$; etc. It will always detect the error. Unfortunately, it still cannot tell us where the error occurs; a shift up in $a$ or a shift down in $c$ both make the checksum congruent to $6\pmod{10}$.

So, Codes 1 and 3 will always detect a horizontal error; code 2 will not. And none will detect the position of the error.

Answer 2

Code 1 can detect horizontal error. Let $c$ be the correct misdialed digit (order doesn't matter because they're added) and let $c'$ be the mistaken misdialed digit. For any two horizontally adjacent digits consist of an odd and even number. That is, $c-c'\equiv 1 \pmod 2$. It follows that the sum of the new digits will be $$ a+b+c'+d+e+X\equiv\\ a+b+c+d+e+X+(c'-c)\equiv\\ 0+(c'-c)\equiv\\ 1 \pmod 2 $$ Thus, any wrong number will fail the test.

Code 2 cannot detect horizontal error. Consider, for example, the phone number $123231$. The number $223231$ will pass the test even though a horizontal error was made with the first digit. In general, this code fails to detect errors in the first digit.