2
$\begingroup$

$a,b,c,d,e,f,g,h,i$ are real numbers and you would like to calculate the equation below by adding as many paranteses as you want:

a-b^c-d/e+f/g^h*i

What is the maximum amount of different results you can get by adding parantheses?

Note: Programming result is acceptable since you share the code and all possible different equations in terms of the letters rather than some garbage real number values.

$\endgroup$
  • $\begingroup$ real numbers as in, they can be anything? Or they should be the same during all the cases where parentheses are added? $\endgroup$ – Marius Apr 26 '17 at 10:57
  • $\begingroup$ @marius you are gonna choose any real number for each letter. no change in values for each letter in the middle of the calculations of course and you cannot change their location either, just adding parantheses. $\endgroup$ – Oray Apr 26 '17 at 11:01
  • $\begingroup$ Am I missing something? I posted an answer that I think is correct, but it seems too trivial. $\endgroup$ – Trenin Apr 26 '17 at 11:55
4
$\begingroup$

I might be wrong, but doen't this relate closely to

Catalan-numbers?

Just look at

the second comment on OEIS:
Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

So the final answer is

$C_9=1430$

There is an important detail left to be shown:

Does every different grouping actually lead to different results?
There are three things to consider here:

1) As there is only one addition and one multiplication, different groupings will give different results if the numbers are well chosen. Otherwise (x+y)+z=x+(y+z) or (xy)z=x(yz) would apply: different parenthesisation would lead to the same result no matter how we choose the numbers.

2) It is also necessary there are no subtractions after the addition and no divisions after the multiplication. Otherwise x+(y-z)=(x+y)-z or x*(y/z)=(x*y)/z would apply, causing different parenthesizations leading to the same results.

3) We also have to take care of every interpretation being valid: that is no zeros in the denominators of the fractions, and at the exponentiations no negative bases with non-integer exponents. Although I don't go into all the details, I'm convinced this can be granted easily.

$\endgroup$
  • $\begingroup$ This is the upper bound. For example, $(a-b)^c-d/e$ is the same as $((a-b)^c-d/e)$ and $((a-b)^c-(d/e))$ $\endgroup$ – Oray Apr 26 '17 at 12:55
  • 1
    $\begingroup$ I cannot see that is a problem. Those all are the same grouping of (((ab)c)(de)), aren't they? You just erased some unnecessary parentheses from the very same expression of $(((a-b)^c)-(d/e))$, I mean. $\endgroup$ – elias Apr 26 '17 at 12:58
  • $\begingroup$ ok let say I ask the same question without only + and -'s. Your answer would be still 1430 different results? or if I asked with only * and /... $\endgroup$ – Oray Apr 26 '17 at 13:07
  • $\begingroup$ For the record, I wrote a program that performed my answer and then sorted the results and removed duplicates. I ended up with this answer as well. $\endgroup$ – Trenin Apr 26 '17 at 13:08
  • 1
    $\begingroup$ You can simplify the current expression to $a-X-Y+Z$, but all parenthesizations of this expression are different I think. $\endgroup$ – Trenin Apr 26 '17 at 13:15
2
$\begingroup$

Edit: This is an oversimplification which is proven to be too high in the comments. I'll leave it here, but note it is not the correct answer.

There are 9 variables and 8 operators. Lets define a system where we choose a pair of adjacent variables and apply the operator between them. The result is another real number, which you can then put back into the equation, leaving you with one less variable and one less operation, on which you can apply your system again recursively.

Using that system, if you have $n+1$ variables with $n$ operations, you will basically go through $n$ rounds before you come up with an answer. In the first round, you have $n$ choices for the adjacent variables. In the second round, you will have $n-1$ choices, and so on.

So, the total number of choices is defined by $T_0=1$ and $T_n = n \times T_{n-1}$ where $n$ is the number of operators.

Thus, the theoretical maximum answer is a simple

$T_n= n\times (n-1) \times (n-2) ... \times 2 \times 1 = n!$

So, in this case, there are

$T_8 = 8! = 40320$ possible results

If we choose

irrational, unrelated numbers

for each variable, we should be able to achieve all of these results. The only real trick is

ensure $a \gt b$ because the expression 'c-d/e+f/g^h*i' can be negative and if $a \lt b$, then $a-b$ is negative, and the entire expression will have an imaginary component.

$\endgroup$
  • $\begingroup$ I disagree. This only gives an upper bound. For example, there are no differences between the following two orders: 1. starting with b^c and then g^h and then the rest from let's say left-to-right; 2. starting with g^h, then b^c, and then the rest again. $\endgroup$ – elias Apr 26 '17 at 12:06
  • $\begingroup$ @elias You are right - I thought I oversimplified and must be missing something! $\endgroup$ – Trenin Apr 26 '17 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.