7. Geometric Counting · Mastering AMC 10/12

7.10%

Triangle Counting

In this section you will be able to count triangles by choosing their 3 corners, and subtract the choices that fall on one line.

How many triangles can you draw using the corners of a stop sign? Listing them by shape is slow. There is a one-line answer.

A triangle is set by its 3 corners. So counting triangles means counting groups of 3 points. That’s a combination.

The catch: 3 points on one line make no triangle. Count every group of 3, then subtract the collinear ones. The same trick works for any shape: ask what defines it, then choose those pieces.

Exploreplay first, formulas later

Try this: Pick any 3 vertices of the octagon. Do you always get a triangle? Press Random triangle a few times.
Try this: Switch to Dot grid and set 5 rows and 5 columns. Turn on the red lines. Find a line with 5 dots: how many triples does it waste?
Try this: Switch to Chords and pick 6 points. Which 3 chords make the shaded triangle? How many of the 8 points does each interior triangle use?

Watch itpredict, then reveal

Example 7.1

How many triangles can be formed by connecting vertices in a regular octagon?

1
You could do casework on the type of triangle, but there is a much slicker way. How many vertices define a triangle?

Predict first:
Your prediction

Example 7.2

AMC 10

Eight points are chosen on a circle, and chords are drawn connecting every pair of points. No three chords intersect in a single point inside the circle. How many triangles with all three vertices in the interior of the circle are created?

1
Look at one triangle inside the circle. Each side lies along a chord. How many chords does the triangle use?

Predict first:
Your prediction

Example 7.3

AMC 10

How many triangles with positive area have all their vertices at points $(i, j)$ in the coordinate plane, where $i$ and $j$ are integers between $1$ and $5$ , inclusive?

1
There are $5 \times 5 = 25$ points. How many ways can you pick 3 of them?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 7.6.1

AMC 10

A set of 25 square blocks is arranged into a $5 \times 5$ square. How many different combinations of 3 blocks can be selected from that set so that no two are in the same row or column?

Problem 7.6.2

AMC

From a regular octagon, a triangle is formed by connecting three randomly chosen vertices of the octagon. What is the probability that at least one of the sides of the triangle is also a side of the octagon?

Checkpoint for section 7.1

Get 2 of 3 right to master this section. One try each, no hints.

7.20%

Rectangle Counting

In this section you will be able to count every rectangle in a grid by choosing 2 horizontal and 2 vertical lines.

A $3 \times 5$ grid has 15 small rectangles. How many rectangles of all sizes are hiding in it? Guess before you scroll.

Four corner points don’t always make a rectangle. But two horizontal lines and two vertical lines always do, and every rectangle comes from exactly one such choice. So you count pairs of lines, not shapes.

Exploreplay first, formulas later

Try this: Pick 2 horizontal and 2 vertical lines. Can two different picks give the same rectangle?
Try this: Change the grid to 2 rows and 3 columns. Predict the count before you look at the readout.
Try this: Turn on Non-squares only. Why does the readout subtract the squares? (You'll need this in Example 7.6.)

Name it

Theorem 7.2.1 · Rectangles in a Grid

The number of rectangles of all sizes in a rectangular grid of size $m \times n$ is

\binom{m+1}{2} \times \binom{n+1}{2}.

Watch itpredict, then reveal

Example 7.4

How many rectangles are in a $3 \times 5$ grid of rectangles?

1
Tedious casework would work, but there is a slick solution. What defines a rectangle in a grid?

Predict first:
Click a choice or type its letter (A–E).

Checkpoint for section 7.2

Get 2 of 3 right to master this section. One try each, no hints.

7.30%

Square Counting

In this section you will be able to count squares size by size, including tilted squares and squares that must cover a given cell.

A chessboard has 64 small squares. How many squares does it have in total? Much more than 64.

Squares don’t come from free choices of lines: the sides must match. So go size by size. A $k \times k$ square slides into a row of $n$ cells in $n - k + 1$ positions, so it fits in $(n - k + 1)^2$ places in an $n \times n$ grid.

Look: squares can also be tilted. A side from one dot to another that goes 1 across and 2 up has length $\sqrt5$ .

Exploreplay first, formulas later

rows4

columns4

square size1

Squares of each size
size	how many	running total
1 × 1	4 × 4 = 16	16
2 × 2	3 × 3 = 9	25
3 × 3	2 × 2 = 4	29
4 × 4	1 × 1 = 1	30

16 + 9 + 4 + 1 = 30 squares

Try this: Set the square size to 2. How many places does it fit in the 4 × 4 grid? Size 3?
Try this: Why does a k × k square fit in (5 − k) × (5 − k) places here? Check it with Slide the square.
Try this: Turn on Tilted squares with a = 1 and b = 2. Is the slanted shape a real square? How long is each side?

Name it

Theorem 7.3.1 · Squares in a Grid

The number of squares in an $n \times n$ grid of squares is

1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}.

