## 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}$?