PreTeXt Sample Book Abstract Algebra (SAMPLE ONLY)

  <exercises>
    <title>Additional Exercises: Detecting Errors</title>
<!--EXERCISE GROUP
<introduction>
<p>Credit card companies, banks, book publishers, and supermarkets all take advantage of the properties of integer arithmetic modulo <m>n</m> and group theory to obtain error detection schemes for the identification codes that they use.</p>
</introduction>
-->
<!-- % TWJ, 2010/03/31 -->
<!-- % Fixed figure reference -->
<!-- % TWJ, 2012/10/21 -->
<!-- % Deleted the word "now" in the description of UPC symbols.  Suggested by R. Beezer. -->
    <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>
<!-- % Corrected exercise. Suggested by John Watterlond. TWJ 8/24/2011 -->
          <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>