16.1 Check Digits

1. Determine the check digit for a money order with identification number 3953981640.

2. Determine the value of ? so that 7?345417803 is a valid money order identification number.

3. Determine the check digit for the Avis identification number 873345672.

4. Determine two values for ? that will make 723459?0161 a valid Postal Service money order number.

5. Determine the check digit for the airline ticket number 30860422052.

6. Suppose a money order with the identification number and check digit 21720421168 is erroneously copied as 27750421168. Will the error be detected? Explain your reasoning.

7. Determine the check digit for the travelers cheque with identification number 661340874.

8. Determine the check digit for an Avis rental car with identification number 651421.

9. If a Postal Service money order with identification number has the check digit 5, what is the check digit for the Postal Service money order number ?

10. Which of the error detection schemes below will detect some errors of the form (jump transposition)?

11. If an Avis identification number has the check digit 5, what is the check digit for the Avis identification number ?

12. Find the check digit for the UPC number 03608072089.

13. Suppose that the packaging of a retail item were damaged in such a way that the first digit of a 12-digit UPC code was scratched off, but the remaining 11 digits were 88072303584; determine the first digit.

14. The fourth digit of the UPC number shown below is not discernible. Determine the correct value.

15. If one randomly chooses a large number of 10-digit ISBNs, about what percent would have an in the check digit position?

16. Determine the ISBN-10 check digit for the number 0-547-16509.

17. Determine the ISBN-13 check digit for the number 978-0-547-16509.

18. When the eighth edition of this textbook was in preparation, the publisher sent the author of this section the following ISBNs for the book: ISBN-10: 1- 4292-0900-3; ISBN-13: 978-1-4292-0890-0. How did the author know the ISBN-13 was wrong, and how did he know how to correct it? (This really happened!)

19. When calculating the check digit for a 13-digit ISBN, why can you disregard the first two digits? (Try it for Exercise 16.)

20. Determine the check digit for the bank routing number 09100001.

21. Determine the check digit for an American Express Travelers Cheque with identification number 461212023.

22. Suppose that a check digit is assigned to a four-digit number by appending the remainder after division by 7. If the number 36806 has a single-digit error in the first position, determine the possibilities for the correct number.

23. Determine whether the MasterCard number 3541 0232 0033 2270 is valid.

24. Suppose that the digit indicated by a question mark in the MasterCard number 426452002177?337 is unreadable. What is the unreadable digit?

25. Suppose that a valid credit card number of the form is changed to . Is the result a valid credit number?

26. Suppose that a valid credit card number of the form is changed to . Is the result a valid credit number?

27. Suppose a correctly coded credit card number is modified in such a way that the sum produced by the Luhn algorithm is increased by 10. Explain why the credit card error detection method does not detect the error. What happens if the sum is increased by 12?

28. If a number of the form is a valid credit card number, what is the check digit for a credit number of the form ?

29. If a credit card number of the form is valid credit card number, what is the check digit for a credit number of the form ?

30. Replace the question mark in the number JM1GD222?J1581570 with a digit that will result in a valid VIN. (See Spotlight 16.1 on page 678 for a description of the method to be used.)

31. Create a check digit for the UPC number 38137009213 using the weights 7, 1, 7, 1, 7, 1, …, 7, 1, instead of 3, 1, 3, 1, 3, 1, …, 3, 1. Test to see whether this check digit will detect single-digit errors by trying several examples.

32. Create a check digit for the UPC number 38137009213 using the weights 2, 1, 2, 1, 2, 1, …, 2, 1, instead of 3, 1, 3, 1, 3, 1, …, 3, 1. Is the error caused by replacing the 3 in the first position with an 8 detected? What about the error caused by replacing the 1 in the third position with a 6? Explain why or why not.

33. If the weights 5, 1, 5, 1, 5, 1, …, 5, 1 were used for the UPC code, which single-digit errors would go undetected?

34. Exercises 31-33 reveal that using the weights 1, 3, or 7 for a particular position detects all errors in that position, whereas using weights 2 or 5 in a position does not detect all errors. Using this observation, make a guess about error-detection capability using weights 9, 4, 6, or 8.

35. Enter the number 036000260809 in a Google search box. Is it a valid UPC number? Now change any one digit. Is the new number a valid UPC number? Try a different change.

36. Suppose that a valid credit card number is mistakenly entered into a credit card reader as . Explain why the Luhn algorithm does not detect the error.

