Can anyone tell me what mathematical trick is hidden in the problem?

Question

By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition.

For example, if 100 is given, you would answer 7.

The reason is that there are 7 possible ways.

100 = 1*2*3*4+5+6+7*8+9

100 = 1*2*3+4+5+6+7+8*9

100 = 1+2+3+4+5+6+7+8*9

100 = 12+3*4+5+6+7*8+9

100 = 1+2*3+4+5+67+8+9

100 = 1*2+34+5+6*7+8+9

100 = 12+34+5*6+7+8+9

If this question is given to you, how would you start?

Answer 1

Write out the string "123456789". Between each number you can either (1) do nothing, (2) put a "+", or (3) put a "*". So we have 3 choices between each number.

This leaves $3^{9-1} = 3^8 = 6561$ possible strings to evaluate.

Of course, some strings can be eliminated (for example, you can't have two "do nothings" in a row -- the smallest number such a choice yields is "123" - already too big). But honestly, I think you're going to be stuck implementing some sort of computer program to run through the hundreds of cases to see when you actually get "100".

On one hand, addition and multiplication are simple operations. On the other hand, the study of interactions between addition and multiplication make up a rather difficult branch of mathematics (i.e. number theory).

I don't think this problem has an easy "do it by hand" way out.

Answer 2

As mentioned by Bill, total number of expressions is 6561 which is far too much to be checked manually, but relatively quickly can be managed e.g. in Excel using brute force:

• Set first 17 columns for the numbers and operands:
  • Formula in odd columns for numbers:
    =ROUND(COLUMN()/2,0)
  • Formula in even columns for operands
    =CHOOSE(MOD(ROUNDDOWN((ROW()-2)/3^(COLUMN()/2-1),0),3)+1,"+","*","")
• Column R (18th) will display the expression:
  =CONCATENATE(A2,B2,C2,D2,E2,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2)
• Column S will show the result, as there is no built-in function to calculate value of column R, I've used below VBA code for it.
  =EvaluateUDF(R2)

Now just need to populate formulas down to row 6562 which can be done quickly with a bit of playing with the mouse of PageDown. And finally filter for any results your are interested in, or sort and group them in a pivot table.

The VBA code:

Function EvaluateUDF(exp as Variant)
  EvaluateUDF=Application.Evaluate(CStr(exp))
End Function