Watch itpredict, then reveal

Example 7.5

How many squares of all sizes can be formed from a $4 \times 4$ grid of unit squares?

rows4

columns4

square size1

Squares of each size
size	how many	running total
1 × 1	?	?
2 × 2	?	?
3 × 3	?	?
4 × 4	?	?

Count hidden: predict it first

1
There are 16 unit squares. Is the answer 16?

Predict first:
Click a choice or type its letter (A–E).

Example 7.6

Omega Learn

How many rectangles, which are not squares, are in a $5 \times 4$ grid of squares?

1
Squares are rectangles too, so count all rectangles first. The grid has 6 vertical and 5 horizontal lines. How many rectangles?

Predict first:
Your prediction

open on YouTube

Example 7.7

Omega Learn

How many squares with side length $\sqrt{5}$ can be found in a $5$ by $5$ grid of points?

1
Can a side of length $\sqrt5$ be horizontal?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 7.8

AMC 10

The $5 \times 5$ grid shown contains a collection of squares with sizes from $1 \times 1$ to $5 \times 5$ . How many of these squares contain the black center square?

rows5

columns5

square size1

Squares of each size
size	how many	running total
1 × 1	?	?
2 × 2	?	?
3 × 3	?	?
4 × 4	?	?
5 × 5	?	?

Count hidden: predict it first

1
Count by size again. How many $1 \times 1$ squares contain the black square?

Predict first:
Your prediction

open on YouTube

Example 7.9

Modified AMC 10

How many rectangles formed by the gridlines in this $5 \times 5$ grid contain the black center square?

1
A rectangle is fixed by its top, bottom, left and right gridlines. For the rectangle to contain the black square, where must its top line be?

Predict first:
Your prediction

open on YouTube

Example 7.10

AMC 10

As shown in the figure below, a regular dodecahedron (the polyhedron consisting of 12 congruent regular pentagonal faces) floats in space with two horizontal faces. Note that there is a ring of five slanted faces adjacent to the top face, and a ring of five slanted faces adjacent to the bottom face. How many ways are there to move from the top face to the bottom face via a sequence of adjacent faces so that each face is visited at most once and moves are not permitted from the bottom ring to the top ring?

Highlight

turn30°

tilt15°

Dodecahedron · Colors: top face, top ring, bottom ring, bottom face.

Drag the solid (or use turn and tilt) to look at the back.

faces F12

vertices V20

edges E30

faces F: 12 pentagons
vertices V: 20 vertices with 3 edges
Add up the sides of every face: 12·5 = 60 = 2 × 30
Add up the edges at every vertex: 20·3 = 60 = 2 × 30

V − E + F = 20 − 30 + 12 = 2

1
Your first move goes from the top face into the top ring. How many choices?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 7.6.4

AMC 10

How many ways are there to place 3 indistinguishable red chips, 3 indistinguishable blue chips, and 3 indistinguishable green chips in the squares of a $3 \times 3$ grid so that no two chips of the same color are directly adjacent to each other, either vertically or horizontally?

Checkpoint for section 7.3

Get 2 of 3 right to master this section. One try each, no hints.

7.40%

Path Counting

In this section you will be able to count shortest grid paths as words of R's and U's, and handle blocked points, pens and colorings.

A rabbit at $(0, 0)$ wants the carrot at $(5, 5)$ . It only hops right or up. How many different routes can it take?

Write each route as a word: R for a right hop, U for an up hop. Every route is a 10-letter word with five R’s and five U’s, and every such word is a route. So counting routes is counting word rearrangements.

When the rules get stranger (blocked spots, moves down, colored cells), look for what really decides the route. Then count those choices.

Exploreplay first, formulas later

Try this: Draw any route to the carrot. Read its word of R's and U's. Why is every route a rearrangement of RRRRRUUUUU?
Try this: Turn on Pascal fill. Which two numbers add up to make each number?
Try this: Change the carrot to (3, 2). Predict the count before you turn on Pascal fill.

Name it

Theorem 7.4.1 · Lattice Paths

The number of ways to get from $(0,0)$ to a point $(m,n)$ moving only up and right is

\binom{m+n}{m}.

