CEMC Banner

Problem of the Week
Problem D and Solution
Check Please 2

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 \(8764\ X6X5\ X6X8\ 5409\) is a valid card number when verified by the Luhn Algorithm, where \(X\) is a single digit. Determine all possible values of \(X\).

Solution

Solution 1

When the digits of the number are reversed the resulting number is \(9045\ 8X6X\ 5X6X\ 4678\). The sum of the digits in the odd positions is \[A=9+4+8+6+5+6+4+7=49.\] When the digits in the remaining positions are doubled, the following products are obtained: \[2(0)=0;\ 2(5)=10;\ 2(X)=2X;\ 2(X)=2X;\] \[2(X)=2X;\ 2(X)=2X;\ 2(6)=12;\ 2(8)=16\] Let \(n\) represent the sum of the digits of \(2X\).

When the digit sums from each of the products are added, the sum is: \[B=0+(1+0)+n+n+n+n+(1+2)+(1+6)=0+1+4n+3+7=4n+11.\] Since \(C=A+B\), we have \(C=49+4n+11=60+4n\).

When an integer from \(0\) to \(9\) is doubled and the digits of the product are added together, what possible sums can be obtained? We summarize these in the following table.

Original Digit \((X)\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\)
Twice the Original Digit \((2X)\) \(0\) \(2\) \(4\) \(6\) \(8\) \(10\) \(12\) \(14\) \(16\) \(18\)
The Sum of the Digits of \(2X\) \((n)\) \(0\) \(2\) \(4\) \(6\) \(8\) \(1\) \(3\) \(5\) \(7\) \(9\)

Notice that the sum of the digits of \(2X\) can be any integer from \(0\) to \(9\) inclusive. It follows that the only values for \(n\) are the integers from \(0\) to \(9\).

To be a valid number, the units digit of \(C\) must be \(0\). We want \(60+4n\) to be an integer whose units digit is \(0\). Since the minimum value of \(n\) is \(0\), it follows that \(60+4n \ge 60\). We will now look at cases based on the value of \(60+4n\).

Therefore, the two valid possibilities for \(X\) are \(0\) and \(7\).

When \(X=0\), the number is \(8764\ 0605\ 0608\ 5409\), which is indeed valid by the Luhn Algorithm.
When \(X=7\), the number is \(8764\ 7675\ 7678\ 5409\) which is indeed valid by the Luhn Algorithm.

Solution 2

The second solution looks at each of the possible values of \(X\) and then verifies the resulting number. A computer program or spreadsheet could be developed to solve this problem efficiently.

Remember that \(A\) is the sum of the digits in the odd positions of the reversal. Each of the digits in the even positions of the reversal are doubled, and \(B\) is the sum of the sum of the digits of each of these products. \(C\) is the sum \(A+B\).

\(\boldsymbol{X}\) Number Reversal \(\boldsymbol{A}\) Double Even Digits \(\boldsymbol{B}\) \(\boldsymbol{C}\) Valid?
\(0\) \(8764\ 0605\ 0608\ 5409\) \(9045\ 8060\ 5060\ 4678\) \(49\) \(0\), \(10\), \(0\), \(0\), \(0\), \(0\), \(12\), \(16\) \(11\) \(60\) Yes
\(1\) \(8764\ 1615\ 1618\ 5409\) \(9045\ 8161\ 5161\ 4678\) \(49\) \(0\), \(10\), \(2\), \(2\), \(2\), \(2\), \(12\), \(16\) \(19\) \(68\) No
\(2\) \(8764\ 2625\ 2628\ 5409\) \(9045\ 8262\ 5262\ 4678\) \(49\) \(0\), \(10\), \(4\), \(4\), \(4\), \(4\), \(12\), \(16\) \(27\) \(76\) No
\(3\) \(8764\ 3635\ 3638\ 5409\) \(9045\ 8363\ 5363\ 4678\) \(49\) \(0\), \(10\), \(6\), \(6\), \(6\), \(6\), \(12\), \(16\) \(35\) \(84\) No
\(4\) \(8764\ 4645\ 4648\ 5409\) \(9045\ 8464\ 5464\ 4678\) \(49\) \(0\), \(10\), \(8\), \(8\), \(8\), \(8\), \(12\), \(16\) \(43\) \(92\) No
\(5\) \(8764\ 5655\ 5658\ 5409\) \(9045\ 8565\ 5565\ 4678\) \(49\) \(0\), \(10\), \(10\), \(10\), \(10\), \(10\), \(12\), \(16\) \(15\) \(64\) No
\(6\) \(8764\ 6665\ 6668\ 5409\) \(9045\ 8666\ 5666\ 4678\) \(49\) \(0\), \(10\), \(12\), \(12\), \(12\), \(12\), \(12\), \(16\) \(23\) \(72\) No
\(7\) \(8764\ 7675\ 7678\ 5409\) \(9045\ 8767\ 5767\ 4678\) \(49\) \(0\), \(10\), \(14\), \(14\), \(14\), \(14\), \(12\), \(16\) \(31\) \(80\) Yes
\(8\) \(8764\ 8685\ 8688\ 5409\) \(9045\ 8868\ 5868\ 4678\) \(49\) \(0\), \(10\), \(16\), \(16\), \(16\), \(16\), \(12\), \(16\) \(39\) \(88\) No
\(9\) \(8764\ 9695\ 9698\ 5409\) \(9045\ 8969\ 5969\ 4678\) \(49\) \(0\), \(10\), \(18\), \(18\), \(18\), \(18\), \(12\), \(16\) \(47\) \(96\) No

Therefore, the two valid possibilities for \(X\) are \(0\) and \(7\).