Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
    
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. – ThisIsNotAnId Mar 10 at 20:40
    
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. – Robert Israel Mar 11 at 0:00

Even if we restrict ourselves to legal combinations of lowest-order digits, it would be extremely tedious to write out the possible ways to place digits into the left side of the equation. Coding this up in Python executes in under 0.1 second and yields 2304 possibilities. (Note the overhead hiding in the repeated list copying, list and set manipulation, conversion to character, sorting...)

# 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
share|cite|improve this answer
    
You might want to reread the question better. The author was asking for a math based logic solution. He only mentioned the code to point out how insane it was that a grade school teacher put it in homework. Nice code though. :) – TheGreatDuck Apr 11 at 18:30

I can immediately determine that 4, 5, and 7 cannot be the one's digit of the right hand side due to their factors not existing for the left. I can also see that 5 is an illegal number for the left side. Basically assume that the problem starts with three single digit numbers. Then, have one single digit number times a two digit number (the one digit possibilities will be the possible one's places) and then so on and so on. From what I can tell there are the following possible combinations of one digit multiplications:

1 * 3 = 3

1 * 6 = 6

2 * 3 = 6

2 * 7 = 14

3 * 4 = 12

3 * 7 = 21

6 * 7 = 42

Some of these have carry over to juggle, but in general, this narrows down your possibilities.

There is also another approach that is based upon a principle of polynomial a that many do not catch. Polynomials are actually numbers in base X. This is important as we can use this to rewrite multiplication.

(100a + 10b + c)(10d + e) = (10000f + 1000g + 100h + 10j + k)

So:

1000ad + 100ae + 100bd + 10be + ce = 10000f 1000g + 10j + k

I believe using something akin to the calculus method for partial fraction decomposition you can solve the algebra by comparing specific digits. At the very least this will help you be allowing you to fill in digits as you go and see what is still possible. After all:

ce % 10 = k Where % means the remainder of a when divided by b.

share|cite|improve this answer
    
I think you overlooked 2*7=14. (Overall, this looks similar to the approach in Michael Harrison's answer.) – Barry Cipra Mar 15 at 18:31
    
No, his was completely different. He was doing intense modulo arithmetic. I'm jut using logic in general to ask "what possibilities can exist" and then working up. – TheGreatDuck Mar 15 at 18:44
    
I was mainly referring to Harrison's observation on the number of possible triples for the ones digits, which is how I noticed you had overlooked a case. – Barry Cipra Mar 15 at 18:59

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
share|cite|improve this answer
    
This question is asking for a Mathematica solution NOT a programming solution. Please attempt to answer the question using the method specifying or delete your answer. – TheGreatDuck Mar 16 at 18:49
    
If the questioner feels an answer is inappropriate, then they can inform the answerer. – Eric Stucky Mar 17 at 0:08
    
Why do I always get the weird feeling that you are following me around this site, and also there is nothing wrong with me informing the answerer that their answer failed to answer the question properly. I see nothing anywhere that says the asker has exclusive privileges as to what doesn't answer the question. If this is a correc answer it also certainly does not belong on MSE (where questions and answers are based around math, not programming) so I don't see any reason why I cannot kindly tell the person to revise their answer? People do this all the time on here. There's nothing wrong with it – TheGreatDuck Mar 31 at 18:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.