Bloggers Wanted
We're looking for people to help with the main blog. If you are consistent, knowledgeable and you're into it, please drop me a note.
|
|
|
|
|
richmondphil
 Senior Boarder
Posts: 63 
|
|
4 can be expressed by these 8 sums of positive integers: 4, 1+3, 2+2, 3+1, 1+1+2, 1+2+1, 2+1+1, 1+1+1+1. How would you prove that a positive integer N can be expressed by 2^(N-1) sums of positive integers?
|
|
The administrator has disabled public write access. |
JohnBStone
 Senior Boarder
Posts: 70
|
|
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
When the sums are counted in this way, they are equivalent to taking N ones and grouping them together to form the numbers to be added. For example, 1+3 means 1+(1+1+1). By inventing a symbol $ for a high- precedence addition (addition within each group), we can write this as 1+1$1$1. Between the N ones, there are N-1 places where we can write a + or a $. That gives 2^(N-1) choices. QED.
|
|
The administrator has disabled public write access. |
querty
Senior Boarder
Posts: 73
|
|
try it after eliminating the 'duplicates', by which i mean 1+2+1 is really
not different than 1+1+2 or 2+1+1.
google 'partitions math', s'interesting stuff.
|
|
The administrator has disabled public write access. |
ciproantib
Senior Boarder
Posts: 71
|
|
haha! indeed. i'm thankful i could remember 'partitions'. getting older.
|
|
The administrator has disabled public write access. |
JohnC
Senior Boarder
Posts: 65
|
|
SPOILER
Let N equal, say, 8. Lay 8 blocks on a table in a straight line, spaced a couple of inches apart. Place a small light bulb between each pair of blocks. Each bulb may be on or off.
Start at one end and count the number of blocks before the first lit bulb. Then count the number of blocks before the next lit bulb, etc. For example:
X X X o X o X X X X X (o=on)
yields 3+1+4 as one way of adding to 8.
There are 2^7 different ways of lighting the bulbs.
Bill Ryan
|
|
The administrator has disabled public write access. |
|
|
|
