ATAR Notes: Forum

VCE Stuff => VCE Mathematics/Science/Technology => VCE Subjects + Help => VCE Mathematics => Topic started by: /0 on May 19, 2009, 11:52:26 am

Title: partition
Post by: /0 on May 19, 2009, 11:52:26 am: Find the number of ways in which 100 can be divided into a sum of 2s, 3s or 4s. :coolsmiley:

thanxxx
Title: Re: partition
Post by: kamil9876 on May 19, 2009, 12:55:45 pm: wow someone's in an inspired mood ;p

Solution:

So we want solutions to 3a+2b+4c=100.

Let's focus on the simple case when a=0. 100=50*2 hence there are 26 different ammounts of four that can fit here. (4*0,4*1...4*25)

when $a \neq 0$ :

3a=100-2b-4c
3a=2(50-b-2c) hence a must by even.

Therefore the values $\frac{a}{2}$ are only between 1 and 16 inclusive. Let's analyse each case in a descending order:

let 100-3a=x

The possible x values are hence 4,4+6,4+6*2.... 4+6*16. Next to each we will write down how many four's fit there.

4 - 0 or 1- 2 four's
10 - 0,1,2 - 3 four's
16 - 0,1,2,3,4 - 5 four's
22 - 0,1,2,3,4,5 - 6 four's
28 - 0,1,2,3,4,5,6,7 - 8 four's
.
.
.

You can see that the pattern is that the difference between consecutive count's of four is such: first is we jump by 1, then by 2, then by 1.. then by 2 again etc. (this can be easily proven, but i will skip it as my post is long enough, ill explain in a later post)

hence the total sum is:

$2+3+5+6+8+9+11...$
$=(2+5+8+11...)+(3+6+9+12...)$

So it is the sum of two arithmetic sequences, now all we need is the last term:

because $\frac{a}{2}$ ranges from 1 to 16. there are 16 terms alltogether and hence 8 terms in each sum. So the sum is:

$(2+5+8..+2+3(7))+(3+6...3+3(7))$
$=(2+5+8...23)+(3+6+9...24)$

Basically add that sum to 26 (the thing we found when a=0)

edit: 200 posts :D:D
Title: Re: partition
Post by: /0 on May 19, 2009, 05:39:32 pm: very nice solution kamil :D

it seems like you're always in an inspired mood
Title: Re: partition
Post by: kamil9876 on May 19, 2009, 05:40:27 pm: bahaha i was referring to you since you've been making some interesting posts today :P

Btw here is a problem whose solution required some inspiration:

Given a set of any 2009 integers, prove that there (always) exists at least one subset which will sum up to a multiple of 2009.

For example: the set of the first 2009 prime numbers, i.e.
{2, 3, 5, 7, ... , 17467, 17471}

has the subset {5, 4013} which sums to 4018 = 2 * 2009.

Sauce: melbourne uni maths society(MUMS)
Title: Re: partition
Post by: /0 on May 21, 2009, 11:24:51 am: aaah i know it has something to do with the pigeonhole principle but i don't know how to apply it lol
Title: Re: partition
Post by: kamil9876 on May 21, 2009, 08:12:54 pm: whoa where did that insight come from? :P