Math 190H Honors Discrete Mathematics for Computing Identification Numbers, Universal Product Codes, and Check Digits Project: Due Wednesday, December 9, 2015 Background An International Standard Book Number (ISBN-10) is a number used to identify a particular book printed before 2007. The number is a ten digit code x1 x2 ,..., x10 . The first nine digits identify the language, publisher, and the number assigned to the book. The last digit is a check digit, which can either be 0,1,...9, or an X which is used to replace 10. The check digit is chosen to satisfy the equality 10 1 ixi 0 mod11 . This check digit enables one to detect single digit errors and transposition of digits. An International Standard Book Number (ISBN-13) is a number used to identify a particular book printed during or after 2007. The number is a 13 digit code x1 x2 ,..., x13 , with the last digit being the check digit. Each digit, from left to right, is alternately multiplied by 1 or 3, then those products are summed mod 10. This value is then subtracted from 10 giving an integer between 1 and 10. If our result is 10, we replace it by 0. Hence the check digit is between 0 and 9. A Universal Product Code (UPC) is a number used to identify a particular product. To prevent against errors while a UPC symbol is scanned, a check digit is used. The last digit in the UPC number is the check digit. If the scanner detects an error, the UPC symbol must be rescanned. To determine if a UPC symbol is valid, the following check procedure is used: Multiply each of the digits in odd positions by 3, and add the digits in the even positions. If this total is a multiple of 10, then the number is a valid UPC. If the total is not a multiple of 10, then the number is not a valid UPC. Example. Is the UPC 0-34707-01993-5 a valid code? We can think of the digits being in positions 1 through 12. First, we multiply each of the digits in odd positions by 3. 3(0)+3(4)+3(0)+3(0)+3(9)+3(3) = 48 Then we add up the digits in the even positions. 3+7+7+1+9+5 = 32 Adding our two subtotals, we have a sum of 48+32 = 80. Since the total of 80 is a multiple of 10, 0-34707-01993-5 is a valid UPC. Part I 1. ISBN Codes In each of the following parts, determine if the given number is a valid ISBN. (a) (b) (c) (d) (e) 0-14-015505-8 1-55874-262-X 0-673-53025-0 0-14-006747-7 0-671-35581-1 2. UPCs In each of the following parts, determine if the given number is a valid UPC. (f) (g) (h) (i) (j) 0-68274-34542-5 0-51122-17301-1 0-70330-13888-8 7-18103-02052-7 0-71662-01402-6 Part II: An ISBN-10 Scavenger Hunt In each of the parts below, one digit has been deleted from the given ISBN. Determine what the missing number is and recover the entire ISBN. Finally, use www.isbn.nu (or other website or search engine) to determine the author and title of the book. Be sure to show all of your work. (a) (b) (c) Part III: An ISBN-13 Scavenger Hunt In 2007 the ISBN-10 codes were lengthened to include 13 digits. In each of the parts below, one digit has been deleted from the given ISBN-13. Determine what the missing number is and recover the entire ISBN-13. Finally, use www.isbn.nu (or other website or search engine) to determine the author and title of the book. Be sure to show all of your work. (a) (b) Part IV: Analysis of Universal Product Codes (UPC) 1. Prove that if a single digit of a valid UPC is changed then the new code is not valid. 2. If two digits are changed in a valid UPC, the new code may or may not be valid. Determine the type of changes to two digits that result in a valid code, and determine the change to two digits that result in a code that is not valid. Justify both of your answers