37. If a valid credit card number using the Luhn algorithm has the form , determine the check digit of the number if the first two digits were transposed and the digits in positions 3 through 15 were unchanged.

38. If a credit card number of the form is a valid credit card number, what is the check digit for a credit card number of the form ?

39. Explain why encoding ID numbers by multiplying them by 15 would not detect the single-digit error of replacing 114180 by 114150.

40. Explain why encoding ID numbers by multiplying them by 15 would not detect the transposition error of replacing 125025 by 120525.

41. Explain why encoding ID numbers by multiplying them by 17 would detect all single-digit errors, adjacent transposition errors, and jump transposition errors.

42. State a general criterion for the detection of an error of the form for the routing number of a checking account.

43. The 10-digit ISBN 0-669-03925-4 is the result of a transposition of two adjacent digits not involving the first or last digit. Determine the correct ISBN.

44. Explain why the bank scheme will detect the error but the UPC scheme will not.

45. Suppose that the check digit for the bank routing number was chosen to be the last digit of instead of using the method described in this chapter. How would this compare with the actual check digit?

46. Explain why an error caused by transposing the first two digits of a Postal Service money order is not detected by the check-digit scheme. Explain why the same is true for the second and third digits. What about the last two digits?

47. Suppose that a company assigns an extra digit to every employee Social Security number by appending a 0 if the sum of the digits is even and a 1 if the sum is odd. If a 2 were mistakenly read as a 7, would the error be detected? What if a 2 were mistakenly read as an 8? Try a few other experiments with single-digit errors. (For experiments, you can use three-digit numbers instead of nine-digit numbers.) Determine which errors are detected by this method. Explain your reasoning. Approximately what percentage of errors is detected by appending the extra digit?

48. Explain why the Postal Service money order check-digit scheme does not detect the mistake of substituting a 0 for a 9, or vice versa.

49. Which digit never appears as a check digit on a Postal Service money order?

50. Which digit never appears as a check digit on an American Express Travelers Cheque?

51. Which digits never appear as a check digit for an airline identification number?

52. Suppose that four-digit numbers are assigned a check digit so that is evenly divisible by 10. Test the number 43216 created in this way to see whether the method detects adjacent transposition errors.

53. Starting with the 10-digit ISBN 0-7167-4782-0, create three new numbers by transposing any two different digits. (They need not be adjacent.) Are these errors detected by the scheme?

54. Suppose that in an Avis identification number, an 8 is mistaken for a 5. Is the error detected? What if a 9 is mistaken for a 2?

55. Give an argument to show that the 10-digit ISBN error-detection method will detect a digits. Does the same argument work for the fourth transposition error involving the first and third and sixth digits?

56. Suppose the check digit of 10-digit ISBNs were chosen so that is divisible by 11 instead of using the method described in the chapter. How would this compare with the actual check digit?

57. Consider a UPC number in which the digits 7 and 2 appear consecutively (i.e., the number has the form ). Will the error caused by transposing these digits (i.e., the number is taken as ) be detected? What if the digits 6 and 2 were transposed instead? State the general criterion for the detection of an error of the form by the UPC scheme.

58. If the first three digits of a routing number for a checking account are 537 and the 5 and 3 are transposed, will the error be detected? If the first three numbers are 237 and the 2 and 7 are transposed, will the error be detected?

59. The Canadian province of Quebec assigns a check digit to an 11-digit driver’s license number so that is divisible by 10. Criticize this method. Describe all single-digit errors that are undetected by this scheme.

60. Speculate on the reason why telephone numbers, Social Security numbers, and serial numbers on most currency do not have check digits.

61. Suppose that a company uses a check-digit scheme similar to the UPC scheme, except that instead of using the UPC weights 3, 1, 3, 1, …, it uses , 1, , 1, …. If two of the ID numbers used by the company are 73215674 and 73215661, determine .

62. If a publishing company has headquarters in both the United States and Germany and publishes the same book in both countries, it is likely that the 10-digit ISBN for the book will be identical except for the first and last digits (because the first digit for U.S. publications is 0 and the first digit for German publications is 3). If the last digit of the U.S. edition is 1, what is the last digit for the German publication?

16.2 The ZIP Code

16.3 Bar Codes

63. Determine the ZIP + 4 code and check digit for each of the following Postnet bar codes.

64. In each of the following Postnet bar codes, exactly one mistake occurs (i.e., a long bar appears instead of a short one, or vice versa). Determine the correct ZIP code.

