PreTeXt Sample Book: Abstract Algebra (SAMPLE ONLY)

<exercises>
  <title>Additional Exercises: Detecting Errors</title>





  <exercise>
    <title>UPC Symbols</title>
    <statement>
      <p>
        Universal Product Code
            <idx><h>Universal Product Code</h></idx>
        (UPC) symbols are found on most products in grocery and retail stores.
        The UPC symbol is a 12-digit code identifying the manufacturer of a product and the product itself
        (<xref ref="figure-upc-codes" />).
        The first 11 digits contain information about the product;
        the twelfth digit is used for error detection.
        If <m>d_1 d_2 \cdots d_{12}</m> is a valid UPC number, then
        <me>
          3 \cdot d_1 + 1 \cdot d_2 + 3 \cdot d_3 + \cdots + 3 \cdot d_{11} + 1 \cdot d_{12} \equiv 0 \pmod{10}
        </me>.
      </p>
      <ol>
        <li>
          <p>
            Show that the UPC number 0-50000-30042-6, which appears in <xref ref="figure-upc-codes" />, is a valid UPC number.
          </p>
        </li>
        <li>
          <p>
            Show that the number 0-50000-30043-6 is not a valid UPC number.
          </p>
        </li>
        <li>
          <p>
            Write a formula to calculate the check digit,
            <m>d_{12}</m>, in the UPC number.
          </p>
        </li>
        <li>
          <p>
            The UPC error detection scheme can detect most transposition errors;
            that is, it can determine if two digits have been interchanged.
            Show that the transposition error 0-05000-30042-6 is not detected.
            Find a transposition error that is detected.
            Can you find a general rule for the types of transposition errors that can be detected?
          </p>
        </li>

        <li>
          <p>
            Write a program that will determine whether or not a UPC number is valid.
          </p>
        </li>
      </ol>
      <figure xml:id="figure-upc-codes">
        <caption>A UPC code</caption>
        <image width="30%" source="UPCcode.png" />
      </figure>
    </statement>
  </exercise>
  <exercise>
    <statement>
      <p>
        It is often useful to use an inner product notation for this type of error detection scheme;
        hence, we will use the notion
        <me>
          (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n }
        </me>
        to mean
        <me>
          d_1 w_1 +  d_2 w_2 + \cdots +  d_k w_k  \equiv 0  \pmod{ n}
        </me>.
      </p>
      <p>
        Suppose that <m>(d_1, d_2, \ldots,
        d_k ) \cdot (w_1, w_2, \ldots,
        w_k ) \equiv 0 \pmod{ n}</m> is an error detection scheme for the <m>k</m>-digit identification number <m>d_1 d_2 \cdots d_k</m>,
        where <m>0 \leq d_i \lt n</m>.
        Prove that all single-digit errors are detected if and only if
        <m>\gcd( w_i, n ) = 1</m> for <m>1 \leq i \leq k</m>.
      </p>
    </statement>
  </exercise>
  <exercise>
    <statement>
      <p>
        Let <m>(d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots,
        w_k ) \equiv 0 \pmod{ n}</m> be an error detection scheme for the <m>k</m>-digit identification number <m>d_1 d_2 \cdots d_k</m>,
        where <m>0 \leq d_i \lt n</m>.
        Prove that all transposition errors of two digits <m>d_i</m> and <m>d_j</m> are detected if and only if
        <m>\gcd( w_i - w_j, n ) = 1</m> for <m>i</m> and <m>j</m> between 1 and <m>k</m>.
      </p>
    </statement>
  </exercise>
  <exercise>
    <title>ISBN Codes</title>
    <statement>
      <p>
        Every book has an International Standard Book Number<idx><h>International standard book number</h></idx> (ISBN) code.
        This is a 10-digit code indicating the book's publisher and title.
        The tenth digit is a check digit satisfying
        <me>
          (d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 )  \equiv 0 \pmod{11}
        </me>.
        One problem is that <m>d_{10}</m> might have to be a 10 to make the inner product zero;
        in this case, 11 digits would be  needed to make this scheme work.
        Therefore, the character X is used for the eleventh digit.
        So ISBN 3-540-96035-X is a valid ISBN code.
      </p>
      <ol>
        <li>
          <p>
            Is ISBN 0-534-91500-0 a valid ISBN code?
            What about ISBN 0-534-91700-0 and ISBN 0-534-19500-0?
          </p>
        </li>
        <li>
          <p>
            Does this method detect all single-digit errors?
            What about all transposition errors?
          </p>
        </li>
        <li>
          <p>
            How many different ISBN codes are there?
          </p>
        </li>
        <li>
          <p>
            Write a computer program that will calculate the check digit for the first nine digits of an ISBN code.
          </p>
        </li>
        <li>
          <p>
            A publisher has houses in Germany and the United States.
            Its German prefix is <c>3-540</c>.
            If its United States prefix will be <c>0-abc</c>,
            find <c>abc</c> such that the rest of the ISBN code will be the same for a book printed in Germany and in the United States.
            Under the ISBN coding method the first digit identifies the language; German is <c>3</c> and English is <c>0</c>.
            The next group of numbers identifies the publisher,
            and the last group identifies the specific book.
          </p>
        </li>
      </ol>
    </statement>
  </exercise>
</exercises>