How to arrange these 10 digits to make a correct equation?

Question

My daughter brought home the "problem of the week" last night and it was explained to me as this:

Given the following digits: $$1\ \ 1\ \ 2\ \ 3\ \ 3\ \ 4\ \ 5\ \ 6\ \ 6\ \ 7$$

Arrange them in this equation to make a correct answer: $$\_\ \_\ \_\ \times \_\ \_ = \_\ \_\ \_\ \_\ \_$$

I did find 4 possible solutions, and will put them at the bottom of this post, don't look if you want to try it yourself first. My question is more about the method to solve this, not the answer.

So I did a little homework, and found out that there are about 3.6 million ways to arrange 10 characters ($10!$). However, since the $1$, $3$, and $6$ are repeated, it knocks it down to a much more manageable ~$470,000$ possibilities.

Here teacher told her that there was only one correct answer.

I tried to just use some common sense to narrow the possibilities down but it still seemed like there were way too many permutations to try.

So I decided to brute force it with a Java program. After spending some time working on a few performance tweaks, I can attempt all ~$470,000$ combinations in about 2 seconds on my mac. I found that the teacher was incorrect and there are 4 possible permutations that are correct.

How would an 11-year old student with no programming experience solve this problem? Is there some "new math" ;) that I don't understand?

EDIT: I ported my Java program to Javascript, so you can play around with it. Not much input validation or error handling, but here you go: Problem of the week

My Solutions:

$$617 \times 43 = 26531$$ $$667 \times 23 = 15341$$ $$653 \times 37 = 24161$$ $$637 \times 23 = 14651$$

Answer 1

This is not a particularly elegant answer, but I do think that it is possible to narrow down the number of possibilities to around 100, by hand, in a couple hours. Incorporating an extra step will narrow it down to just a few dozen which can be checked by multiplying out. The strategy is mostly algorithmic, but it also incorporates some observations which allow us to rule out a number of possibilities on the fly.

We write the equation in the following form, where each letter represents a digit: $$ abc \times de = fghij.$$

The first step is to look at all admissible digits for the triple $(c,e,j)$. It is not difficult to check that there are 14 such triples. The second step is to use these triples to determine admissible digits for the triple $(b,d,i)$. We find that there are about 10 triples which work for each $(c,e,j)$. Finally, we make several observations to quickly rule out a number of these possibilities. For example, it is impossible (except some special cases) to have $d=1$, since this generally results in a product under $12000$. It is similarly easy to rule out many cases where $d=2$ or $a=1$. In general, these observations can be summarized: in step 3 we check the largest digits $a$, $d$ and $f$ to rule out cases where the product $ad$ does not jive with the remaining options for $f$.

Here is an example. Consider the admissible triple $(c,e,j) = (7,6,2)$. In this case, the triple $(b,d,i)$ must satisfy the equation $6b+4+7d \equiv i$ (mod $10$). Checking through the remaining digits $1,1,3,3,4,5,6$ gives six possibilities for $(b,d,i)$: $(1,3,1)$, $(3,6,4)$, $(4,1,5)$, $(4,5,3)$, $(5,1,1)$, $(6,3,1)$. Based on the above observations, we can rule out $(4,1,5)$ and $(5,1,1)$, since $d=1$. For the triple $(1,3,1)$, we have now exhausted both $1$s and the $2$, meaning we must have $f \geq 3$, yet no choice of $a$ gives this $f$. Similar considerations of $a$ and $f$ can rule out the final three options.

In total, I did the above computation for $5$ of the $14$ admissible triples $(c,e,j)$, and for each of the $5$, I found between $6$ and $16$ admissible triples $(b,d,i)$ (I found $6$, $6$, $9$, $15$, and $16$ for the five triples I tried). Eleven of these $52$ can be ruled out by elementary considerations (e.g. $d \neq 1$) and many more by slightly extra computation (comparing possibilities for $a$ and $f$).

I do not claim that an $11$ year old could narrow down the possibilities so quickly, but it is possible to narrow it down to around 100 possible $6$-tuples $(c,e,j,b,d,i)$ in under a couple hours. If one adds the final step of checking suitable $a$ and $f$, I do believe that an eager mathematician could use this algorithm to find all solutions by hand.

Answer 2

You can reduce it to $6570$ possibilities, since you just need to choose the digits on the left side and that uniquely determines the right side.
This can be cut down more, maybe even to the point where you could do it, rather tediously, by hand, if you choose the lowest-order digits first and winnow out the cases where this implies impossible digits on the right.

Thus suppose you guess that the lowest-order digit of the first number is $2$. Then the only possibilities for the lowest-order digits of the second are $3$ ($2 \times 3 = 6$) and $7$ ($2 \times 7$ ends in $4$). If it's $3$, then removing a $2$, $3$ and $6$ leaves $1,1,3,4,5,6,7$ from which we choose the second-lowest digits on the left...

Answer 3

Even if we restrict ourselves to legal combinations of lowest-order digits, it would be tedious to write out the possible ways to place digits into the left side of the equation. Coding this up in Python handles this in under 0.1 second and yields 2304 possibilities.

# Compute products of the form ABC x DE, choosing digits from:
all_digits = [1, 1, 2, 3, 3, 4, 5, 6, 6, 7]

# Possible values for C, and corresponding choices for E:
c_list = [1, 2, 3, 4, 6, 7]
e_map = { 1:[3,6], 2:[3,7], 3:[1,2,4,7], 4:[3], 6:[1,7], 7:[2,3,6] }

ntry = 0
for c in c_list:
#for c in set(all_digits):
    remain1 = all_digits[:]
    remain1.remove(c)
    for e in e_map[c]:
    #for e in set(remain1):
        remain2 = remain1[:]
        remain2.remove(e)
        for a in set(remain2):
            remain3 = remain2[:]
            remain3.remove(a)
            for b in set(remain3):
                remain4 = remain3[:]
                remain4.remove(b)
                for d in set(remain4):
                    ntry += 1
                    remain5 = remain4[:]
                    remain5.remove(d)
                    n1 = 100*a + 10*b + c
                    n2 = 10*d + e
                    prod = n1 * n2
                    # Test if prod uses up the remaining digits:
                    if sorted(list(str(prod))) == sorted([str(x) for x in remain5]):
                        print "%d x %d = %d" % (n1, n2, prod)

print "Total %d tries" % ntry

Answer 4

This is interesting. Here's a two-liner in R that finds the four solutions:

library(combinat)
for (x in unique(permn(c(1,1,2,3,3,4,5,6,6,7)))) if ((100*x[1]+10*x[2]+x[3]) * (10*x[4]+x[5]) == (10000*x[6]+1000*x[7]+100*x[8]+10*x[9]+x[10])) print(x)

Output:

[1] 6 1 7 4 3 2 6 5 3 1
[1] 6 6 7 2 3 1 5 3 4 1
[1] 6 3 7 2 3 1 4 6 5 1
[1] 6 5 3 3 7 2 4 1 6 1