Saturday, November 4, 2006

Pick And Choose. Topic: Combinatorics. Level: AMC.

Problem: (2006 Math Is Cool Championships) How many rectangles can you make in a $ 5 \times 6 $ grid? [Reworded]

Solution #1: Here's the "harder" solution, involving counting and subtracting. Consider all $ 42 $ points (since there are $ 5 $ and $ 6 $ sides). Pick any point first; there are $ 42 $ possible. Then pick any point not on the same horizontal/vertical lines. There are $ 42-6-7+1 = 30 $ of these. Form a rectangle with these as opposite vertices. We get $ 42*30 $ rectangles.

But wait, each rectangle has four vertices so we overcount by $ 4 $ times (pick vertices $ 1-3 $, $ 3-1 $, $ 2-4 $, $ 4-2 $). So divide by $ 4 $ and get $ 315 $. QED.

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

Solution #2: Here's the "clever" solution. We will pick four lines - two vertical and two horizontal. It's not hard to see that each set of four lines will determine a unique rectangle (formed by the four intersection points). Hence the result is

$ 6C2 \cdot 7C2 = 15 \cdot 21 = 315 $.

QED.

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

Comment: The first is probably more practical in a competition setting, but the second is probably more generally applicable and more educational. In any case, it's good to see two approaches to the same problem.

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

Practice Problem: (2006 Math Is Cool Championships) How many integers are in the range of the function $ f(x) = \frac{4x^2+75}{2x^2+3} $?

2 comments:

  1. Second solution is similar to my "pick two points" solution, just with the correct numbers haha.

    Anyway, you're still only counting the rectangles aligned with the axes. I want to see a full solution. :P

    ReplyDelete
  2. Well I think of a grid as filled in with lines and the rectangles are supposed to be made out of the lines... so we don't care about those... lol.

    ReplyDelete