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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

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[Bearbeiten | Quelltext bearbeiten]

Zwei EAN-Codes unterscheiden sich an der Stelle mit Index j[Bearbeiten | Quelltext bearbeiten]

1. EAN-Code:

2. EAN-Code:

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 .

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))

daraus folgt:

(weil und in dieser Menge gibt es nicht zwei Zahlen die beide kongruent 0 modulo 10 sind)

Zwei benachbarte Stellen x und y werden vertauscht[Bearbeiten | Quelltext bearbeiten]

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

Ergänzung (27/10/13):

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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 vorliegt. Das heißt, wenn die Summe nicht kongruent zu 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 , die gleich sind, und zusätzlich zwei Ziffern, die unterschiedlich sind. Diese Ziffern werden mit oder multipliziert. Diesen Faktor bezeichnen wir allgemein als ():

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

Diese Kongruenz müssen wir einfach lösen:

Nachdem sein muss, da , dürfen wir durch teilen.

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

Vertauschen von benachbarten Ziffern wenn Differenz ungleich 5[Bearbeiten | Quelltext bearbeiten]

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 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 auf ändern bzw. umgekehrt.

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

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

Nachdem ist, müssen wir den Modul auch anpassen:

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

Link zu anderen Lösungen des gleichen Beispiels[Bearbeiten | Quelltext bearbeiten]

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