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]

6 comments:

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

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

    ReplyDelete
  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 :)

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

    ReplyDelete
  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

    ReplyDelete