0% found this document useful (0 votes)

94 views21 pages

Counting A

math

Uploaded by

Senben Liao

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

94 views21 pages

Counting A

math

Uploaded by

Senben Liao

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 21

Lesson 16: Counting A

Adithya B., Brian L., William W., Daniel X.

October 2020

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 1 / 16
Casework: General Ideas

Casework is unappealing, but sometimes it’s the only way to solve a

question, or at least the easiest way without being extremely clever
Always try to look for ways to simplify casework. Small observations
go a long way
Have a rough estimate for how long casework will take you before you
begin to make sure it’s feasible
Organize your casework. Label every case on your scratchwork to
make sure that it’s exhaustive and you’re not overcounting
Outline all major cases before beginning to compute any particular
case

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 2 / 16
Casework

2019 HMMT C9
How many ways can one fill a 3 × 3 square grid with nonnegative integers
such that no nonzero integer appears more than once in the same row or
column and the sum of the numbers in every row and column equals 7?

How do we begin?
List out all ways the fill a single row/column
(0, 0, 7), (0, 1, 6), (0, 2, 5), (0, 3, 4), (1, 2, 4)
What happens if there’s a 7 in the grid?
There must be a (0, 0, 7) column and row, so we end up wanting to
fill up a 2 × 2
We can have either 3 7s or 1 7 in the grid
6 + 9 · 6 = 60

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 3 / 16
2019 HMMT C9

What
 happens
 if we have a 6 in the grid?
0 1 6
 ? ? 1
? ? 0
Similarly, we can either have 3 6s, or 1 6. How many in each case?
12 + 9 · 22 · 2 = 84
What
 happens
 if we have a 5 in the grid?
0 2 5
 ? ? 2
? ? 0
Same deal - we can either have 3 5s or 1 5. This time the cases are
slightly different
12 + 9 · 22 = 48
Proceeding similarly, if there is a 3 there are 12 ways, and if there are
only 1, 2, 4 there are 12 ways
60 + 84 + 48 + 12 + 12 = 216
Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 4 / 16
2019 HMMT C9: An Easier Approach

Remember that our tuples are

(0, 0, 7), (0, 1, 6), (0, 2, 5), (0, 3, 4), (1, 2, 4). Try writing them in binary
Key idea: In each tuple, there’s a 1 in the 1s place, a 1 in the 2s
place, a 1 in the 4s place
So, we can construct all possible squares by just adding 1 to 3
squares, then 2 to 3 squares, then 4 to 3 squares
The number of ways to choose 3 squares to add 1 to is 3! = 6
Same for the others, so our answer is 63 = 216

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 5 / 16
Casework

2018 AIME II #15

Find the number of functions f from {0, 1, 2, 3, 4, 5, 6} to the integers
such that f (0) = 0, f (6) = 12, and

|x − y | ≤ |f (x) − f (y )| ≤ 3|x − y |

for all x and y in {0, 1, 2, 3, 4, 5, 6}.

Let y = x + 1. We obtain 1 ≤ |f (x + 1) − f (x)| ≤ 3. Let

f (x + 1) − f (x) = g (x).
Note that
g (0) + g (1) + g (2) + g (3) + g (4) + g (5) = f (6) − f (0) = 12
Given f (0) = 0 and f (6) = 12, how many times can g (x) be negative
(where 0 ≤ x ≤ 5)?
At most once. If it decreases more than that, then
f (6) ≤ 3 · 4 − 2 = 10, which is not true.
Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 6 / 16
2018 AIME II #15

Casework on the number of times g (x) is negative

Case 1: g (x) is always positive
How many ways are there to choose values for g (x) given
1 ≤ g (x) ≤ 3?
For 0 ≤ x ≤ 5, let g (x) = 1 a times, g (x) = 2 b times, and g (x) = 3
c times
a + 2b + 3c = 12 and a + b + c = 6
b + 2c = 6
(0, 6, 0), (1, 4, 1), (2, 2, 2), (3, 0, 3)
Number of 6possible ways to order is
6 6 6

0,6,0 + 1,4,1 + 2,2,2 + 3,0,3 = 1 + 30 + 90 + 20 = 141
Case 2: g (x) is negative once
Note 2 ≤ |f (x + 2) − f (x)| ≤ 6 or 2 ≤ |g (x) + g (x + 1)| ≤ 6
If g (x) or g (x + 1) is negative (only one can be), then it must be
equal to −1, and the other has to be equal to 3.
Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 7 / 16
2018 AIME II #15

If g (0) = −1, then g (1) = 3. For g (x) where 2 ≤ x ≤ 5, we can find