65. Below is a 12-digit delivery-point bar code. Determine the ZIP + 4 number, the last two digits of the street address, and the check digit.

66. If the check digit for the ZIP + 4 code for a house on 1738 Maple Street is 3, what would the check digit for the delivery-point code be?

67. Find the check digit for the ZIP + 4 code 50037-2452.

68. Explain why any two errors in a particular block of five bars in a Postnet code are always detectable. Explain why not all such errors can be corrected.

69. Form all possible strings consisting of exactly three ’s and two ’s and arrange the strings in alphabetical order. (For example, the first two possibilities are aaabb and aabab.) Do you see any relationship between your list and the Postnet code?

70. The back cover of recently published books includes a bar code that has the 10-digit ISBN above the bars and a 13-digit identification number below the bars (see below). Examine the bar code on several books. How does the number below the bar code differ from the UPC code?

71. Suppose that the first block of a UPC bar code following the guard bar pattern that a scanner reads is 1000100. Is the scanner reading left to right or right to left?

16.4 Encoding Personal Data

72. If a Social Security number begins with 0, the number was issued in a state in the

73. The Canadian postal system has assigned each geographic region a six-character code composed of alternating letters (not including D, F, I, O, Q, and U) and digits, such as P7B5E1 and K7L3N6. Discuss the advantages that this scheme has over the five-digit ZIP code used in the United States.

74. Given that the letters D, F, I, O, Q, and U are not used in the Canadian postal code (see the previous exercise), determine the maximum possible number of postal codes.

75. Determine the Soundex code for the names Hu, Lee, and Shaw.

76. Determine the Soundex code for Skow, Sachs, Lennon, Lloyd, Ehrheart, and Ollenburger.

77. Determine the total number of codes possible using the Soundex Coding System.

78. Explain why none of the following blocks of digits can be a Soundex code for someone’s last name: S-205, S-723, S-5513.

79. In Florida, the last three digits of the driver’s license number of a female with birth month and birth date are . For both males and females, the fourth and fifth digits from the end give the year of birth. Determine the last five digits of a Florida driver’s license number for a female born on July 18, 1942.

80. Thinking of the last three digits of a Florida driver’s license number as a 3-digit integer, what is the largest possible integer it can be?

81. Suppose two females with Florida driver’s licenses were born exactly one month apart. By how much would the 3-digit integers represented by the last three digits of their driver’s license numbers differ?

82. Describe a situation in which the 3-digit integers represented by the last three digits of the Florida driver’s licenses of identical twins could differ.

83. Explain why an Illinois driver’s license number that ends with the last five digits 03217 is suspicious.

84. Determine the last five digits of an Illinois driver’s license number for a male born on June 18, 1942.

85. In Illinois, one obtains the last three digits of the driver’s license number for a female by adding 600 to the number for a male with the same birthday. In Florida, 500 is added to the number for a male. Why can't Florida use 600?

86. Explain why an Illinois driver’s license number that ends with 77061 cannot be valid.

87. Determine the birth date of a person whose Illinois driver’s license number ends with 58818.

88. Provide three names that share the same Soundex code as Gallihan.

89. The state of Washington encodes the last two digits of the year of birth into driver’s license numbers (in positions 8 and 9) by subtracting the two-digit number from 100. For example, a person born in 1942 has 58 in positions 8 and 9, whereas a person born in 1971 has 29 in positions 8 and 9. Speculate on the reason for subtracting the birth year from 100.

90. Apply the Soundex code to common ways to misspell your name. Do they give the same code as your name does?

91. Why would the Soundex system of coding be a poor method for encoding names in China?

92. Explain why an error caused by transposing any two digits of an American Express Travelers Cheque is not detected by the check-digit scheme.

93. Determine the Soundex code for Smith, Schmid, Smyth, and Schmidt.

94. Driver’s license number-assignment schemes that use personal data sometimes produce the same number for different people. Speculate about circumstances under which this is more likely to occur.

95. When using the travelers cheque, credit card, or UPC number algorithms for detecting errors, does the computer have to know which digit is the check digit?

96. Change 173 into a Postnet code.

97. The following is an actual identification number and bar code from a roll of wallpaper. What appears to be wrong with them? Speculate on the reason for the apparent violation of the UPC format.

98. Explain why the last three digits of a valid Illinois driver’s license cannot be 373.