wu :: forums
« wu :: forums - Partitions »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 4:50am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Eigenray, Icarus, Grimbal, william wu, SMQ, towr)
   Partitions
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Partitions  (Read 1365 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Partitions  
« on: Sep 14th, 2002, 8:13pm »
Quote Quote Modify Modify

  Given a natural number n, a partition P of n is a nondecreasing sequence (a1, ... , ak) of strictly positive integers such that the sum of its terms is n. For instance, the partitions of 4 are:
 
(1,1,1,1), (1,1,2), (1,3), (2,2), (4). (Hope I didn't forget any Smiley)
 
   Given a particular partition P of n, let A(P) be the number of 1's to appear in P, and let B(P) be the number of distinct elements of P. So A(1,1,1,1) = 4 and B(1,1,1,1) = 1. Prove that, for all n,
 
sum A(P) = sum B(P)
 
where the sum extends over all partitions of n. (For n = 4, both sums are equal to 7, for example)
« Last Edit: Nov 7th, 2002, 8:48am by Pietro K.C. » IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
NickH
Senior Riddler
****





   
WWW

Gender: male
Posts: 341
Re: NEW PUZZLE: PARTITIONS  
« Reply #1 on: Oct 5th, 2002, 1:28pm »
Quote Quote Modify Modify

This is a GREAT puzzle!
 
I'm attacking it using Ferrers diagrams?  Could this be a fruitful approach?
 
Nick
IP Logged

Nick's Mathematical Puzzles
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PUZZLE: PARTITIONS  
« Reply #2 on: Oct 5th, 2002, 3:34pm »
Quote Quote Modify Modify

  Well, finally someone shows some interest!!! Smiley I was beginning to think this problem was too boring for you guys.
 
   I'm not too sure how to solve it with Ferrers diagrams; my approach was different. Would you care to detail your method? And are there any non-obvious results about partitions that Ferrers diagrams give easy proofs to? I'm really not that familiar with them.
IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PUZZLE: PARTITIONS  
« Reply #3 on: Oct 7th, 2002, 11:47am »
Quote Quote Modify Modify

Here's a weird sort of proof. Image each partition as a series of stacks of square blocks. Here's a couple examples (using round blocks, which ironically don't stack in real life), for n = 13:
 
00
00
00
000
0000
5521 = "X"
 
0
00
00000
00000
43222 = "Y"
 
You can see that each series of stacks has a non-increasing property (each stack is at least as big as the next stack). You can also see that you can "rotate" each partition, to make a complementary partition. We'll say that complementary partition of X is X'.
 
Notice that Y=X' in the above diagrams.
 
Now notice that A(X) = B(X').
 
This inversion process is one-to-one, and the result can be the same as the initial partition only if A(X) = B(X).
 
Furthermore, if a partition X is included for a number n, then so is X'.
 
To sum up:
 
1) Take all the partitions P of n, and calculate sum A(P).
2) Now complement them all. You know that sum B(P') = sum A(P)
3) But the set P' is the same as the set P, so sum B(P) = sum A(P)
IP Logged

Doc, I'm addicted to advice! What should I do?
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: NEW PUZZLE: PARTITIONS  
« Reply #4 on: Oct 8th, 2002, 4:22am »
Quote Quote Modify Modify

on Oct 7th, 2002, 11:47am, James Fingas wrote:
You can also see that you can "rotate" each partition, to make a complementary partition. We'll say that complementary partition of X is X'.
 
Notice that Y=X' in the above diagrams.
 
Now notice that A(X) = B(X').

 
Maybe I misunderstand you or the definition of A or B, but isn't  A(X) = 1, B(X') = B(Y) = 3 ?
 
I think that A(X) is the difference between the largest and the second largest element in X'. Haven't had time yet to consider what B(X) maps to when you rotate X though.
IP Logged

"You're a jerk, <your surname>!"
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PUZZLE: PARTITIONS  
« Reply #5 on: Oct 8th, 2002, 11:34am »
Quote Quote Modify Modify

You're right. I posted that on too little sleep. If you consider C(P) = the largest element in the partition, and D(P) = the number of elements in the partition, then my proof is okay, but it doesn't have much to do with this question.
 
After thinking about the problem harder, I don't think there can be any proof as simple as this for A(P) and B(P).
IP Logged

Doc, I'm addicted to advice! What should I do?
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PUZZLE: PARTITIONS  
« Reply #6 on: Oct 8th, 2002, 11:50am »
Quote Quote Modify Modify

  The rotating idea is really good, even though it does not help much in this case. I'm sure it could help give a simple proof of a variety of results.
 
   I'm trying REALLY hard not to give hints on this one - I know just how hard it is not to read them. Smiley
IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PUZZLE: PARTITIONS  
« Reply #7 on: Oct 8th, 2002, 12:52pm »
Quote Quote Modify Modify

I have been examining the problem, and I have come to the conclusion that your solution is by induction on n. However, I don't yet know what the solution is.
 
The reason I say this is that the number of unique partitions as a function of n is: 1,2,3,5,7,11, ..., and the number of 1s as a function of n is: 1,2,4,7,12,19,30, .... You can see that the increase in the number of 1s is equal to the number of partitions.
 
This makes intuitive sense: when you increase n by one, you add 1s in only one way: by tacking a 1 on the end of every partition. Tacking a 1 on the end is a one-to-one modification. Now all I have to show is that the number of unique elements in the partitions grows in the same way.
« Last Edit: Oct 9th, 2002, 10:35am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PUZZLE: PARTITIONS  
« Reply #8 on: Oct 9th, 2002, 6:28am »
Quote Quote Modify Modify

I have finally solved the problem! It was pretty tough, so good work, Pietro!
 
I'm going to introduce some new notation:
 
An = sum of A(P) (over all unique partitions P of n)
Bn = sum of B(P) (over all unique partitions P of n)
Qn = the number of unique partitions of n (think 'quantity') (I could have picked N for this, but I decided not to)
 
The start of my solution came by examining how you actually take the inductive step from n to n+1.  
 
My first realization was that the partitions of n+1 aren't really very unique. In fact, all of these partitions share a lot in common with the partitions of n. Looking at this partition of 3,
 
0
00
21
 
It is similar to both of the partitions of 2:
 
0
0
2
 
00
11
 
All you do is add a single block (I'm still using those darned round blocks) to the partitions of 2, and you get a partition of 3. However, you can't add the block just willy-nilly--you must follow certain rules. Consider the following partition, P:
 
0
00
00
00000
00000
00000000
65333111
 
It consists of a series of "stair steps". You are only allowed to add new blocks on the inside corners of the stairsteps (I'll mark these locations with X)
 
X
0X
00
00X
00000
00000X
00000000X
65333111
 
If you add a block in any other place, you don't get a valid partition with n+1 blocks. Now I realized the following: the number of stairsteps in a partition P is equal to B(P). The number of blocks you can add is equal to B(P) + 1.
 
Now I looked at the problem in reverse. How do you go from n to n-1? You just take away blocks! You have to take them away from the outside corners of the stairsteps. I will now mark the blocks that you can take away with 'o'.
 
o
0o
00
0000o
00000
0000000o
 
You'll notice that you can take away exactly B(P) blocks.
 
Next, I tried to consider how many stair-steps you end up with, depending on which block you add or take away, but this problem is very complicated. Sometimes, adding a block adds a stairstep, but sometimes it doesn't, and sometimes it removes a stairstep. Looking at P above, you can see all these possibilities. Consideration of the partitions one at a time is very difficult.
 
However, you will notice that every block that you can add will become the outside corner of a stairstep. Therefore, for every possible transition from a partition of n to a partition of n+1, there is exactly one corresponding transition from a partition of n+1 back to the partition of n. When you sum up these possible transitions, you get:
 
sum (possibilities going forward from n) = sum (possibilities going backwards from n+1)
sumn (B(P) + 1) = sumn+1 (B(P))
Bn + Qn = Bn+1
 
But this is exactly what I wanted to prove! (see my last post) We know that:
 
An + Qn = An+1
 
And it is easy to see that:
 
A1 = B1
 
If we assume the inductive hypothesis, then the answer falls right out:
 
An = Bn
An + Qn = Bn + Qn
An+1 = Bn+1
 
QED
IP Logged

Doc, I'm addicted to advice! What should I do?
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PUZZLE: PARTITIONS  
« Reply #9 on: Oct 9th, 2002, 11:13am »
Quote Quote Modify Modify

  Well, good job! Such smart people on this forum! Smiley
 
   My proof was direct, with just some overtones of induction; the proof for n involves mention of n-1, but no induction hypothesis. It's good to see a different proof, especially one so ingenious! Mine is as follows.
 
   To keep things short, let S be the set of all partitions of n, and let Q(n) be as James's (i.e. Q(n) is the cardinality of S). Defining Q(0) = 1, the sum of A(P) over S is clearly equal to the sum of Q from 0 to n-1; because exactly Q(n-i) members of S have i 1's or more - they are of the form
 
(1, ... , 1, P(n-i)), where P(n-i) is any partition of n-i.
 
   So, when you sum the Q's, you count those P's in S with i 1's exactly i times, giving the previously stated result. This is the result that got me started, and, I thought, the easier to come up with first.
 
   Now, another way to look at the sum of B(P) over S is the following: count the number of partitions in which a number i appears, and sum those results over i. With that in mind, it is easily seen that i appears in Q(n-i) partitions; because, if
 
a1 + ... + i + ... + ak = n,
 
then
 
a1 + ... + ak = n-i,
 
and vice-versa.
 
   The degenerate case i = n is taken care of by our previous definition of Q(0). Hence, the sum of B(P) over S is also equal to the sum of Q from 0 to n-1, and we have
 
sum A(P) = sum B(P).
 
Quod erat demonstrandum. Smiley
« Last Edit: Oct 9th, 2002, 11:20am by Pietro K.C. » IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board