wu :: forums « wu :: forums - Partitions » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 4:24pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: william wu, Icarus, Grimbal, Eigenray, towr, SMQ)    Partitions « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Partitions  (Read 1356 times)
Pietro K.C.
Full Member

Gender:
Posts: 213
 Partitions   « on: Sep 14th, 2002, 8:13pm » Quote 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 )

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

Gender:
Posts: 341
 Re: NEW PUZZLE: PARTITIONS   « Reply #1 on: Oct 5th, 2002, 1:28pm » Quote 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

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

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

Gender:
Posts: 949
 Re: NEW PUZZLE: PARTITIONS   « Reply #3 on: Oct 7th, 2002, 11:47am » Quote 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

wowbagger
Uberpuzzler

Gender:
Posts: 727
 Re: NEW PUZZLE: PARTITIONS   « Reply #4 on: Oct 8th, 2002, 4:22am » Quote 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

James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: NEW PUZZLE: PARTITIONS   « Reply #5 on: Oct 8th, 2002, 11:34am » Quote 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

Pietro K.C.
Full Member

Gender:
Posts: 213
 Re: NEW PUZZLE: PARTITIONS   « Reply #6 on: Oct 8th, 2002, 11:50am » Quote 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.
 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

Gender:
Posts: 949
 Re: NEW PUZZLE: PARTITIONS   « Reply #7 on: Oct 8th, 2002, 12:52pm » Quote 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

James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: NEW PUZZLE: PARTITIONS   « Reply #8 on: Oct 9th, 2002, 6:28am » Quote 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

Pietro K.C.
Full Member

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

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

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.
 « 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »