Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
voider

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)

Share this post


Link to post
Share on other sites

7 answers to this question

Recommended Posts

  • 0
Guest

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 this post


Link to post
Share on other sites
  • 0

When voider said one variable, I think he meant ANY one variable (a or b or c ... or g) to make 7 unique expressions. Counting the negatives would turn that into 14.

Share this post


Link to post
Share on other sites
  • 0
Guest

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 this post


Link to post
Share on other sites
  • 0
Guest

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 this post


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

Share this post


Link to post
Share on other sites
  • 0
Guest

Assuming that all variables are nonzero,there should be 84 not 133 possible operations with 2 variables

7C2*4=84

Share this post


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

Share this post


Link to post
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...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...