the possible values with a similar procedure as case 1.
g (2) + g (3) + g (4) + g (5) = 10
a + 2b + 3c = 10 and a + b + c = 4, so b + 2c = 6
(1, 0, 3) and (0, 2, 2) =⇒ 4 + 6 = 10
If g (5) = −1, we have another 10 possibilities because the case is
symmetric.
If g (1) = −1, then g (0) = g (2) = 3.
g (3) + g (4) + g (5) = 7
a + 2b + 3c = 7 and a + b + c = 3
(1, 2, 0), (2, 0, 1) =⇒ 3 + 3 = 6
We have 6 more functions when g (2), g (3), g (4) = −1.
141 + 2 · 10 + 4 · 6 = 185 .

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 8 / 16
Symmetry

Some counting questions have a notion of symmetry

Easy example: How many ways are there to arrange n people around
a table if rotations are indistinguishable?
n!/n = (n − 1)!
You can tell a question will involve symmetry if it includes words such
as ”indistinguishable” or involves something that can be spun/flipped
like a cube or a circle
We divided by n in the above example because all permutations
belong into a group of equivalent rotations of size n. When beginning
symmetry questions, it’s important to first find these equivalence
groups

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 9 / 16
Symmetry

2018 PUMaC C5
How many ways are there to color the 8 regions of a three-set Venn
Diagram with 3 colors such that each color is used at least once? Two
colorings are considered the same if one can be reached from the other by
rotation and reflection.

Replace 3 colors with n, and remove the restriction that we need each
color at least once
Note that there are 6 possible symmetries - 3 flips and 3 rotations.
So, our answer is n8 /6
Why is this wrong?
Unlike our previous example, not every coloring is in “groups of 6.”
For example, if everything is colored the same color, there is only 1
symmetry, not 6. We can’t just blindly divide by 6

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 10 / 16
2018 PUMaC C5

Note that 6 is the maximum possible number of elements in a

“symmetry class,” so all symmetry classes have 1, 2, 3 or 6 elements.
Let’s go through them 1 by 1.
Call the regions R∅ , RA , RB , etc. Ignore R∅ and RA,B,C
How many symmetry classes have size 1?
This means that no matter how it’s rotated or flipped, it is still the
same coloring. So, RA = RB = RC and RA,B = RA,C = RB,C
There are n2 colorings with symmetry class size 1
How many symmetry classes have size 2?
Trick question! None of them do
How many symmetry classes have size 3?
This means that both S1 = {RA , RB , RC } and
S2 = {RA,B , RA,C , RB,C } have at most 2 distinct elements
We have 3 cases: (|S1 |, |S2 |) = (1, 2), (2, 1), (2, 2)
Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 11 / 16
2018 PUMaC C5

For (1, 2), choose a color for S1 , and choose 2 colors along with an
orientation for S2 . So, we get 3n2 (n − 1)
For (2, 2), we choose 2 colors for each S1 and S2 , but note that we
multiply by 3 once since they have the same orientation, so
3n2 (n − 1)2
In total, we have 3n2 (n − 1)(n + 1)
Finally, how many have symmetry class size 6?
Just the remainder, so

n6 − 3n2 (n2 − 1) − n2 = n6 − 3n4 + 2n2

So, our answer is

6 4 2 3n2 (n2 − 1) n8 + 3n6 + 2n4

2 n − 3n + 2n 2
n + +n =
6 3 6

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 12 / 16
2018 PUMaC C5
n8 +3n6 +2n4
Denote f (n) = 6 . How do we finish?
We need at least one of each color, so by PIE our answer is

f (3) − 3f (2) + 3f (1) = 1485 − 240 + 3 = 1248

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 13 / 16
Burnside’s Lemma

As we saw in the previous question, computations can get hard when

there are too many symmetries
We want a method to prevent casework on symmetries
Burnside’s Lemma
Given a set X and a group of symmetries, G , let X g be the number of
elements in X fixed by g ∈ G . Then,
1 X g
|X /G | = |X |
|G |
g ∈G

Roughly speaking, this means that the total number of ways to count
something is the average of the fixed sets over all symmetries
We won’t be proving this since it requires some nontrivial group
theory

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 14 / 16
Burnside’s Lemma

Classic
How many ways are there to color the faces of a cube with n colors if
rotations are considered indistinguishable?

Let’s use Burnside’s! We first need a list of all the symmetries

This basically means: How many ways can we orient the cube? We
have 6 ways to choose the top face and 4 ways to choose the front
face. So, 24 total symmetries
Let’s try to characterize these symmetries more descriptively. Given a
certain orientation, how can we move the cube?
The identity rotation: 1
90o rotation about a face: 6
180o rotation about a face: 3
120o rotations about a space diagonal: 8
180o rotations about a face diagonal: 6

Adithya B., Brian L., William W., Daniel X. Lesson 16: Counting A October 2020 15 / 16
Burnside’s Lemma