Another week, another riddler. This one is from math professor Jim Propp:
When you write lengthy mathematical expressions using parentheses, it’s always clear which “open” parenthesis corresponds to which “close” parenthesis. For example, in the expression (1+2(3−4)+5), the closing parenthesis after the 4 pairs with the opening parenthesis before the 3, and not with the opening parenthesis before the 1.
But pairings of other mathematical symbols can be more ambiguous. Take the absolute value symbols in Jim’s example, which are vertical bars, regardless of whether they mark the opening or closing of the absolute value. As Jim points out, |−1|−2|−3| has two possible interpretations:
- The two left bars are a pair and the two right bars are a pair. In this case, we have 1−2·3 = 1−6 = −5.
- The two outer bars are a pair and the two inner bars are a pair. In this case, we have |−1·2−3| = |−2−3| = |−5| = 5.
Of course, if we gave each pair of bars a different height (as is done in mathematical typesetting), this wouldn’t be an issue. But for the purposes of this problem, assume the bars are indistinguishable.
How many different values can the expression |−1|−2|−3|−4|−5|−6|−7|−8|−9| have?
This problem was solved by finding all the ways brackets can exist then narrowing it down based on if it lead to something valid. The method for narrowing it down were:
- at any point there have to be the same or more open brackets than closed brackets
- at the end there have to be as many open brackets as closed brackets
Using this and Pythons “eval” function we can find the number of solutions: 39
And I did a minor extension! If we take the the index to be the integers from -1 to -2*(i)-1 (so the inputs are |-1|, |-1|-2|-3|, |-1|-2|-3|-4|-5|, etc) and find the number of unique solutions we get the following series:
This is a unique solution in the OEIS that I was able to get accepted. Fun!