## Monday, June 5, 2006

### Better Count Them Right. Topic: Probability & Combinatorics/Sets. Level: AIME.

Problem: (2006 ARML Tiebreaker - #1) In how many ways can you choose three distinct numbers from the set $\{1, 2, \ldots, 34\}$ such that the sum is divisible by three? [Reworded]

Solution: Well let's break it down into cases. Even better, let's just look at the elements $\pmod{3}$. There are $11$ $0$'s, $12$ $1$'s, and $11$ $2$'s.

CASE 1: $0, 0, 0$.

Well we can just take $11 \cdot 10 \cdot 9$ but since we want combinations of these, it is $\frac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165$.

CASE 2: $1, 1, 1$.

Same idea, only we have $12$ to choose from. $\frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = 220$.

CASE 3: $2, 2, 2$.

Same as CASE 1. $165$.

CASE 4: $0, 1, 2$.

We have $11 \cdot 12 \cdot 11$ total sets of three. We see that since the elements are distinct modulo three none of them can be permutations of each other. So we have $11 \cdot 12 \cdot 11 = 1452$.

It's not hard to tell that these are all the cases (well, a little harder under time pressure) so we can just sum them up to get $165+220+165+1452 = 2002$. QED.

--------------------

Comment: The fastest correct answer to this problem at the Las Vegas ARML Site was 2 minutes and 2 seconds. Across the country, it was somewhere around 1 minute. Pretty quick.

--------------------

Practice Problem: (2006 ARML Tiebreaker - #2) Let $f(x) = mx+b$ where $m$ and $b$ are integers with $m > 0$. If $2^{f(x)} = 5$ when $x = \log_8{10}$, find the ordered pair $(m, b)$. [Reworded]

1. Brian got it in 1:10 I think.

2. i got log 2=(3-m)/(3b+3)...

3. side comment:
the first question is almost identical to one that i wrote this year in E=mC.
except i had asked for the set of {1,2,...,10}. everything was identically the same :)

4. 4d331: Umm, not sure how you got that. The question is correct.

5. Oh. Generating functions is bad for the first problem after all. =/

f(log_8 10) = log_2 5 = 3(log_8 10) - 1
m = 3, b = -1

6. (m,b)=(3,-1)