9. Geometric Counting · Mastering AMC 8

9.10%

Geometric Counting Fundamentals

In this section you will be able to count triangles by choosing 3 points, and throw out the groups of 3 that sit on one line.

Draw an octagon and join any 3 of its corners. You get a triangle! How many different triangles can you make? Guess before you count.

A triangle is fixed by its 3 corners. So counting triangles is really counting groups of 3 points.

Look:3 points on one straight line make a flat line, not a triangle. Count all groups of 3, then subtract the flat ones.

Exploreplay first, formulas later

Try this: Click any 3 corners of the octagon. Do you always get a triangle?
Try this: Press Random triangle a few times. How many groups of 3 corners are there? Does it match 8 × 7 × 6 ÷ 6?
Try this: Press Dot grid and pick the 3 dots of the middle row. What goes wrong?
Try this: Turn on "Show lines with 3+ points". How many red lines? Why do we subtract them?

Watch itpredict, then reveal

Example 9.1

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

1
How many vertices defines a triangle?

Predict first:
Your prediction

Try it

Problem 9.5.1

How many triangles can be formed by connecting 3 points in the figure below?

Contest cornerreal contest problems

Problem 9.5.6

Omega Learn Math Contest

How many triangles are in this figure?

Checkpoint for section 9.1

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

9.20%

Number of Squares in Grid

In this section you will be able to count squares of every size in a grid, one size at a time.

How many squares are on a 4 × 4 grid? If you said 16, look again: the big outer square counts too, and so do the 2 × 2 ones!

Count the squares size by size. A bigger square has fewer places to sit, so each size gives a smaller perfect square.

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 and press Slide the square until it comes back. How many spots did it visit?
Try this: Try sizes 1, 2, 3 and 4. What pattern do the numbers 16, 9, 4, 1 make?
Try this: Change the grid to 5 × 5. Predict the new total before you look at the table.

Name it

Theorem 9.2.1 · Squares in a Grid

The number of squares in a $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 9.2

How many squares of all sizes can be formed from a 4x4 grid of unit squares?

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

1
What's the easiest and most systematic way to count all possible squares?

Try it

Problem 9.5.2

How many squares of all sizes can be formed from a 3x3 grid of unit squares?

Problem 9.5.15(additional)

How many squares are in a 5x5 grid of squares with 2 diagonally opposite corners missing?

Checkpoint for section 9.2

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

9.30%

Number of Rectangles in Grid

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

A chocolate bar is a 3 × 5 grid of squares. You may snap out any rectangle of pieces. How many different rectangles could you snap out?

Every rectangle has a top side, a bottom side, a left side and a right side. Pick those lines, and the rectangle is fixed.

Look:squares are rectangles too. To count rectangles that are not squares, count all rectangles and subtract the squares.

Exploreplay first, formulas later

Try this: Click 2 horizontal lines and 2 vertical lines. Do you always get a rectangle?
Try this: How many ways can you pick 2 of the 4 horizontal lines? List them!
Try this: Turn on Non-squares only. Which rectangles turn red when you pick them?

Name it

Theorem 9.3.1 · Rectangles in a Grid

The general formula for 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 9.3

How many rectangles are in a 3x5 grid of rectangles?

1
What defines a rectangle in a grid?

Predict first:

Example 9.4

Omega Learn

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

1
Counting non-squares directly is messy. What is easier to count?

open on YouTube

Example 9.5

Omega Learn

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

1
Can a square with side $\sqrt{5}$ sit flat, with sides along the grid lines?

Predict first:

open on YouTube

Try it

Problem 9.5.3

How many rectangles of any size are in a $4 \times 6$ grid of squares?

Problem 9.5.8(additional)

How many rectangles of any size are in a $4 \times 6$ grid of squares?

Problem 9.5.16(additional)

How many rectangles are in the figure below?

Contest cornerreal contest problems

Problem 9.5.14(additional)

AMC 8

Toothpicks are used to make a grid that is 60 toothpicks long and 32 toothpicks wide. How many toothpicks are used altogether?

Checkpoint for section 9.3

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

9.40%

