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

Home > Numbers
Power partition procedure (Posted on 2017-03-26) Difficulty: 3 of 5
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.)
Solution One solution | Comment 1 of 5
The problem can be thought of as combinations.  Row n of Pascal's Triangle sums to 2^n.  The ways of expressing n as a sum correspond to row n-1.

I'll demonstrate with n=5

There's 1 way to use one number 4C4=1
5

There are 4 ways to use two numbers.  Each number has to be at least 1, you choose where to put the other 3.  4C3=4
4+1
3+2
2+3
1+4

There are 6 ways to use three numbers.  Each number has to be at least 1, you choose where to put the other 2.  4C2=6
3+1+1
2+2+1
2+1+2
1+3+1
1+2+2
1+1+3

There are 4 ways to use four numbers.  Each number has to be at least 1, you choose where to put the extra 1.  4C1=4
2+1+1+1
1+2+1+1
1+1+2+1
1+1+1+2

There is 1 ways to use 5 numbers.  There is nothing extra to place.  4C0=1
1+1+1+1+1

  Posted by Jer on 2017-03-26 14:26:21
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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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