|
|
| Line 2: |
Line 2: |
| | Compute the [[remainder]] when <center><p><math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}</math></p></center> is divided by 1000. | | Compute the [[remainder]] when <center><p><math>{2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}</math></p></center> is divided by 1000. |
| | ==Solution== | | ==Solution== |
| − | Let <math>\omega</math> and <math>\zeta</math> be the two [[complex]] third-roots of 1. Then let
| + | Since |
| | | | |
| − | <math>S = (1 + \omega)^{2007} + (1 + \zeta)^{2007} + (1 + 1)^{2007} = \sum_{i = 0}^{2007} {2007 \choose i}(\omega^i + \zeta^i + 1)</math>.
| |
| | | | |
| − | Now, if <math>i</math> is a [[multiple]] of 3, <math>\omega^i + \zeta^i + 1 = 1 + 1 + 1 = 3</math>. If <math>i</math> is one more than a multiple of 3, <math>\omega^i + \zeta^i + 1 = \omega + \zeta + 1 = 0</math>. If <math>i</math> is two more than a multiple of 3, <math>\omega^i + \zeta^i + 1 = \omega^2 + \zeta^2 + 1= \zeta + \omega + 1 = 0</math>. Thus
| + | <math>\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n</math> |
| | | | |
| − | <math>S = \sum_{i = 0}^{669} 3 {2007 \choose 3i}</math>, which is exactly three times our desired expression.
| |
| | | | |
| − | We also have an alternative method for calculating <math>S</math>: we know that <math>\{\omega, \zeta\} = \{-\frac{1}{2} + \frac{\sqrt 3}{2}i, -\frac{1}{2} - \frac{\sqrt 3}{2}i\}</math>, so <math>\{1 + \omega, 1 + \zeta\} = \{\frac{1}{2} + \frac{\sqrt 3}{2}i, \frac{1}{2} - \frac{\sqrt 3}{2}i\}</math>. Note that these two numbers are both cube roots of -1, so <math>S = (1 + \omega)^{2007} + (1 + \zeta)^{2007} + (1 + 1)^{2007} = (-1)^{669} + (-1)^{669} + 2^{2007} = 2^{2007} - 2</math>.
| + | that sum equals <math>2^{2007}</math>. So we just need to find n such that |
| | + | |
| | + | <math>n\equiv 2^{2007} \pmod 100</math> |
| | + | |
| | | | |
| − | Thus, the problem is reduced to calculating <math>2^{2007} \pmod{1000}</math>.
| |
| | | | |
| | {{solution}} | | {{solution}} |
Revision as of 10:30, 8 October 2007
Problem
Compute the remainder when
is divided by 1000.
Solution
Since
that sum equals 
. So we just need to find n such that
This problem needs a solution. If you have a solution for it, please help us out by adding it.
. So we just need to find n such that
