Sunday, December 11, 2005

A Little Logic Goes a Long Way. Topic: Logic/Sets. Level: AIME

Problem: (1983 AIME - #13) For each non-empty subset of $\{1, 2, 3, 4, 5, 6, 7\}$ arrange the members in decreasing order with alternating signs and take the sum. For example, for the subset $\{5\}$ we get $5$. For $\{6, 3, 1\}$ we get $6 - 3 + 1 = 4$. Find the sum of all the resulting numbers. [Source:]

Solution: Well, if you were really in a tenacious mood, you could take all $128$ of the subsets and add it all up. But I'm not, so we'll attack it with some logic.

Consider some subset $S$ of $\{1,2,3,4,5,6\}$. It has some value, call it $x$ when arranged in the given manner. What happens we you add $7$ to $S$? Clearly $7$ has to be the new biggest element. Thus the signs of each of the other elements switches, which means the new subset $S+\{7\}$ has value $7-x$. Adding up $S$ and $S+\{7\}$, we have $x+(7-x) = 7$.

And this works for ANY subset $S$, so if we pair the subsets of $\{1,2,3,4,5,6,7\}$ accordingly, we have the sum of the values of each pair to be $7$. And since there are $128$ total subsets, we have $64$ pairs and an answer of $(64)(7) = 448$. QED.


Comment: As you can see, this argument is pretty slick in killing off this problem in a few moments. Though a #13 on the 1983 AIME, it would be something like a #6 probably on an AIME now.


Practice Problem: Let $(x,y)$ be distinct, relatively prime elements of $\{1,2,\ldots,10\}$. Let $z = x+y$. Find the sum of all values of $z$.


  1. If x=1, then y=1,2,3,4,5,6,7,8,9,10, and sum(z) = 55+10=65.
    If x=2, then y=1,3,5,7,9 and sum(z)=5^2+5(2)=35.
    If x=3, then y=1,2,4,5,7,8,10 and sum(z) = 55-3(3)+3(7) = 67
    If x=4, then y=1,3,5,7,9 and sum(z)=5^2+5(4)=45.
    If x=5, then y=1,2,3,4,6,7,8,9 and sum(z)=55-5(2)+5(8)=85.
    If x=6, then y=1,5,7 and sum(z) = 13+18=31.
    If x=7, then y=1,2,3,4,5,6,8,9,10 and sum(z) = 55-7+7(9) = 111.
    If x=8, then y=1,3,5,7,9 and sum(z)=5^2+5(8)=65.
    If x=9, then y=1,2,4,5,7,8 and sum(z)=27+9(6)=81.
    If x=10, then y=1,3,7,9 and sum(z)=20+10(4)=60.

    Our answer is 645.

    How are you REALLY supposed to do it??? :P

  2. Sum of all the numbers less than n and relatively prime to n is n\phi{n} / 2, so you just need to find \sum_{n=1}^{10} n\phi{n}/2, which is trivial.