TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 81

Im europäischen Artikelnummersystem EAN werden Zahlen mit 13 Dezimalziffern der Form $a_{1}a_{2}...a_{12}p$ verwendet. Dabei wird die letzte der 13 Ziffern, das ist die Prüfziffer p im EAN-Code so bestimmt, dass

$a_{1}+3a_{2}+a_{3}+3a_{4}+...+a_{11}+3a_{12}+p\equiv 0{\text{ mod 10 }}$

gilt. Man zeige, dass beim EAN-Code ein Fehler in einer einzelnen Ziffer stets erkannt wird, während eine Vertauschung von zwei benachbarten Ziffern genau dann nicht erkannt wird, wenn die beiden Ziffern gleich sind oder sich um 5 unterscheiden.

Zwei EAN-Codes unterscheiden sich an der Stelle mit Index j

1. EAN-Code: $S+kx_{j}\equiv 0{\text{ mod 10 }}$

2. EAN-Code: $S+ky_{j}\equiv 0{\text{ mod 10 }}$

S ... Summe der übrigen Stellen (ist bei beiden Codes gleich)

Erläuterung: Jede Stelle wird entweder mit 1 oder 3 multipliziert, um den Beweis nicht zwei mal zu führen, arbeiten wir mit Konstante $k\in \{1,3\}$.

$S+kx_{j}\equiv S+ky_{j}{\text{ mod 10 }}$

$S+kx_{j}-S-ky_{j}\equiv 0{\text{ mod 10 }}$

$kx_{j}-ky_{j}\equiv 0{\text{ mod 10 }}$

$k(x_{j}-y_{j})\equiv 0{\text{ mod 10 }}$

Division durch k ist erlaubt, weil k und 10 teilerfremd sind.

Anmerkung: Zwei Zahlen a und b sind dann teilerfremd, wenn ihr ggT(a, b) = 1 ist.

Beispiele:

• Die Zahlen 12 und 77 sind teilerfremd, denn ihre Primfaktorzerlegungen 12 = 2 · 2 · 3 und 77 = 7 · 11 enthalten keine gemeinsamen Faktoren.
• Die Zahlen 15 und 25 sind nicht teilerfremd, denn in ihren Primfaktorzerlegungen 15 = 3 · 5 und 25 = 5 · 5 kommt 5 als gemeinsamer Faktor vor, der zugleich ggT(15; 25) ist.

Siehe auch http://de.wikipedia.org/wiki/Teilerfremd ( --Mnemetz 14:51, 15. Nov 2005 (CET))

$x_{j}-y_{j}\equiv 0{\text{ mod 10 }}$

$x_{j}\equiv y_{j}{\text{ mod 10 }}$

daraus folgt: $x_{j}=y_{j}$

(weil $x,y\in \{0,1,...,9\}$ und in dieser Menge gibt es nicht zwei Zahlen die beide kongruent 0 modulo 10 sind)

Zwei benachbarte Stellen x und y werden vertauscht

$S+x+3y\equiv S+3x+y{\text{ mod 10 }}$

$S+x+3y-S-3x-y\equiv 0{\text{ mod 10 }}$

$2y-2x\equiv 0{\text{ mod 10 }}$

$2y\equiv 2x{\text{ mod 10 }}$

$y\equiv x{\text{ mod 5 }}$

daraus folgt: entweder $x=y$ oder x und y unterscheiden sich um 5.

Diskussion über diese Lösung bitte unter f.thread:36355 führen.

Ergänzung: --Mnemetz 14:42, 15. Nov 2005 (CET)

Die Ziffern der Europäischen Artikel-Nummerierung sind auf jedem Produkt unter dem Strichcode zu finden. Dabei bezeichnen die ersten beiden Ziffern das Herkunftsland des Produktes. Die nächsten fünf Ziffern bezeichnen die Firma und die darauffolgenden fünf Ziffern die firmeninterne Produktbezeichnung. Die letzte Ziffer ist das Kontrollsymbol. Als Gewichte werden abwechselnd 1 und 3 gewählt:

  EAN       5  4   4  9  0  0   0  0  5  0  5  1       9
  Gewicht   1  3   1  3  1  3	1  3  1  3  1  3	
  Produkt   5  12  4  27 0  0	0  0  5	 0  5  3      Summe: 61

Mit diesem Verfahren werden nun alle Einzelfehler und fast alle Vertauschungsfehler erkannt. Unerkannt bleibt beispielsweise die Vertauschung von 8 und 3. Denn 1*8 + 3*3 = 17 und 1*3 + 3*8 = 27. Bei dieser Art von Codes gibt es keine Möglichkeit, sowohl Einzelfehler als auch Vertauschungsfehler mit Sicherheit zu erkennen.

Siehe auch: http://studhome.rrze.uni-erlangen.de/~snvivola/mathematisches.html (dead)

Link zu anderen Lösungen des gleichen Beispiels

TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 64