2016 AMC 10B Problem 14

P11-15~5 minPrint

Coordinate Geometry Basic Counting Bound the quantity above/below or estimate to pin it down Split into exhaustive cases and handle each

How many squares whose sides are parallel to the axis and whose vertices have coordinates that are integers lie entirely within the region bounded by the line $y=\pi x$ , the line $y=-0.1$ and the line $x=5.1?$

Show solution without answering

Key insight

The line y = pi x slopes up, so a square can only cross it at its top-left corner. Check that corner, then count squares by side length.

Solution

Understand the region. It is a triangle: to the right of and below the line $y = \pi x$ , above $y = -0.1$ , and left of $x = 5.1$ . Corners must have whole-number coordinates, so "above $-0.1$ " just means $y \ge 0$ , and "left of $5.1$ " just means $x \le 5$ .

Which corner can cross the line? The line goes up as it goes right, so the region is widest at the right. For a square, the corner closest to the line is the top-left one. If that corner is on or below the line, the whole square is.

Set up the count. Name a square by its bottom-left corner $(a, b)$ and side $s$ . Its top-left corner is $(a, b + s)$ . The square fits when:

$b \ge 0$ (bottom edge not below the $x$ -axis),
$a + s \le 5$ (right edge not past $x = 5$ ),
$b + s \le \pi a$ (top-left corner not above the line).

Since $b + s$ is a whole number, the last rule means $b + s$ is at most the whole-number part of $\pi a$ :

$a$	$1$	$2$	$3$	$4$
$\pi a$	$3.14$	$6.28$	$9.42$	$12.57$
top of square at most	$3$	$6$	$9$	$12$

(For $a = 0$ the top would have to be at most $0$ , which is impossible.)

Count. For a given $a$ and $s$ , the bottom $b$ can be $0, 1, \ldots$ up to (top limit) $- s$ . That is (top limit) $- s + 1$ choices.

Side $1$ ( $a$ can be $1, 2, 3, 4$ ): $3 + 6 + 9 + 12 = 30$ .
Side $2$ ( $a$ can be $1, 2, 3$ ): $2 + 5 + 8 = 15$ .
Side $3$ ( $a$ can be $1, 2$ ): $1 + 4 = 5$ .
Side $4$ ( $a$ must be $1$ ): the top would need to be at most $3$ , but the square is $4$ tall. None.

Total: $30 + 15 + 5 = 50$ .

The answer is $\boxed{\textbf{(D)}\ 50}$ .

Why this works

To check that a square fits under a slanted line, you only need to test the one corner that sticks out furthest toward the line. After that, it is careful counting, organized by the size of the square. The strange numbers $-0.1$ and $5.1$ are there only so that squares touching the $x$ -axis or the line $x = 5$ still count.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The region is the triangle-like area with $y \ge -0.1$ , $x \le 5.1$ and $y \le \pi x$ . For lattice squares the first two conditions simply say $y \ge 0$ and $x \le 5$ .

Describe a square by its lower-left corner $(a, b)$ and side $s$ . Since the line $y = \pi x$ rises to the right, the corner of the square most likely to cross it is the top-left corner $(a, b+s)$ . So the square fits exactly when
$b \ge 0, \qquad a + s \le 5, \qquad b + s \le \pi a.$
Because $b + s$ is an integer, the last condition is $b + s \le \lfloor \pi a \rfloor$ , and $\lfloor \pi a\rfloor = 3, 6, 9, 12$ for $a = 1, 2, 3, 4$ (and $a = 0$ gives nothing).

For each $a$ and $s$ the number of valid $b$ is $\lfloor \pi a \rfloor - s + 1$ when positive:

$s = 1$ : $a = 1,2,3,4$ give $3 + 6 + 9 + 12 = 30$ .
$s = 2$ : $a = 1,2,3$ give $2 + 5 + 8 = 15$ .
$s = 3$ : $a = 1,2$ give $1 + 4 = 5$ .
$s = 4$ : $a = 1$ would need $b + 4 \le 3$ , impossible.

Total: $30 + 15 + 5 = 50$ .

The answer is $\boxed{\textbf{(D)}\ 50}$ .

Review in the AoPS books

Introduction to Geometry, Chapter 17: Analytic Geometry
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Introduction to Algebra, Chapter 8: Graphing Lines