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)
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    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Two proposed proofs | Comment 2 of 4 |
Starting with the innermost multiplication, when expanded it produces a*b terms at most, where a and b are the numbers of terms in the two multiplicands, to be added to the number of terms in the rest of the innermost parentheses. Do this separately for each innermost (or locally innermost) multiplication and then addition. You will eventually stop.

Alternative proof:

The most terms you could have at the end is 2^n, where n is the number of letters. In the first, unexpanded, example given, n = 6. When already partially expanded, as in the second expression given n is larger, as we count each occurrence of a given letter (to account for the ultimate possibility of square, cube, etc. factors) and thus 2^n is larger, but we know that it's still true that in this case the number of terms must still be 2 to the original n or less, as that is a tighter restriction on what the number of terms can be. In any case it is finite.

Actually it's always less than 2^n if we also count constants in the count of "variables", as no term will lack all of these pieces.

So we predicted less than 64:

xsu+xsv+xt + ysu+ysv+yt

Just 6 terms--indeed less than 64.

  Posted by Charlie on 2017-04-13 10:03:35
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information