Path Counting

In this section you will be able to count up-and-right paths on a grid by turning each path into a word of R's and U's.

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

Write each route as a word: R for a right hop, U for an up hop. Different routes give different words. So counting routes is the same as counting word rearrangements.

Look:if some point is blocked, count all paths and subtract the paths through the blocked point.

Exploreplay first, formulas later

Try this: Draw any route to the carrot. How many R hops? How many U hops?
Try this: Turn on Pascal fill. What number sits at the carrot? Why is each number the sum of its left and lower neighbours?
Try this: Change the trip to 3 right steps and 2 up steps. Predict the number before you look.

Name it

Theorem 9.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 9.6

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
How many right and up moves does the rabbit need to get to the carrot?

Predict first:
Your prediction: R movesYour prediction: U moves

Example 9.7

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
You may visit one or two of the spots, just not all three. What is easier to count: the safe paths or the eaten ones?

Predict first:

open on YouTube

Example 9.8

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 never moves left. So once she steps right out of a column, can she come back to it?

open on YouTube

Example 9.9

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
From a white square, which squares can the marker move to?

open on YouTube

Try it

Problem 9.5.4

A mouse is standing on a grid at location (0,0). There is cheese on the grid at (5,5). He can only move right or up. How many different paths can he take to the cheese?

Problem 9.5.11(additional)

Josh starts at the point (0,0) and needs to travel to his home at the point (6,7). There is a fire at the point (2,3) so he cannot travel there. How many ways are there for Josh to reach his home if he can only move up or right?

Problem 9.5.12(additional)

Josh starts at the point (0,0) and needs to travel to his home at the point (6,7). There is a fire at the point (2,3) so he cannot travel there. Also, he needs to pick up a book from the library at the point (5,5). How many ways are there for Josh to pick up the book and reach his home if he can only move up or right?

Problem 9.5.13(additional)

Josh is now home at the point (6,7) but realizes he forgot something at school which is at the point (8,11). Because he is in a rush to get there before it closes, he is now willing to move diagonally (up-right) in addition to being able to go up and right. How many ways can he reach his school?

Contest cornerreal contest problems

Problem 9.5.5

AMC 8

Samantha lives 2 blocks west and 1 block south of the southwest corner of City Park. Her school is 2 blocks east and 2 blocks north of the northeast corner of City Park. On school days she bikes on streets to the southwest corner of City Park, then takes a diagonal path through the park to the northeast corner, and then bikes on streets to school. If her route is as short as possible, how many different routes can she take?

Problem 9.5.7

Omega Learn Math Contest

Joe is standing at the point (0,0) in the infinite coordinate plane. On any given move, there is a $\frac{1}{3}$ chance of him moving up, $\frac{1}{3}$ chance of him moving right, $\frac{1}{6}$ chance of him moving down, and $\frac{1}{6}$ chance of him moving left. If the probability he will reach the point (3,3) in less than or equal to 8 moves can be described as $\frac{a}{3^b}$ , then what is the value of a + b?

Checkpoint for section 9.4

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

9.5

Practice Problems

In this section you will be able to mix triangles, squares, rectangles and paths on contest problems.

Time to mix it all up! These problems use every trick in the chapter: choosing points, choosing lines and turning paths into words.

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

Contest cornerreal contest problems

Problem 9.5.10(additional)

EMCC

A frog is located at the origin. It makes four hops, each of which moves it either 1 unit to the right or 1 unit to the left. If it also ends at the origin, how many 4-hop paths can it take?

Problem 9.5.17(additional)

BmMT

Leanne and Jing Jing are walking around the $xy$ plane. In one step, Leanne can move from any point $(x, y)$ to $(x + 1, y)$ or $(x, y + 1)$ and Jing Jing can move from $(x, y)$ to $(x - 2, y + 5)$ or $(x + 3, y - 1)$ . The number of ways that Leanne can move from $(0, 0)$ to $(20, 20)$ is equal to the number of ways that Jing Jing can move from $(0, 0)$ to $(a, b)$ , where a and b are positive integers. Compute the minimum possible value of $a + b$ .