Take the 2-minute tour ×
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.

Given a set of numbers (in this case):

3, 7, 7, 100, 50

Either:

prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + 7) * 100)

or

find the expression that does form the number k = 190.

I am not sure how to work on this problem analytically as the general case of any subset and any number k appears to be an NP Hard problem.

I wish to brute force the solution for this. Is the following algorithm sufficient:

Take set F: Compute all possible ordered subsets of F (How to do this elegantly?)

Compute all possible combinations of operators between each ordered subset...

If any equal 190 then the problem is solved, if none equal 190 then clearly its not possible.

How do I generally design this algorithm? Is there a better way to solve this problem (preferably without brute force)?

My attempt at analytics:

I wanted to see if by working with the number modulo Q it would be easy to filter out which possible expressions may evaluate to 190. Since the expression S = 190 must be true mod Q for all Q if it is true.

My other attempt at brute force:

Starting from 190, systematically, add, subtract, divide, etc... expressions from the original set in the hope that one of these expressional chains concludes in a value that is still present in the set. This seems to be as computationally expensive as the previous method (How would I implement this?)

share|improve this question
    
Are repetitions allowed: For example $100/100 = 1$ and $190 = 1 + 1 + \dots + 1 $? –  hot_queen May 2 '13 at 22:44
    
Only elements from the set used once, if there are 3 5's u can use 5 up to 3 times –  frogeyedpeas May 2 '13 at 23:20
2  
I think this might be what you're looking for: sysexpand.com/?path=exercises/expression-from-numbers –  Jebdm Jan 11 at 7:16

1 Answer 1

up vote 2 down vote accepted

I saw this riddle somewhere before, and I think it should be numbers 3 7 7 8 50 100 given (you probably missed number 8), and then the solution for this is:

( 50 - 8 ) * 7 - 100 - 7 + 3 = 190

:)

share|improve this answer

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.