O Universal Product Code (UPC) é o código utilizado nos códigos de barra e consiste em um vetor (x1, x2, ldots, x12) in(Z / 10 Z)^10 tal que
3 x1+x2+3 x3+x4+3 x5+x6+3 x7+x8+3 x9+x10+3 x11+x12=0 em Z / 10 Z
Mostre que um erro causado pela troca entre o segundo e terceiro dígitos no UPC (0,7,4,9,2,7,0,2,0,9,4,6) é detectado. Por outro lado, mostre que existe uma troca entre dois dígitos adjacentes neste UPC que não é detectado.

Passo 1

O enunciado define o UPC como o vetor (x1,x2,dots,x12)in(Z/10Z)^12 que satisfaz
3x1+x2+3x3+x4+3x5+x6+3x7+x8+3x9+x10+3x11+x12equiv0pmod10
Queremos mostrar que, no código
(0,7,4,9,2,7,0,2,0,9,4,6),
a troca entre os dígitos segundo e terceiro é detectada, mas existe outra troca de dígitos adjacentes que não é detectada.

Passo 2

Denotemos por é ímpar},\ 1,&se é par. \end{cases}]
Se trocamos os dígitos e , o novo somatório difere do original por
Como , a troca é indetectável se, e somente se,
Isto significa que apenas trocas de dígitos adjacentes cuja diferença seja deixam .

Passo 3

No nosso UPC, x2=7 e x3=4. Aqui c2=1 e c3=3, logo
De<a2,3=(c2-c3)(x3-x2) =(1-3)(4-7)=-2cdot(-3)=6notequiv0pmod10
Portanto a troca entre os dígitos segundo e terceiro é de fato detectada.

Passo 4

Buscamos agora um par adjacente (xi,xi+1) tal que xi+1-xiequiv5pmod10. Observando
(dots,4,9,dots)
nos dígitos terceiro e quarto, vemos que x3=4, x4=9, portanto
x4-x3=9-4=5
Como c3-c4=3-1=2, a mudança no somatório é
De<a3,4=2,(x4-x3)=2cdot5=10equiv0pmod10,
ou seja, essa troca não é detectada.

Resposta

A troca entre o segundo e o terceiro dígitos (7rightarrow4) é detectada, pois altera o somatório em 6notequiv0.
Já a troca entre o terceiro e o quarto dígitos (4rightarrow9) não é detectada, pois altera o somatório em 0.

Exercícios relacionados