O International Standard Book Number (ISBN-10) é um identificador único para livros e consiste em um vetor (d1, d2, ldots, d10) in F11^10 tal que
1 cdot d1+2 cdot d2+3 cdot d3+cdots+9 cdot d9+10 cdot d10=0 in F11
Mostre que, em geral, todo erro dado pela troca de dois dígitos adjacentes em qualquer ISBN-10 será detectado.

Passo 1

O ISBN- 10 é um vetor l(d1,d2,dots,d10r) em F11^10 que satisfaz a condição de paridade
overline1,d1+overline2,d2+cdots+overline9,d9+10,d10=overline0 (em F11)
Queremos mostrar que, se trocarmos dois dígitos adjacentes dr e dr+1 (com 1<= r<=9), o novo vetor não satisfaz mais essa equação, a menos que dr=dr+1 (caso trivial em que nada muda).

Passo 2

Seja
S ;=;overline1,d1+overline2,d2+cdots+overline r,dr+r+1,dr+1+cdots+10,d10
Pela definição de ISBN- 10, temos
S=overline0(em F11)

Passo 3

Agora trocamos apenas os dígitos nas posições r e r+1. Chamemos o novo vetor de dots,dr+1',dr',dots, onde
dr'=dr+1, dr+1'=dr,
e todos os outros di'=di para ineq r,r+1.

Passo 4

O novo somatório de verificação é
S' ;=; overline1,d1+cdots+overline r,dr' + r+1,dr+1'+cdots+10,d10
Substituindo dr'=dr+1 e dr+1'=dr, temos
S' ;=; l(S - overline r,dr - r+1,dr+1r) +overline r,dr+1 + r+1,dr

Passo 5

Calculando a diferença S' - S em F11:
S' - S =l(-overline r,dr-r+1,dr+1+overline r,dr+1+r+1,drr) =overline r,(dr+1-dr)+r+1,(dr-dr+1)
Fatorando,
S' - S =(r+1-overline r),(dr-dr+1) =overline1,(dr-dr+1) =dr-dr+1(bmod,11)
Como dr,dr+1inF11, essa diferença só é overline0 se dr=dr+1. Se os dois dígitos fossem distintos, S'neq S=overline0, logo o erro é detectado.

Resposta

Qualquer troca de dois dígitos adjacentes distintos em um ISBN- 10 altera o somatório de verificação por dr-dr+1neqoverline0, portanto o erro é sempre detectado.

Exercícios relacionados