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

 Power partition procedure (Posted on 2017-03-26)
Number 3 can be expressed as the sum of one or more positive integers in 4 distinct ways:
3; 2 + 1; 1 + 2; 1 + 1 + 1
Number 4 can be expressed as the sum of one or more positive integers in 8 distinct ways:
4; 3 + 1; 1+3; 2 + 2; 2 + 1 + 1; 1+2+1; 1+1+2; 1+1+1+1
Prove : any positive integer n can be so expressed in 2n - 1 ways.

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 3rd solution - elegance | Comment 4 of 5 |
Imagine n 1's in a row.  There are n-1 spaces between them.  In each space either combine or separate.  There are 2^(n-1) ways to choose.

For example with n=5
+ means combine
| means separate

1+1+1+1+1 becomes 5
1+1+1+1|1 becomes 4+1
1+1+1|1+1 becomes 3+2
1+1+1|1|1 becomes 3+1+1
...
1|1|1|1|1 becomes 1+1+1+1+1

 Posted by Jer on 2017-03-26 21:31:02

 Search: Search body:
Forums (0)