Watch itpredict, then reveal

Example 7.11

A rabbit is walking in a coordinate plane and has to get from $(0,0)$ to the carrot at the point $(5,5)$ . If the rabbit can only move 1 unit up or 1 unit right on any given move, how many ways are there for the rabbit to get to the carrot?

1
Casework would be tedious. Write R for a right move and U for an up move. How many right moves does the rabbit need?

Predict first:
Your prediction

Example 7.12

How many ways to go from $(0, 0)$ to $(5, 6)$ moving only right or up if you cannot visit all of $(1, 2)$ , $(3, 4)$ , and $(5, 5)$ because there is a monster that will eat you if you visit all 3 locations?

1
Ignore the monster for now. How many right/up paths go from $(0,0)$ to $(5,6)$ ?

Predict first:
Your prediction

open on YouTube

Example 7.13

BMMT

Sally is inside a pen consisting of points $(a, b)$ such that $0 \le a \le b \le 4$ . If she is currently on the point $(x, y)$ , she can move to either $(x, y + 1)$ , $(x, y - 1)$ , or $(x + 1, y)$ . Given that she cannot revisit any point she has visited before, find the number of ways she can reach $(4, 4)$ from $(0, 0)$ .

1
Sally can never move left. Once she steps right into a new column, can she ever come back to the old one?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 7.14

AMC 8

A game board consists of 64 squares that alternate in color between black and white. The figure below shows square $P$ in the bottom row and square $Q$ in the top row. A marker is placed at $P$ . A step consists of moving the marker onto one of the adjoining white squares in the row above. How many 7-step paths are there from $P$ to $Q$ ? (The figure shows a sample path.)

1
Each step moves up one row onto a white square diagonally above. How many ways can the marker reach a given white square?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 7.15

HMMT

The cells of a $5 \times 5$ grid are each colored red, white, or blue. Sam starts at the bottom-left cell of the grid and walks to the top-right cell by taking steps one cell either up or to the right. Thus, he passes through 9 cells on his path, including the start and end cells. Compute the number of colorings for which Sam is guaranteed to pass through a total of exactly 3 red cells, exactly 3 white cells, and exactly 3 blue cells no matter which route he takes.

1
How must the grid be colored so that the condition is satisfied?

Checkpoint for section 7.4

Get 2 of 3 right to master this section. One try each, no hints.

7.50%

Polyhedrons

In this section you will be able to count faces, edges and vertices of a polyhedron by counting everything twice and using Euler's formula.

A cube has 6 faces and 8 corners. Saw off every corner. How many edges does the new solid have?

You can’t see the back of a solid, so don’t count edges one by one. Count them twice: once from the faces, once from the vertices. Every edge borders 2 faces and joins 2 vertices.

Then one formula ties the three numbers together. Look: for every convex polyhedron, $V - E + F = 2$ .

Exploreplay first, formulas later

Highlight

turn30°

tilt15°

Cube · Colors: faces with the same number of sides.

Drag the solid (or use turn and tilt) to look at the back.

faces F6

vertices V8

edges E12

faces F: 6 quadrilaterals
vertices V: 8 vertices with 3 edges
Add up the sides of every face: 6·4 = 24 = 2 × 12
Add up the edges at every vertex: 8·3 = 24 = 2 × 12

V − E + F = 8 − 12 + 6 = 2

Try this: Count the cube's edges from its faces, then from its vertices. Do the two sums in the panel agree?
Try this: Try every shape. What is V − E + F each time?
Try this: Turn on Cut every corner. How many new faces and new vertices appear for each corner you cut?

Name it

Concept 7.5.1 · Counting Edges Twice

In a polyhedron, if you add up the number of sides on every face, you get 2 times the number of edges of the polyhedron. This is because each edge is part of 2 faces.

If you add up the number of edges connected to every vertex, you also get 2 times the number of edges, since each edge is counted at 2 different vertices.

For example, a cube has 4 sides per face and 6 faces, so it has $\frac{4 \times 6}{2} = 12$ edges. Also, there are 3 edges per vertex and 8 vertices, so there are $\frac{3 \times 8}{2} = 12$ edges.

Theorem 7.5.2 · Euler's Polyhedron Formula

\text{Edges} = \text{Faces} + \text{Vertices} - 2

E = F + V - 2

Remark 7.5.4

A classic application: if a polyhedron has 12 hexagonal faces and 10 pentagonal faces, how many vertices does it have? Find the number of faces ( $22$ ) and the number of edges,

\frac{12 \times 6 + 10 \times 5}{2} = 61

