Jump to content
BrainDen.com - Brain Teasers
  • 0


voider
 Share

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)

Link to comment
Share on other sites

7 answers to this question

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.

Link to comment
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
Link to comment
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?

Link to comment
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.

I have an answer now.

Link to comment
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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...