Mrs. Nguyen’s prestidigitation

From a set of 1 through 9 playing cards, I draw five cards and get cards showing 8, 4, 2, 7, and 5. I ask my 6th graders to make a 3-digit number and a 2-digit number that would yield the greatest product. I add, “But do not complete the multiplication — meaning do not figure out the answer. I just want you to think about place value and multiplication.”box model of 3 x 2 digit multiplication

The problem above comes from Fawn Nguyen, who teaches math at a public school in southern California and writes a blog called Finding Ways. To her students she is “Mrs. Win,” an English approximation to the Vietnamese pronunciation.

It’s clear that much care and craftsmanship went into formulating this problem. Why did Nguyen choose a two-digit-by-three-digit product, rather than two-by-two or three-by-three? The asymmetry ensures a unique solution. Why did she use playing cards to select the digits, rather than simply asking the kids to call out numbers? The cards produce a set of distinct digits, without duplicates, and they also rule out the possibility of choosing zero. Repeated digits or zeros would not ruin the problem, but they would needlessly complicate it. Nguyen’s classroom procedure eliminates these distractions without even mentioning them. This is the kind of subtle indirection you find in the performance of a first-rate stage magician.

I’ve had some serious fun with Nguyen’s problem. Finding the answer is not difficult—especially if you cheat and set aside her boldfaced injunction forbidding arithmetic. But of course the answer itself isn’t the point, as Nguyen makes clear in her blog post describing the students’ search for a solution. What we really care about is why one particular arrangement of those digits yields a larger product than all other arrangements. We want an explanatory pattern or principle, a rule that works not just for this one set of digits but for any instance of the max-product problem. I had many stumbles on the path to finding such a rule. Here are some notes I made along the way. But before reading on you might want to write down your own best guess at the answer.

  1. First, some notation. Let’s label the digits like so:

    x_{2}\; x_{1}\; x_{0}&{}\\
    \underline{\times \quad y_{1} \; y_{0}}&{},

    where the subscripts encode the power of 10 associated with each digit. The object is to find a one-to-one mapping between the sets \(\{x_{2}, x_{1}, x_{0}, y_{1}, y_{0}\}\) and \(\{8, 4, 2, 7, 5\}\) that maximizes the product.

  2. Nguyen’s sixth graders were quick to perceive one important principle: Larger digits should generally go to the left, and smaller digits to the right, in order to get the most benefit from place values in decimal notation. No one proposed 258 × 47 as the maximum product; that combination is obviously beaten by 852 × 74.
  3. If we wanted to solve this problem by exhaustive search, how exhausting would the search be? There are \(5! = 120\) permutations of the five digits, and each permutation corresponds to a different multiplication problem. But in view of the observation made in item 2, the number of plausible candidates is much smaller: just \(\binom{5}{2} = \binom{5}{3} = 10\). You could check them all in a matter of minutes. (But Mrs. Nguyen would not approve.)
  4. Again following the logic of item 2, we can stipulate that the 8—the largest of the five digits—must wind up either in position \(x_2\) or in position \(y_1\). The question is which. My first thought was that surely the 8 goes in the three-digit number, because position \(x_2\) gives the 8 a value of 800, whereas it’s only worth 80 as \(y_1\).
  5. My second thought undermined my first thought. Suppose the problem had been formulated without Mrs. Nguyen’s clever card trick, and we had to work with the digits 8, 7, 0, 0, 0. Then the arrangement yielding the maximum product is surely either 800 × 70 or 700 × 80. But of course those two products are both equal to 56,000. In other words, if we consider just the leading digits, it doesn’t matter which goes in the multiplier and which in the multiplicand.
  6. Let’s write out the full six-term polynomial defining the product:\[1000 x_{2}y_{1} + 100 x_{1}y_{1} + 10 x_{0}y_{1} + 100 x_{2}y_{0} + 10 x_{1}y_{0} + x_{0}y_{0}\]The leading term provides another way of understanding why the largest digit can be either \(x_2\) or \(y_1\). It’s just the commutative law. We get \(1000 x_{2}y_{1}\) with either ordering. Thus we need to consider the smaller terms to decide which placement is better. Hint: \(y_1\) appears in three terms but \(x_2\) turns up in only two.
  7. Maybe it would help to look at a smaller version of the problem? For example, maximize the product \(x_{1}\, x_{0} \times y_{0}\) with digits drawn from the set \(\{1, 2, 3\}\). Where does the largest digit belong?
  8. Here’s a vague, daydreamy notion: The task of maximizing the product of these numbers looks something like an isoperimetric problem. If you have a rectangle of perimeter \(2(h + w)\), you maximize the area \(hw\) by making \(h=w\), so that the rectangle becomes a square. Maybe, by analogy, we should make the three-digit and the two-digit numbers as close to equal as possible, while at the same time making both of them as large as possible.
  9. At this point I was ready to commit. I was persuaded by the arguments in items 6 and 7, and 8 that the largest digit should be bound to variable \(y_1\), and the next largest to \(x_2\). Then the same rule could be applied recursively to the remaining digits and variables, yielding this assignment:

    7\, 4\, 2&{}\\
    \underline{\times \quad 8 \, 5}&{}\\
    6\, 3\, 0\, 7\, 0&{}

  10. Of course you already know I was wrong. Even if you haven’t yet solved the problem for yourself or looked up the answer elsewhere, it’s a well-established principle of proper storytelling that no one ever stumbles on the right answer on the first try.

    My error was revealed by a program running an exhaustive-search algorithm. It showed that exchanging the positions of the 7 and the 8 yields a larger product:

    8\, 4\, 2&{}\\
    \underline{\times \quad 7 \, 5}&{}\\
    6\, 3\, 1\, 5\, 0&{}

    But that isn’t the right answer either. Instead of switching the 7 and 8, you can exchange the 5 and the 4 to get the following result, which does turn out to be optimal:

    7\, 5\, 2&{}\\
    \underline{\times \quad 8 \, 4}&{}\\
    6\, 3\, 1\, 6\, 8&{}

