TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 71

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\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.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag

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

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

2. EAN-Code: $S+ky_{j}\equiv 0\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}\mod 10$

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

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

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

Division durch k ist erlaubt, weil k und 10 teilerfremd sind. (Q.: Buch, Mathematik für Informatiker, S. 21 oben)

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\mod 10$

$x_{j}\equiv y_{j}\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\mod 10$

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

$2y-2x\equiv 0\mod 10$

$2y\equiv 2x\mod 10$

$y\equiv x\mod 5$

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

Ergänzung (27/10/13):

$2y\equiv 2x\mod 10$

$x=y+5$

$2y\equiv 2(y+5)\mod 10$

$2y\equiv 10*2y\mod 10$

$2y\equiv 2y\mod 10$

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

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

Edit: --Fabiii 00:04, 07. Nov 2007 (CET)

Die Ziffern der Europäischen Artikel-Nummerierung (GTIN - Global Trade Item Number) sind auf jedem Produkt unter dem Strichcode zu finden. Dabei bezeichnen die ersten zwei oder drei Ziffern das Herkunftsland des Produktes. Die nächsten fünf bis sieben Ziffern bezeichnen die Firma und die darauffolgenden drei bis fünf Ziffern die firmeninterne Artikelnummer. Die letzte Ziffer ist die Prüfziffer. 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

Lösungsvorschlag von Berti

Die obige Lösung ist korrekt, allerdings sind ein paar Erläuterungen vielleicht ganz hilfreich.

Hinweis: Der Lösungsweg ist ähnlich wie beim ISBN-Beispiel aus dem Buch Mathematik für Informatik (Auflage 2014), S. 21f.

Wir müssen zwei Dinge zeigen. Erstens dass ein Fehler in einer einzelnen Ziffer immer erkannt wird und zweitens dass das Vertauschen von zwei benachbarten Ziffern nur erkannt wird, wenn sich diese nicht um 5 unterscheiden.

Fehler in einzelner Ziffer

Um zu zeigen, dass ein Fehler in einer einzelnen Ziffer erkannt wird, müssen wir uns überlegen, wie überhaupt ein Fehler erkannt wird bzw. was ein Fehler überhaupt ist. Ein Fehler liegt vor, wenn $a_{1}+3a_{2}+a_{3}+...+p\not \equiv 0\mod 10$ vorliegt. Das heißt, wenn die Summe nicht kongruent zu $0\mod 10$ ist. In so einem Fall wäre der EAN-Code falsch und der Fehler gefunden.

Anders gesagt prüfen wir, ob zwei EAN-Codes immer noch kongruent bezüglich Modulo 10 sind, wenn der Unterschied nur in einer einzelnen Ziffer vorliegt. Beide EAN-Codes bestehen also aus zwei Summen $s=a_{1}+3a_{2}+a_{3}+...+p$, die gleich sind, und zusätzlich zwei Ziffern, die unterschiedlich sind. Diese Ziffern werden mit $1$ oder $3$ multipliziert. Diesen Faktor bezeichnen wir allgemein als $n$ ($n\in \{1,3\}$):

$s+n\cdot a\equiv s+n\cdot b\mod 10$

Wie gesagt, ist $s$ für beide EAN-Codes (den richtigen und den falschen) gleich, die Abweichung liegt in einer Ziffer $a$ bzw. $b$, die auch immer den gleichen Faktor $n$ hat.

Diese Kongruenz müssen wir einfach lösen:

$n\cdot a\equiv n\cdot b\mod 10$

Nachdem $\operatorname {ggT} (n,10)=1$ sein muss, da $n\in \{1,3\}$, dürfen wir durch $n$ teilen.

$a\equiv b\mod 10$

Durch diese Kongruenz ergibt sich, dass $a$ und $b$ die gleichen Ziffern sein müssen. Eine Abweichung in einer Ziffer wird also gefunden.

Vertauschen von benachbarten Ziffern wenn Differenz ungleich 5

Wir zeigen, dass das Vertauschen von benachbarten Ziffern erkannt wird und kommen im Zuge des Beweises automatisch auf die Einschränkung mit der Differenz dieser Ziffern, die nicht $5$ sein darf.

Wie beim vorherigen Beweis stellen wir wieder die Behauptung auf, dass zwei unterschiedliche EAN-Codes kongruent sind, diese allerdings nur zwei vertauschte Ziffern aufweisen. Vertauschte Ziffern bedeutet, dass sich bei zwei Ziffern die Faktoren von $1$ auf $3$ ändern bzw. umgekehrt.

$s+a+3\cdot b\equiv s+3\cdot a+b\mod 10$

Die Ziffer $a$ hatte vorher den Faktor $1$ und nachher den Faktor $3$, bei der Ziffer $b$ (die Nachbarziffer von $a$) ist es genau umgekehrt.

Löst man diese Kongruenzengleichung nun nach den üblichen Regeln für Gleichungen, kommt man auf diese Form:

$2\cdot b\equiv 2\cdot a\mod 10$

Nachdem $\operatorname {ggT} (2,10)=2$ ist, müssen wir den Modul auch anpassen:

$b\equiv a\mod 5$

Hier sieht man also, dass $a$ und $b$ kongruent sind, also die gleichen Ziffern sind, mit der Einschränkung aber, dass die Differenz nicht $5$ sein darf. Ansonsten wären die zwei Ziffern in der gleichen Restklasse ${\bar {5}}$ und der Fehler würde nicht erkannt werden.

Link zu anderen Lösungen des gleichen Beispiels

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