CEMC Banner

Problem of the Week
Problem C and Solution
Check Please 1

Problem

Debit and credit cards contain account numbers which consist of many digits. When shopping online, customers are often asked to type in their account number. Because there are so many digits, it is easy to make a mistake. The last digit of the number is a specially generated check digit which can be used to verify whether or not the number is valid. A common algorithm used for verifying numbers is called the Luhn Algorithm. The steps performed in the Luhn Algorithm are outlined in the flowchart below. Two examples are provided.

An alternative format for the flowchart diagram follows.

Example 1

  1. Number: \(135792\)

  2. Reversal: \(297531\)

  3. Digits in odd positions are underlined: \(\underline{2}9\underline{7}5\underline{3}1\) \[\begin{aligned} A&=2+7+3\\ &=12 \end{aligned}\]

  4. Double remaining digits: \[\begin{aligned} 2 \times 9 &= 18\\ 2 \times 5 &= 10\\ 2 \times 1 &= 2 \end{aligned}\]

  5. Calculate \(B\): \[\begin{aligned} B &= (1+8) + (1+0) + 2\\ &= 9 + 1 + 2\\ &= 12 \end{aligned}\]

  6. \(C=12+12=24\)

  7. \(C\) does not end in zero, so the number is not valid.

Example 2

  1. Number: \(1357987\)

  2. Reversal: \(7897531\)

  3. Digits in odd positions are underlined: \(\underline{7}8\underline{9}7\underline{5}3\underline{1}\) \[\begin{aligned} A&=7+9+5+1\\ &=22 \end{aligned}\]

  4. Double remaining digits: \[\begin{aligned} 2 \times 8 &= 16\\ 2 \times 7 &= 14\\ 2 \times 3 &= 6 \end{aligned}\]

  5. Calculate \(B\): \[\begin{aligned} B &= (1+6) + (1+4) + 6\\ &= 7 + 5 + 6\\ &= 18 \end{aligned}\]

  6. \(C=22+18=40\)

  7. \(C\) ends in zero, so the number is valid.

The number \(13X9\ Y659\ 784\) is a valid card number when verified by the Luhn Algorithm, where \(X\) and \(Y\) are each single digits such that \(X \le Y\).

Determine all possible values of \(X\) and \(Y\).

Solution

When the digits of the card number are reversed the resulting number is \(487\ 956Y\ 9X31\). The sum of the digits in the odd positions is \(A=4+7+5+Y+X+1=17+X+Y\).

When the digits in the remaining positions are doubled, the following products are obtained: \[8\times 2=16;\ 9\times 2=18;\ 6\times 2=12;\ 9\times 2=18;\ 3\times 2=6\] When the digit sums from each of the products are added, the sum is: \[B=(1+6)+(1+8)+(1+2)+(1+8)+6=7+9+3+9+6=34\] Since \(C= A+B\), we have \(C=17+X+Y+34=51+X+Y\).

For the card to be valid, the units digit of \(C\) must be zero. Since \(X\) and \(Y\) are digits, the minimum value of \(X+Y\) is \(0\) and the maximum is \(9+9=18\). So \(C\) must be between \(51\) and \(51+18=69\), inclusive. The only value in this range that has a units digit of \(0\) is \(60\). Thus, \(C=60\).

Since \(C=51+X+Y=60\), it follows that \(X+Y=9\). Since \(X \le Y\), the only possibilities for \(X\) and \(Y\) are shown in the following table:

\(X\) \(Y\)
\(0\) \(9\)
\(1\) \(8\)
\(2\) \(7\)
\(3\) \(6\)
\(4\) \(5\)

The corresponding card numbers are \(1309\ 9659\ 784\), \(1319\ 8659\ 784\), \(1329\ 7659\ 784\), \(1339\ 6659\ 784\), and \(1349\ 5659\ 784\), which are indeed verified by the Luhn Algorithm.