(we divide by 2 since each edge is part of 2 faces). Finally, apply Euler's Polyhedron Formula: $V = E - F + 2 = 61 - 22 + 2 = 41$ .

(A sharp eye: every vertex needs at least 3 edges, so $2E \ge 3V$ . Here $122 < 123$ , so no real polyhedron has exactly these faces. The method is what matters; a soccer ball, with 20 hexagons and 12 pentagons, works.)

Watch itpredict, then reveal

Example 7.16

AMC 12

A convex polyhedron $Q$ has vertices $V_1, V_2, \ldots, V_n$ , and $100$ edges. The polyhedron is cut by planes $P_1, P_2, \ldots, P_n$ in such a way that plane $P_k$ cuts only those edges that meet at vertex $V_k$ . In addition, no two planes intersect inside or on $Q$ . The cuts produce $n$ pyramids and a new polyhedron $R$ . How many edges does $R$ have?

Highlight

turn30°

tilt15°

Cube · Colors: faces with the same number of sides.

Drag the solid (or use turn and tilt) to look at the back.

faces F6

vertices V8

edges E12

faces F: 6 quadrilaterals
vertices V: 8 vertices with 3 edges
Add up the sides of every face: 6·4 = 24 = 2 × 12
Add up the edges at every vertex: 8·3 = 24 = 2 × 12

V − E + F = 8 − 12 + 6 = 2

1
Essentially, we are cutting off every corner of the polyhedron (try Cut every corner on the cube). According to Euler's Polyhedron Formula, how many faces did the original polyhedron have?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 7.6.3

AMC 10

A rhombic dodecahedron is a convex polyhedron where each of the 12 faces is a rhombus, and all of the faces are congruent to each other. The number of edges that meet at a vertex is either 3 or 4, depending on the vertex. What is the number of vertices at which exactly 3 edges meet?

Problem 7.6.5

AMC 12Challenge

Each face of a regular tetrahedron is painted either red, white, or blue. Two colorings are considered indistinguishable if two congruent tetrahedra with those colorings can be rotated so that their appearances are identical. How many distinguishable colorings are possible?

Problem 7.6.6

AMC 10/12

If $A$ and $B$ are vertices of a polyhedron, define the distance $d(A, B)$ to be the minimum number of edges of the polyhedron one must traverse in order to connect $A$ and $B$ . For example, if $\overline{AB}$ is an edge of the polyhedron, then $d(A, B) = 1$ , but if $\overline{AC}$ and $\overline{CB}$ are edges and $\overline{AB}$ is not an edge, then $d(A, B) = 2$ . Let $Q$ , $R$ , and $S$ be randomly chosen distinct vertices of a regular icosahedron (regular polyhedron made up of 20 equilateral triangles). What is the probability that $d(Q, R) > d(R, S)$ ?

Checkpoint for section 7.5

Get 2 of 3 right to master this section. One try each, no hints.

7.6

Practice Problems

In this section you will be able to mix every tool from this chapter on two harder contest problems.

Two harder counting problems where symmetry does the heavy lifting. Each has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 7.6.7(additional)

AIME

There is an unlimited supply of congruent equilateral triangles made of colored paper. Each triangle is a solid color with the same color on both sides of the paper. A large equilateral triangle is constructed from four of these paper triangles. Two large triangles are considered distinguishable if it is not possible to place one on the other, using translations, rotations, and/or reflections, so that their corresponding small triangles are of the same color.

Given that there are six different colors of triangles from which to choose, how many distinguishable large equilateral triangles may be formed?

Problem 7.6.8(additional)

AMC 10Challenge

Square $ABCD$ in the coordinate plane has vertices at the points $A(1, 1)$ , $B(-1, 1)$ , $C(-1, -1)$ , and $D(1, -1)$ . Consider the following four transformations:

$L$ , a rotation of $90^\circ$ counterclockwise around the origin;
$R$ , a rotation of $90^\circ$ clockwise around the origin;
$H$ , a reflection across the $x$ -axis; and
$V$ , a reflection across the $y$ -axis.

Each of these transformations maps the square onto itself, but the positions of the labeled vertices will change. For example, applying $R$ and then $V$ would send the vertex $A$ at $(1, 1)$ to $(-1, -1)$ and would send the vertex $B$ at $(-1, 1)$ to itself. How many sequences of $20$ transformations chosen from $\{L, R, H, V\}$ will send all of the labeled vertices back to their original positions? (For example, $R, R, V, H$ is one sequence of $4$ transformations that will send the vertices back to their original positions.)