All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Growth Potential (Posted on 2017-04-13) Difficulty: 4 of 5
Suppose you’re working on an algebraic expression that involves variables, addition, multiplication, and parentheses. You try repeatedly to expand it using the distributive law.

How do you know that the expression won’t continue to expand forever?

For example, expanding
(x + y)(s(u + v) + t)
gives
x(s(u + v) + t) + y(s(u + v) + t),
which has more parentheses than the original expression.

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Yet another proof | Comment 3 of 4 |
For any expression, construct an array of counts where the nth element (counting from the RIGHT) counts the number of products with exactly n parentheticals in the expression. For the example given, that looks like: [1, 1] -- s(u+v) is a product with 1 parenthetical, and (x+y)( stuff ) is a product with 2 parentheticals.

An example like (x+y)(a+b)(c + d(e+f)) would have an array like [1,0,1] in the same way.

If I pick any case where I can apply the distributive property and do so, I decrease one element of the array, and then increase the next lower element by twice however many added terms are in the second term less one. In the example given, when we go from (x+y)(s(u+v) + t) to x(s(u+v)+t) + y(s(u+v) + t) then the array goes from [1,1] to [0,4], increasing the next term by 3 because s(u+v)+t has two terms. [The exact size of the increase is irrelevent, only the fact that the increase is to the next lower term matters.]

If instead we had expanded s(u+v) first, we'd have (x+y)(su + sv + t) and the array would become [1,0]. If there is no "next lower element" then nothing increases from the operation.

Let's define "less than" in the context of comparing arrays so that a < b if in the first element left to right where a and b differ then a's element < b's element. (you might also imagine the array as digits in a Base-N number where N is something larger than the maximum count, which would give the same meaning to "less than".

The key then is to see that no matter which place we choose to apply the distributive property, the change to the array results in a strictly smaller array. Since each operation reduces the array, and since when there are no parentheticals at all the array is all zeros, after a finite number of operations the array must reach all zeros and there must be an end to the expansion.


  Posted by Paul on 2017-04-13 12:25:16
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (15)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information