So that’s it—the answer we’ve been seeking, the maximum product, the solution to Mrs. Nguyen’s problem. There’s no arguing with arithmetic.

But it’s hardly the end of the trail. Why does that peculiar permutation of the digit set gives the biggest product? Does the same pattern work for other two-digit-by-three-digit products? What about problems of other shapes and sizes? And what is the pattern, anyway? How would you succinctly state the rule for placing digits in Mrs. Nguyen’s boxes?

In trying to make sense of what’s going on here, I’ve found a certain graphic device to be helpful. I call it a lacing diagram, because it reminds me of the various schemes for lacing up a pair of sneakers. The patterns are easier to perceive with larger numbers of digits (i.e., high-top sneakers), so the examples given below show sets of 10 digits arranged to form a five-by-five multiplication problem.

In a lacing diagram the red arrows trace a path that threads its way through all the digits, ordered from largest to smallest. Each segment of this path can either cross from one factor to the other (a trans step) or stay within the same factor (a cis step). The particular lacing shown here is made up of alternating trans and cis segments. The sequence of t’s and c’s below the diagram serves as a linearized encoding of the pattern; the number below the encoding is the product of the two factors.

Tctctctct 200

Here is the lacing diagram corresponding to the pattern that I initially believed would prevail in all Nguyen products:

Ttttttttt 200

In this case, all the steps are trans, as the arrows zigzag from one side to the other. The linear encoding consists of nine t’s.

And finally here is the lacing diagram for the winning permutation, the arrangement that gives the largest product. The pattern is the same as the second lacing diagram above—the zigzag—except for a single twist: The leftmost digits of the two factors have been switched, and so there is one cis step in the path.

lacing pattern tcttttttt

After a bit of puzzling, I was able to work out why that single twist yields a better score than the plain zigzag. It’s because \((9 \times 7) + (8 \times 6) = 111\), whereas \((9 \times 6) + (8 \times 7) = 110\). Likewise \((9 \times 5) + (8 \times 4) = 77\), whereas \((9 \times 4) + (8 \times 5) = 76\), and so on. Note the difference between the twisted and the zigzag products: \(8439739020\, - 8428629020 = 11110000\). Each of the four pairings of the leftmost digits with those to their right contributes a 1 in that difference.

If one twist is a good thing, maybe more twists would be even better? For example, if we invert the 5 and the 4, we get \((5 \times 3) + (4 \times 2) = 23\) instead of \((5 \times 2) + (4 \times 3) = 22\), again for a net gain. But of course there’s a flaw in this strategy. Flipping the 5 and the 4 increases their products with neighboring digits to the right, but lowers those with digits to the left. Flipping the leftmost digits doesn’t run afoul of this rule because there are no neighbors to the left.

