2003 Combination Sum

Probability Level 4

( 2003 1 ) + ( 2003 4 ) + ( 2003 7 ) + … + ( 2003 2002 ) = k ( 2 2002 − 1 ) \large\dbinom{2003}1+\dbinom{2003}4+\dbinom{2003}7+\ldots+\dbinom{2003}{2002}=k(2^{2002}-1)

If the value of k k can be represented by a b \dfrac{a}{b} when a a and b b are coprime positive integers, find a + b a+b .


The answer is 5.

Ikkyu San by Ikkyu San , 23, Thailand

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Kerry Soderdahl
Aug 30, 2015

L e t S = ( 2003 1 ) + ( 2003 4 ) + ( 2003 7 ) + … + ( 2003 2002 ) \mathrm{Let\ } S={{2003}\choose{1}}+{{2003}\choose{4}}+{{2003}\choose{7}}+\ldots+{{2003}\choose{2002}}

By Pascal's rule:

= [ ( 2002 0 ) + ( 2002 1 ) ] + [ ( 2002 3 ) + ( 2002 4 ) ] + … =\left[{{2002}\choose{0}}+{{2002}\choose{1}}\right]+\left[{{2002}\choose{3}}+{{2002}\choose{4}}\right]+\ldots

… + [ ( 2002 6 ) + ( 2002 7 ) ] + … + [ ( 2002 2001 ) + ( 2002 2002 ) ] \ldots+\left[{{2002}\choose{6}}+{{2002}\choose{7}}\right]+\ldots+\left[{{2002}\choose{2001}}+{{2002}\choose{2002}}\right]

Again, by Pascal's rule:

= [ 2 ( 2001 0 ) + ( 2001 1 ) ] + [ ( 2001 2 ) + 2 ( 2001 3 ) + ( 2001 4 ) ] + … =\left[2{{2001}\choose{0}}+{{2001}\choose{1}}\right]+\left[{{2001}\choose{2}}+2{{2001}\choose{3}}+{{2001}\choose{4}}\right]+\ldots

… + [ ( 2001 5 ) + 2 ( 2001 6 ) + ( 2001 7 ) ] + … + [ ( 2001 2000 ) + 2 ( 2001 2001 ) ] \ldots+\left[{{2001}\choose{5}}+2{{2001}\choose{6}}+{{2001}\choose{7}}\right]+\ldots+\left[{{2001}\choose{2000}}+2{{2001}\choose{2001}}\right]

We observe that ∑ k = 0 j ( j k ) = 2 j \sum_{k=0}^j{{j}\choose{k}}=2^j

Subtracting from above:

S − 2 2001 = ( 2001 0 ) + ( 2001 3 ) + ( 2001 6 ) + … + ( 2001 2001 ) S-2^{2001}={{2001}\choose{0}}+{{2001}\choose{3}}+{{2001}\choose{6}}+\ldots+{{2001}\choose{2001}}

We may repeat the above procedure:

S − 2 2001 − 2 1999 = ( 1999 2 ) + ( 1999 5 ) + ( 1999 8 ) + … + ( 1999 1997 ) S-2^{2001}-2^{1999}={{1999}\choose{2}}+{{1999}\choose{5}}+{{1999}\choose{8}}+\ldots+{{1999}\choose{1997}}

After many repetitions:

S − 2 2001 − 2 1999 − 2 1997 − … − 2 1 = 0 S-2^{2001}-2^{1999}-2^{1997}-\ldots-2^1=0

S = 2 1 + 2 3 + 2 5 + … + 2 1999 + 2 2001 S=2^1+2^3+2^5+\ldots+2^{1999}+2^{2001}

1 2 S = 2 0 + 2 2 + 2 4 + … + + 2 1998 + 2 2000 \frac{1}{2}S=2^0+2^2+2^4+\ldots++2^{1998}+2^{2000}

S + 1 2 S = 3 2 S = 2 0 + 2 1 + 2 2 + 2 3 + … + 2 2000 + 2 2001 S+\frac{1}{2}S=\frac{3}{2}S=2^0+2^1+2^2+2^3+\ldots+2^{2000}+2^{2001}

2 ( 3 2 S ) = 3 S = 2 1 + 2 2 + 2 3 + 2 4 + … + 2 2001 + 2 2002 2\left(\frac{3}{2}S\right)=3S=2^1+2^2+2^3+2^4+\ldots+2^{2001}+2^{2002}

3 S − 3 2 S = 3 2 S = 2 2002 − 2 0 3S-\frac{3}{2}S=\frac{3}{2}S=2^{2002}-2^0

S = 2 3 ( 2 2002 − 1 ) = k ( 2 2002 − 1 ) S=\frac{2}{3}(2^{2002}-1)=k(2^{2002}-1)

k = 2 3 k=\frac{2}{3}

2 + 3 = 5 2+3=\boxed{5}

6 Helpful 0 Interesting 0 Brilliant 0 Confused

I used B.E (1+x)^n = sum(i=0 to n) nCi * x^i ; and then substituted 1, w, w^2 in the equation and added them. This gave me nC0 + nC3 + nC6 + .... ( = s1 , say ) and then i observed that the sum nC1 + nC4 + nC7 + ... is either +1 (if [n/3] is something even ) or -1 (if the same is something odd). Since [2003/3] = 667 which is looking like an odd number, therefore, the sum should be s1 - 1, and then some calculation and the answer are in right front of you.

Dev Sharma - 1 year, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...