BrainDen.com - Brain Teasers

Question

If you have 7 integer variables, e.g. a, b, c, d, e, f, g, and you can use each at most once in an expression with the operators +, -, *, / (integer division), how many unique expressions can be formed?

E.g. (a - b) * c + f is mathematically the same as:

c * (a - b) + f

f + (a - b) * c

f + c * (a - b)

so they all correspond to a single unique expression.

If there was one variable, there are 7 unique expressions.

With two variables, I think there are 133 unique expressions.

I don't know the answer (yet), and I very much doubt anyone can find a closed form formula for the general problem. About the context where this problem originated, I suspect it was intended to be virtually unsolvable... (and deceptively mediocre-looking)

Recommended Posts

• 0 with one variable, i only get 2 unique expressions with those operators. a and -a.

i would be interested to see how you get 133, with 2.

the only ones i see are...

a +b

a -b

a *b

a /b

-a +b

-(a +b)

-a*b

-a/b

anything else is essentially the same operation.

Share on other sites
• 0 with one variable, i only get 2 unique expressions with those operators. a and -a.

i would be interested to see how you get 133, with 2.

the only ones i see are...

a +b

a -b

a *b

a /b

-a +b

-(a +b)

-a*b

-a/b

anything else is essentially the same operation.

If I understand the problem, then you need to add four more to your list for 2 variables:

a

b

-a

-b

voider said "....you can use each at most once..."

Edited by thoughtfulfellow

Share on other sites
• 0 I don't think you can count a AND -a as two expressions. If it is a unique integer variable, then using it's negative creates a new value all together. ie, you can't say that 7 and -7 are the same integer. And I don't think using "-" as an argument of an operator is valid either?

Share on other sites
• 0

Clarification:

The operators are binary.

If there was one variable...

With two variables...

I was not clear on this.

What I meant was, still assuming there are 7 variables:

The number of expressions with exactly one variable is 7: a, b, c, d, e, f, g

The number of expressions with two or less variables (i.e. including the 7) is 133: a, b, c, d, e, f, g, a + b, a - b, a * b, a / b, ..., f / g, ... g / a.

Share on other sites
• 0 Assuming that all variables are nonzero,there should be 84 not 133 possible operations with 2 variables

7C2*4=84

Share on other sites
• 0

133 is correct, = 7C2 * 6 + 7

37766040

There are several subproblems that have to be combined optimally:

1. Iterating through order 4^6 operator combinations

2. Iterating through order 2^10 postfix expressions

3. Iterating through order 7! variable combinations

While this method is faster than brute force it is still very slow. If anyone finds an optimization based on a revelational observation that changes the need to "try almost everything" please let me know.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×