Ziffer wechseln -> ISBN falsch < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine ISBN-10 besteht aus [mm] x_{1}x_{2}...x_{9}x_{10} [/mm] mit xi [mm] \in [/mm] {0,1,...,9} für i=0,...,9 und einer Prüfziffer [mm] x_{10}.
[/mm]
Eine Nummer ist gültig [mm] \gdw \summe_{i=1}^{10}(11-i)*x_{i} \equiv [/mm] 0 mod 11
Weisen Sie nach, dass ein Fehler in einer einzelnen Ziffer in einer gültigen ISBN zu einer ungültigen ISBN führt. Hinweis: Betrachten Sie die Differenz der Prüfsummen. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
Ich habe einen Lösungsansatz (es fehlt nicht mehr viel denke ich), jedoch komme ich nicht mehr weiter. Kann vielleicht jemand weiterhelfen?
Sei A: 3423620153 eine gültige ISBN (Sie ist gültig, habe sie aus einer voherigen Aufgabe). Die Prüfsumme lautet bereits ausgerechnet: [mm] \summe_{i=1}^{10}(11-i)*x_{i} [/mm] = 165
Nehmen wir an, wir ändern die 2. Ziffer von 4 zu 3. Somit lautet die gestörte ISBN B: 3323620153 .
Die Prüfsumme der gestörten ISBN B lautet: [mm] \summe_{i=1}^{10}(11-i)*x_{i} [/mm] = 156
Die Differenz der beiden Prüfsummen lautet: 165-156=9*(4-3)=9
Allgemein aufgeschrieben:
Sei A die Prüfsumme der gültigen ISBN und B die Prüfsumme der gestörten ISBN.
i sei die Stelle, an der die fehlerhafte Ziffer auftritt.
a sei die gültige Ziffer und b sei die ungültige Ziffer.
Dann lautet die Differenz zweier Prüfsummen allgemein: A-B=(11-i)*(a-b)
Der Faktor (11-i) kann nur zwischen 1 und 10 liegen.
Der Faktor (a-b) kann nur zwischen -9 und 9 liegen (0 jedoch ausgenommen, da sonst keine fehlerhafte bzw. andere ISBN Nummer vorliegen würde).
Und jetzt müsste ich ja noch zeigen, dass A-B=(11-i)*(a-b) nicht restlos durch 11 teilbar ist. Und genau hier komme ich nicht weiter. Ich weiß nicht, wie ich das zeigen könnte... Ich weiß zwar, dass die beiden Faktoren (11-i) und (a-b) jeweils nicht restlos durch 11 teilbar sind, jedoch sagt das ja nicht aus, dass das Produkt der beiden Faktoren ebenfalls nicht durch 11 teilbar ist...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:40 Di 22.01.2013 | | Autor: | Teufel |
Hi!
Doch, in diesem Fall bist du fertig. Ich weiß nicht, in wie weit du mit Körpern oder Integritätsringen vertraut bist, aber wenn du modulo einer Primzahl (hier: 11) rechnest, dann ist ein Produkt genau dann 0, wenn einer der Faktoren 0 ist. Hier sind beide Faktoren ungleich 0 (da 11 sie nicht teilt), also auch das Produkt.
|
|
|
| |
|
> Hi!
>
> Hier sind beide Faktoren ungleich 0 (da 11
> sie nicht teilt), also auch das Produkt.
Hallo,
Woher weißt du, dass das Produkt
(11-i)*(a-b)
nicht restlos durch 11 teilbar ist? Das die beiden Faktoren jeweils nicht durch 11 teilbar sind, habe ich ja bereits gezeigt.
Die Prüfsumme der ungültigen ISBN (ungültig im Sinne davon, dass nur 1 Ziffer falsch ist) weicht um A-B bzw (11-i)*(a-b) von der gültigen ISBN nach unten ab (Also A-B bzw (11-i)*(a-b) wird von der Prüfsumme der gültigen ISBN Abgezogen, was dann die Prüfsumme der ungültigen ISBN gibt)
Wir wissen, dass die Prüfsumme der gültigen ISBN (also A) restlos durch 11 teilbar ist.
Was wir aber doch noch nicht wissen, bzw. noch nicht gezeigt haben, ist, dass die Prüfsumme der ungültigen ISBN nicht restlos durch 11 teilbar ist.
Es muss also gezeigt werden, dass folgene Kongruenz NICHT gilt:
A-(11-i)*(a-b) [mm] \equiv [/mm] 0 mod 11
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:37 Di 22.01.2013 | | Autor: | Teufel |
Ja, ziehen wir das nochmal von vorne auf:
Du hast eine ISBN A. Sei B die ISBN, die an einer Stelle von A abweicht. Wenn B auch korrekt wäre, so müsste A-B=0 sein, wenn wenn A korrekt ist, dann ist die Summe da ja 0 und wenn B auch korrekt ist, ist die Summe eben auch 0. Also ist die Differenz der Summen auch 0.
Nun guckst du dir aber die Differenz der Summen an und stellst fest, dass sie nicht 0 ist. Daher muss A oder B fehlerhaft gewesen sein. A kann es nach Voraussetzung nicht sein, also ist B fehlerhaft. So weit nochmal zum groben Aufbau.
Nun ist noch die Frage, warum (11-i)*(a-b) nicht 0 mod 11 ist. Und da muss ich dich nochmal fragen, ob du weißt, was ein Körper (oder Integritätsring) ist und ob du weißt, dass [mm] \IZ_11 [/mm] ein Körper ist. Wenn ja, dann gilt wie in jedem Körper (z.B. auch [mm] \IR), [/mm] dass ein Produkt genau dann 0 ist, wenn einer der Faktoren 0 ist. Hier sind aber beide Faktoren ungleich 0, also auch das Produkt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:54 Di 22.01.2013 | | Autor: | KlickKlack |
> Ja, ziehen wir das nochmal von vorne auf:
>
> Du hast eine ISBN A. Sei B die ISBN, die an einer Stelle
> von A abweicht. Wenn B auch korrekt wäre, so müsste A-B=0
> sein, wenn wenn A korrekt ist, dann ist die Summe da ja 0
> und wenn B auch korrekt ist, ist die Summe eben auch 0.
> Also ist die Differenz der Summen auch 0.
>
> Nun guckst du dir aber die Differenz der Summen an und
> stellst fest, dass sie nicht 0 ist. Daher muss A oder B
> fehlerhaft gewesen sein. A kann es nach Voraussetzung nicht
> sein, also ist B fehlerhaft. So weit nochmal zum groben
> Aufbau.
>
Ahh ok jetzt habe ich den Nachweis verstanden.
> Nun ist noch die Frage, warum (11-i)*(a-b) nicht 0 mod 11
> ist. Und da muss ich dich nochmal fragen, ob du weißt, was
> ein Körper (oder Integritätsring) ist und ob du weißt,
> dass [mm]\IZ_11[/mm] ein Körper ist. Wenn ja, dann gilt wie in
> jedem Körper (z.B. auch [mm]\IR),[/mm] dass ein Produkt genau dann
> 0 ist, wenn einer der Faktoren 0 ist. Hier sind aber beide
> Faktoren ungleich 0, also auch das Produkt.
Was ein Körper oder Integritätsring ist weiß ich nicht, aber mit dem obigem Beweis ist ja schon alles geklärt.
Danke dir ;)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:07 Di 22.01.2013 | | Autor: | Teufel |
Ok, kein Problem. :)
Naja, ein Körper ist einfach eine Menge mit + und *, die einige schöne Eigenschaften hat, mit denen man "normal wie in [mm] \IR" [/mm] rechnen kann. Und dann folgen auch solche Sachen wie, dass das Produkt von 2 Zahlen, die ungleich 0 sind, nicht 0 sein kann (auch wie in [mm] \IR). [/mm] Du kannst aber auch eine 10x10-Tabelle machen und alles mit allem Multiplizieren. Also alle Zahlen paarweise von 1 bis 10. Dann siehst du, dass nirgends irgendwo 0 rauskommt. So kannst du das auch machen. Ist vielleicht etwas Arbeit, aber es geht noch.
|
|
|
|
