19
$\begingroup$

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$$

$\endgroup$
0

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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...

$\endgroup$
2
  • $\begingroup$ I have a question about your first estimate of 6570 possibilities. Won't this require further evaluation since not every product will consist of digits found in the list? So our choices on the left are intricately related to the possibilities/choices on the right. $\endgroup$ Commented Mar 10, 2016 at 20:40
  • $\begingroup$ Of course. The $6570$ is the number of ways to take $5$ of the $10$ possible digits and assign them to the $5$ positions on the left side of the equation. If they were $10$ distinct digits, it would be $10!/5! = 30240$, but since some of the digits appear twice that cuts down on the number of possibilities. $\endgroup$ Commented Mar 11, 2016 at 0:00
1
$\begingroup$

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
$\endgroup$
0
0
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ If the questioner feels an answer is inappropriate, then they can inform the answerer. $\endgroup$ Commented Mar 17, 2016 at 0:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .