wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Partitions
        
(Message started by: Pietro K.C. on Sep 14^th, 2002, 8:13pm)

Title: Partitions
Post by Pietro K.C. on Sep 14^th, 2002, 8:13pm

Given a natural number n, a partition P of n is a nondecreasing sequence (a₁, ... , a_k) 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 :))

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)

Title: Re: NEW PUZZLE: PARTITIONS
Post by NickH on Oct 5^th, 2002, 1:28pm

This is a GREAT puzzle!

I'm attacking it using Ferrers diagrams? Could this be a fruitful approach?

Nick

Title: Re: NEW PUZZLE: PARTITIONS
Post by Pietro K.C. on Oct 5^th, 2002, 3:34pm

Well, finally someone shows some interest!!! :) 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.

Title: Re: NEW PUZZLE: PARTITIONS
Post by James Fingas on Oct 7^th, 2002, 11:47am

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)

Title: Re: NEW PUZZLE: PARTITIONS
Post by wowbagger on Oct 8^th, 2002, 4:22am

on 10/07/02 at 11:47:30, 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.

Title: Re: NEW PUZZLE: PARTITIONS
Post by James Fingas on Oct 8^th, 2002, 11:34am

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).

Title: Re: NEW PUZZLE: PARTITIONS
Post by Pietro K.C. on Oct 8^th, 2002, 11:50am

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. :)

Title: Re: NEW PUZZLE: PARTITIONS
Post by James Fingas on Oct 8^th, 2002, 12:52pm

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.

Title: Re: NEW PUZZLE: PARTITIONS
Post by James Fingas on Oct 9^th, 2002, 6:28am

I have finally solved the problem! It was pretty tough, so good work, Pietro!

I'm going to introduce some new notation:

A_n = sum of A(P) (over all unique partitions P of n)
B_n = sum of B(P) (over all unique partitions P of n)
Q_n = 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)
sum_n (B(P) + 1) = sum_n+1 (B(P))
B_n + Q_n = B_n+1

But this is exactly what I wanted to prove! (see my last post) We know that:

A_n + Q_n = A_n+1

And it is easy to see that:

A₁ = B₁

If we assume the inductive hypothesis, then the answer falls right out:

A_n = B_n
A_n + Q_n = B_n + Q_n
A_n+1 = B_n+1

QED

Title: Re: NEW PUZZLE: PARTITIONS
Post by Pietro K.C. on Oct 9^th, 2002, 11:13am

Well, good job! Such smart people on this forum! :)

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

a₁ + ... + i + ... + a_k = n,

then

a₁ + ... + a_k = 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. :)