Page 314 - Discrete Mathematics and Its Applications

4.5 Applications of Congruences 293

15. The first nine digits of the ISBN-10 of the European ver- a) 036000291452
sion of the fifth edition of this book are 0-07-119881. b) 012345678903
What is the check digit for that book? c) 782421843014
16. The ISBN-10 of the sixth edition of Elementary Number d) 726412175425
Theory and Its Applications is 0-321-500Q1-8, where Q 26. Does the check digit of a UPC code detect all single er-
is a digit. Find the value of Q. rors? Prove your answer or find a counterexample.
17. Determine whether the check digit of the ISBN-10 for 27. Determine which transposition errors the check digit of
this textbook (the seventh edition of Discrete Mathemat- a UPC code finds.
ics and its Applications) was computed correctly by the
Some airline tickets have a 15-digit identification number
publisher.
a 1 a 2 ...a 15 where a 15 is a check digit that equals a 1 a 2 ...a 14
The United States Postal Service (USPS) sells money orders mod 7.
identified by an 11-digit number x 1 x 2 ...x 11 . The first ten dig-
28. Find the check digit a 15 that follows each of these initial
its identify the money order; x 11 is a check digit that satisfies
14 digits of an airline ticket identification number.
x 11 = x 1 + x 2 + ··· + x 10 mod 9.
a) 10237424413392
18. Find the check digit for the USPS money orders that have b) 00032781811234
identification number that start with these ten digits.
c) 00611232134231
a) 7555618873 d) 00193222543435
b) 6966133421
c) 8018927435 29. Determine whether each of these 15-digit numbers is a
valid airline ticket identification number.
d) 3289744134
a) 101333341789013
19. Determine whether each of these numbers is a valid USPS
b) 007862342770445
money order identification number.
c) 113273438882531
a) 74051489623
b) 88382013445 d) 000122347322871
c) 56152240784 30. Which errors in a single digit of a 15-digit airline ticket
d) 66606631178 identification number can be detected?
∗ 31. Can the accidental transposition of two consecutive dig-
20. One digit in each of these identification numbers of a
postal money order is smudged. Can you recover the its in an airline ticket identification number be detected
smudged digit, indicated by a Q, in each of these num- using the check digit?
bers? Periodicals are identified using an International Standard
a) Q1223139784 Serial Number (ISSN). An ISSN consists of two blocks
b) 6702120Q988 of four digits. The last digit in the second block is a check
c) 27Q41007734 digit. This check digit is determined by the congruence d 8 ≡
d) 213279032Q1 3d 1 + 4d 2 + 5d 3 + 6d 4 + 7d 5 + 8d 6 + 9d 7 (mod 11). When
d 8 ≡ 10 (mod 11), we use the letter X to represent d 8 in the
21. One digit in each of these identification numbers of a
postal money order is smudged. Can you recover the code.
smudged digit, indicated by a Q, in each of these num- 32. For each of these initial seven digits of an ISSN, deter-
bers? mine the check digit (which may be the letter X).
a) 493212Q0688 a) 1570-868
b) 850Q9103858 b) 1553-734
c) 2Q941007734 c) 1089-708
d) 66687Q03201 d) 1383-811
22. Determine which single digit errors are detected by the 33. Are each of these eight-digit codes possible ISSNs? That
USPS money order code. is, do they end with a correct check digit?
23. Determine which transposition errors are detected by the a) 1059-1027
USPS money order code. b) 0002-9890
24. Determine the check digit for the UPCs that have these c) 1530-8669
initial 11 digits. d) 1007-120X
a) 73232184434 34. Does the check digit of an ISSN detect every single error
b) 63623991346 in an ISSN? Justify your answer with either a proof or a
c) 04587320720 counterexample.
d) 93764323341 35. Does the check digit of an ISSN detect every error where
25. Determine whether each of the strings of 12 digits is a twoconsecutivedigitsareaccidentallyinterchanged?Jus-
valid UPC code. tify your answer with either a proof or a counterexample.