For a more explicit definition of the zigzag-with-a-twist arrangement, here is a Python implementation. The basic idea is to deal out the digits alternately to the \(x\) and \(y\) factors, starting with \(x\) and working through the digits in descending order. When \(y\) (the smaller factor) runs out of room, any remaining digits are tacked onto the end of \(x\). Finally—this is the twist—the leftmost \(x\) and \(y\) digits are swapped. This procedure works in any base.

def twisted_zigzag(digit_set, s):
    s = min(s, len(digit_set) - s)    # len of smaller factor
    digits = sorted(list(digit_set))  # smallest to largest
    x = []
    y = []
    while digits:                     # pop from end of list
        x.append(digits.pop())        # start with x
        if len(y) < s:                # zigzag until y is full
    x[0], y[0] = y[0], x[0]           # swap first digits
    return x, y

Does the zigzag-with-a-twist arrangement give the maximum product for all possible Nguyen-type problems? I can offer substantial evidence supporting that proposition. For base-10 numbers formed without repeated digits there are 4,097 two-factor multiplication problems with digits sorted in descending order. The zigzag-twist pattern gives the correct result for all of them.For digit sets that include 0, the solution is not always unique. Indeed, the algorithm works for all problems in bases between 2 and 15. It’s hardly a daring conjecture to suggest that it works in all bases, but I have not produced a proof. Maybe Mrs. Nguyen’s sixth graders will do so.

This entry was posted in mathematics.

7 Responses to Mrs. Nguyen’s prestidigitation

  1. Jon says:

    That’s bizarre. I must say, I saw the right answer immediately. Here is my logic.

    Instead of a 3-digit number times a 2-digit number, divide the numbers by powers of 10 so you get, in decimal:
    a.bc * d.e
    Should the 8 be in d or a? Well, it is almost symmetrical, but in position d it will get to multiply 0.bc, which can be greater than 0.e. So
    7.bc * 8.e
    Where should the 5 go? Of course, b, so it multiplies 8 instead of 7. Then done.

    I think this same logic proves the pattern for all of these problems, in all bases.

  2. Jon says:

    Sorry, I guess I skipped the last step. After assigning the 5, you have
    75.c * 8.e
    The 4 should go to e since 75>8. Basically, the zig-zag pattern comes from shifting the digits, so you always know which side is going to be bigger and the next larger digit is placed on the other side.

  3. Jordan says:

    Very interesting assignment! I have to applaud Ms. Nguyen for making a problem that helps sixth graders but also intrigues me as a good thought experiment. It helps consider the why in math which is something that, at least back when I was in sixth grade, was something my teachers rarely inspired in their students.

  4. Barry Cipra says:

    I stopped reading at the suggested pause point and came up with this:

    Think of there being a decimal point after the first digit in each number, i.e., you’re multiplying a.bc times d.e with digits 2, 4, 5, 7, and 8. The observation that the digits be in decreasing order in each number is taken to be obvious. For simplicity, we might as well include 0 as a sixth digit, so we can assume we’re looking to maximize 8.bc times d.ef with digits 0, 2, 4, 5, and 7.

    If we take d=7, the product is at least 8×7=56, whereas otherwise it is less than 9×6=54, so we now want to maximize 8.bc times 7.ef with a distribution of 0, 2, 4, and 5. The 5 now is either b or e. Clearly you get more “bang for your buck” when you multiply .5 by 8 instead of 7, so we should put it in the e position.

    At this point it makes sense to move the decimal point and write the problem as 8.bc times 75.f with digits 0, 2, and 4. In this case, you get (a lot) more from multiplying .4 by 75 instead of 8, so we should let b=4. This leads to 84.c times 75.f, so the .2 gives more when it multiplies 84 than 75, and that leads to the final answer, 84 times 752.

  5. Evo says:

    Nice problem.

    In deciding the final step, I came to the correct decision by thinking geometrically. At the final step we are simply trying to ascertain if the 2 goes after the 75 or the 84. However consider the following dimensioned rectangles: A - 752 x 84 and B - 842 x 75.
    Remember that the closer the sides of a rectangle, the larger the area (with maximal area for perimeter occupier ring in the case of a square). It then follows that the area of A must be greater than the area of B because it is closer to a square…hence the answer!