Re: ISBN & undecimal counting

msb@xxxxxxx (Mark Brader) writes:

> ObPuzzle: the fact that algorithms such as these are used suggests
> strongly that a check-digit algorithm where
>
> * each digit is replaced with a certain digit, depending on
> its position and original value and nothing else
> * these digits are added mod 10 to produce a checksum
>
> with the properties that
>
> * if any one digit is changed, the checksum changes
> * if any two adjacent digits are transposed, the checksum changes.
>
> is impossible. Can you prove that it's impossible?

Let f_i(x) be the value assigned if x is in position i. A sum is valid
if f_1(x)+f_2(x)+...+f_n(x)=0 mod 10.

The two conditions are now:

f_i(x) is a permutation of 0-9

and

f_i(x)+f_{i+1}(y)=f_i(y)+f_{i+1}(x) mod 10 only when x=y
or equivalently:
f_i(x)-f_{i+1}(x)=f_i(y)-f_{i+1}(y) mod 10 only when x=y

Thus the ten values f_i(0)-f_{i+1}(0),...,f_i(9)-f_{i+1}(9) must all be
different mod 10, covering all values from 0 to 9. Their sum is thus 5
modulo 10.

However, [f_i(0)+...+f_i(9)]-[f_{i+1}(0)+...+f_{i+1}(9)] = 0, so the ten
values actually sum to 0 modulo 10.

Note that this proof depends on 0+1+...+9 not being a multiple of 10;
this result does not hold in an odd-numbered base, which makes the ISBN
code possible modulo 11.

--
David Grabiner, grabiner@xxxxxxxxxxxxxxxxxxxx, http://remarque.org/~grabiner
Baseball labor negotiations FAQ: http://remarque.org/~grabiner/laborfaq.html
Shop at the Mobius Strip Mall: Always on the same side of the street!
Klein Glassworks, Torus Coffee and Donuts, Projective Airlines, etc.
.

Relevant Pages

  • Re: ISBN & undecimal counting
    ... > * each digit is replaced with a certain digit, ... > * if any two adjacent digits are transposed, the checksum changes. ... are two permutations whose sum mod 10 is another permutation. ...
    (rec.puzzles)
  • Re: Summation, modulo and decimal
    ... >I'm trying to use the modulo (modulus, mod, %) to do the following: ... >The problem is that modulo is only def. ... It not worked because before it shift the ... >digit to the left the number is added to the previous value, so, I used ...
    (sci.math)
  • Summation, modulo and decimal
    ... The problem is that modulo is only def. ... It not worked because before it shift the ... digit to the left the number is added to the previous value, so, I used ...
    (sci.math)
  • Re: Summation, modulo and decimal
    ... and I told you how to figure out the k-th digit. ... it is a trivial matter to "place" it in the appropriate ... >> since taking it modulo 10 and then modulo 2 will yield the same ... >> digit you need only divide by 10^k. ...
    (sci.math)
Loading