VCE Stuff > VCE Mathematics

partition

(1/2) > >>

/0:
Find the number of ways in which 100 can be divided into a sum of 2s, 3s or 4s. :coolsmiley:

thanxxx

kamil9876:
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 :

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

Therefore the values 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:




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

because ranges from 1 to 16. there are 16 terms alltogether and hence 8 terms in each sum. So the sum is:




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


edit: 200 posts :D:D

/0:
very nice solution kamil :D

it seems like you're always in an inspired mood

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

/0:
aaah i know it has something to do with the pigeonhole principle but i don't know how to apply it lol

Navigation

[0] Message Index

[#] Next page