Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 AIME I Problems/Problem 8"

(→‎Solution)
(→‎Solution)
Line 12: Line 12:
  
 
Which is
 
Which is
−
<math>(10)2^{10}+(8)2^9+(6)2^8+(4)2^7 ... +(-10)2^0</math>
+
<math>(10)2^{10}+(8)2^9+(6)2^8+(4)2^7 ... +(-10)2^0 = \sum_{k = 0}^{10}(10-2k)2^{(10-k)}</math>
  
 
By simplifying this, we will get
 
By simplifying this, we will get

Revision as of 20:06, 20 March 2009

Problem 8

Let $S = \{2^0,2^1,2^2,\ldots,2^{10}\}$. Consider all possible positive differences of pairs of elements of $S$. Let $N$ be the sum of all of these differences. Find the remainder when $N$ is divided by $1000$.

Solution

We can do this in an organized way. $(2^{10}-2^9)+(2^{10}-2^8) ... +(2^{10}-2^0) = (10)2^{10} - 2^9-2^8 ... -2^0$ $(2^9-2^8)+(2^9-2^7) ...+(2^9-2^0) = (9)2^9 - 2^8-2^7 ... -2^0$ $(2^8-2^7)+(2^8-2^6) ...+(2^8-2^0) = (8)2^8-2^7-2^6 ... -2^0$

If we continue doing this, we will have $(10)2^{10}+(9)2^9+(8)2^8 ... +2^1 -2^9-(2)2^8-(3)2^7 ... -(10)2^0$

Which is $(10)2^{10}+(8)2^9+(6)2^8+(4)2^7 ... +(-10)2^0 = \sum_{k = 0}^{10}(10-2k)2^{(10-k)}$

By simplifying this, we will get $(16)2^{10}+2^7-(7)2^4-2$

We only care about the last three digits so the answer will be $384+128-112-2 = 398$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_8&oldid=30845"