Bijective Arguments

MathDash
Last updated 2025-01-14

1 Lecture notes

s h
In this lecture, you will want to think about different ways of looking at the same thing.

y
You may have heard different names for this lecture, including combinatorial argu-

a l
ments, bijections, one-to-one correspondence, symmetry and pairing tricks, etc. They

n
all mean (vaguely) the same thing.

D
In essence, we’re asked to count the number of things in a certain set 𝐴, which can be

h O
difficult. Instead, we can show that the elements in set 𝐴 equals the number of elements

t
in another set 𝐵, where counting the elements in set 𝐵 is easier. We’ll do this by pairing

a e
up each element of 𝐴 with a unique element in 𝐵. In doing so, we form a bijection

s
(sometimes called one-to-one correspondence) between 𝐴 and 𝐵.
To drive this point home, we only have a bijection when:

y M l U
• an object in the first set is related to only one object in the second set, and

• an object in the second set is related to only one object in the first set.

B rna 𝑎 1

e
𝑏 2

t
3

In
𝑐

𝑑 4

Let’s take a look at a few common themes of bijection problems.

1.1 Order begets bijection

Say we wish to count the number of ways some structure can be arranged. (In fact, there
is a whole field of combinatorics dedicated to this, called enumerative combinatorics.)
Our most powerful tool will be to biject the desired arrangement to a simpler one.

Example 1.1
How many seven-digit positive integers have the property that their digits, read left
to right, are in strictly increasing order?
1
MathDash (Last updated 2025-01-14) Bijective Arguments

Walkthrough. Note that all arrangements of seven distinct digits are equally likely. Let 𝑆
be the set of seven-digit positive integers described in the statement, and let 𝑇 be the set
of subsets of 7 distinct digits chosen from 1 through 9. I claim that there exists a bijection
between 𝑆 and 𝑇 .

1. Convince yourself that for every integer in 𝑆 , there is a unique element in 𝑇 that
corresponds to it. Hint: if the element in 𝑆 is 1234567, what element in 𝑇 corre-
sponds to it?

2. Convince yourself of the other direction.

3. Compute |𝑇 | .

A bijection from set 𝑆 to set 𝑇 require two things: the set 𝑇 we are bijecting to, and
the function 𝑓 we will use to biject 𝑆 to 𝑇 . In the example above, 𝑇 is the set of ways to

h
choose 7 distinct digits from 1 through 9, and 𝑓 is the function that takes a seven-digit

s y
positive integer and returns the set of digits in that integer.

D a
1.2 Stars and bars

n l
h O
Theorem 1.2 (Stars and bars)

t
The number of
ways to distribute 𝑛 indistinguishable objects to 𝑘 distinguishable

e
1
people is 𝑛+𝑘−
𝑘−1 .

Ma s
True to its name, the proof of this theorem follows from bijecting the set of ways to

U
distribute 𝑛 objects to 𝑘 people to the set of ways to arrange 𝑛 stars and 𝑘 − 1 bars. For

y l
example, the following represents giving one object to the first person, one to the second,

B rna
two to third, none to the fourth, and one to the fifth:

★ | ★ | ★★ || ★.

I will leave as an exercise to the reader to prove this theorem.

te
Example 1.3 (AMC 10A 2003/21)

In
Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and
peanut butter cookies. There are at least six of each of these three kinds of cookies
on the tray. How many different assortments of six cookies can be selected?

Walkthrough. Let 𝑐 be the number of chocolate chip cookies selected, and define 𝑜, 𝑝
similarly. Clearly the problem is equivalent to finding the number of solutions to 𝑐 + 𝑜 +
𝑝 = 6 given that 0 ≤ 𝑐, 𝑜, 𝑝 ≤ 6.

1. Biject the solutions to this equation to a stars and bars arrangement. Hint: the
addition signs act as natural bars!

2. Finish with the given formula.

There are many variants of stars and bars, and they all involve tweaking the formula
slightly. For example:

2
MathDash (Last updated 2025-01-14) Bijective Arguments

Example 1.4
Find the number of ways to distribute 𝑛 indistinguishable objects to 𝑘 distinguishable
people such that each person receives at least one object.

Walkthrough.

1. Convince yourself that this is equivalent to finding the number of solutions to

𝑎1 + · · · + 𝑎𝑘 = 𝑛,

where 𝑎𝑖 ≥ 1 for all 𝑖 .

2. Make the substitution 𝑎′𝑖 = 𝑎𝑖 − 1. What is the new bound on 𝑎′𝑖 ?

h
3. Finish with the stars and bars formula.

Example 1.5

a s ly
D n
An integer is non-decreasing if its digits never decrease (but may stay the same) when
read left to right. How many four-digit positive integers are non-decreasing?

t h O
Walkthrough. Let the digits be the baskets, and the stars be the four chosen digits.

a e
s
Remark 1.6. Another way to think about this is to choose digits 𝑎, 𝑏, 𝑐, 𝑑 such that 1 ≤ 𝑎 ≤

M U
𝑏 ≤ 𝑐 ≤ 𝑑 ≤ 9. We can cleverly rewrite 𝑏 = 𝑎 + 𝑥, 𝑐 = 𝑏 + 𝑦, 𝑑 = 𝑐 + 𝑧 for nonnegative integers
𝑥, 𝑦, 𝑧. See if you can finish the argument from here.

y
B rna l
1.3 Combinatorial Arguments
The central idea is to count in two different ways. A common argument used to prove
combinatorial identities is committee forming.

te
Example 1.7

In
For all positive integers 𝑛, prove that
𝑛  
∑︁ 𝑛
= 2𝑛 .
𝑘=0
𝑘

Walkthrough. Say we wish to form a committee by choosing a subset of 𝑛 people. Then

we may do so in two distinct ways:

1. Choose zero people for the committee, or 1 person, or 2 people, etc.

2. Consider each person individually and decide if they are on or not on the commit-
tee.

3
MathDash (Last updated 2025-01-14) Bijective Arguments

Example 1.8
For all positive integers 𝑛, prove that
𝑛  
∑︁ 𝑛
𝑘 = 𝑛 · 2𝑛−1 .
𝑘=0
𝑘

Walkthrough. Form a committee, and choose a leader from that committee.

For more practice, prove the following identities:

Theorem 1.9 (Pascal’s identity)

For positive integers 𝑛, 𝑘 ,
𝑛+1

h
     
𝑛 𝑛
+ = .
𝑘+1 𝑘+1

s
𝑘

a ly
D n
Theorem 1.10 (Hockey stick identity)
For positive integers 𝑛, 𝑘 ,

h O
𝑛  
𝑛+1

t
 
∑︁ 𝑖
= .
𝑘+1

a e
𝑖=𝑘
𝑘

M U s
Theorem 1.11 (Vandermonde’s identity)

y l
For positive integers 𝑚, 𝑛, 𝑘 ,

B rna
𝑘     
∑︁ 𝑚 𝑛 𝑚+𝑛
= .
𝑖=0
𝑖 𝑘−𝑖 𝑘

te
1.4 Path walking

In
Example 1.12
John has to go from the same starting point, ( 0, 0) , to the same ending point, ( 5, 5) , by
moving only in the positive 𝑥, 𝑦 directions but this time he is unable to pass through
the construction zone at ( 3, 3) . How many successful paths exist for John?

Walkthrough. We use complimentary counting.

4
MathDash (Last updated 2025-01-14) Bijective Arguments

1. How many paths are there from 𝐴 to 𝑃 ? (Find a bijection!)

2. What about 𝑃 to 𝐵?

3. Extract the answer.

We now introduce one of the most important bijections in combinatorics.

Example 1.13 (Catalan numbers)

Let 𝐶 𝑛 , or the 𝑛th Catalan number, be the number of paths from ( 0, 0) to (𝑛, 𝑛) that
don’t go above the line 𝑦 = 𝑥 . Show that

1 2𝑛
 
𝐶𝑛 = .
𝑛+1 𝑛

s h y
Walkthrough. Let’s count the number of paths from ( 0, 0) to (𝑛, 𝑛+ 1) that stay below the

a l
raised diagonal joining ( 0, 0) and (𝑛, 𝑛+ 1) . We will use the so-called cyclic shift argument.

D n
1. Convince yourself this is equivalent to the problem.

h O
2. Biject the paths from ( 0, 0) to (𝑛, 𝑛 + 1) to a sequence of 𝑛 right and 𝑛 + 1 up moves.

t
Let 𝑠 be one such sequence. How many cyclic permutations of 𝑠 are there? For

a e
example, if 𝑛 = 3 and 𝑠 = 𝑅𝑅𝑅𝑈𝑈𝑈𝑈 , then 𝑈𝑅𝑅𝑅𝑈𝑈𝑈 is a cyclic permutation of 𝑠

s
(we move the 𝑈 at the end of 𝑠 to the front).

M U
3. Prove that exactly 𝑛 + 1 of the cyclic permutations of 𝑠 stay below the raised diag-
onal.

y l
4. Show that the number of paths is therefore

B rna
𝑛 + 1 2𝑛 + 1
 
.
2𝑛 + 1 𝑛

e
Deduce that this is 𝐶 𝑛 .

t
There is an alternate proof counting the set 𝑆 of paths from ( 0, 0) to (𝑛, 𝑛) that go above

In
𝑦 = 𝑥 , which we biject to the set 𝑇 of paths from ( 0, 0) to (𝑛, 𝑛 + 1) . The mapping is done
by finding the first point the path in 𝑆 goes above 𝑦 = 𝑥 , then reflecting the remaining
path across 𝑦 = 𝑥 + 1. In the diagram below, the green and red path combined represent
a path in 𝑆 , and the green and blue path combined represent the corresponding path in
𝑇.

Many problems spawn naturally from Catalan numbers. Thus, a common trick is to
find a bijection to Catalan numbers. Richard Stanley (the father of enumerative combi-
natorics) has 96 pages of such bijections.
5
MathDash (Last updated 2025-01-14) Bijective Arguments

Example 1.14
Compute the number of valid expressions of 𝑛 sets of parentheses. An expression is
valid if there are an equal number of open and close parentheses, and at no point
are there more close parentheses than open parentheses when reading left to right.
For example, (())() is valid, but ()())( is not.

Walkthrough. Let each open parentheses represent a step to the right, and each close
parentheses represent a step up.

1. What does the path of a valid expression look like?

2. Biject to the Catalan numbers.

h
1.5 Symmetry

Example 1.15

a s ly
What is the probability that, after 6 coins are flipped, there are more heads than

D n
tails?

t h O
Walkthrough. Find the probability there are the same number of heads and tails, then

e
exploit symmetry.

Ma s
Example 1.16 (AIME 1983/13)

U
For {1, 2, 3, . . . , 𝑛} and each of its non-empty subsets a unique alternating sum is de-

y l
fined as follows. Arrange the numbers in the subset in decreasing order and then,

B rna
beginning with the largest, alternately add and subtract successive numbers. For
example, the alternating sum for {1, 2, 3, 6, 9} is 9 − 6 + 3 − 2 + 1 = 5 and for {5} it is
simply 5. Find the sum of all such alternating sums for 𝑛 = 7.

e
Walkthrough. Let 𝑆 be a non-empty subset of {1, 2, . . . , 6}, and let 𝑓 (𝑆) be the alternating

t
sum of 𝑆 .

In
1. Find a pairing so that for every 𝑆 , there exists a unique subset 𝑇 of {1, 2, . . . , 7} such
that 𝑓 (𝑆) + 𝑓 (𝑇 ) = 7.

2. Compute the number of pairs and finish.

Example 1.17 (AMC 10A 2018/20)

A scanning code consists of a 7 × 7 grid of squares, with some of its squares colored
black and the rest colored white. There must be at least one square of each color in
this grid of 49 squares. A scanning code is called symmetric if its look does not change
when the entire square is rotated by a multiple of 90◦ counterclockwise around its
center, nor when it is reflected across a line joining opposite corners or a line joining
midpoints of opposite sides. What is the total number of possible symmetric scan-
ning codes?

Walkthrough. Stare at the figure below until it makes sense.

6
MathDash (Last updated 2025-01-14) Bijective Arguments

10 9 8 7 8 9 10
9 6 5 4 5 6 9
8 5 3 2 3 5 8
7 4 2 1 2 4 7
8 5 3 2 3 5 8
9 6 5 4 5 6 9
10 9 8 7 8 9 10

2 Examples

Example 2.1 (AIME 1994/11)

Ninety-four bricks, each measuring 4′′ × 10′′ × 19′′, are to be stacked one on top of

h
another to form a tower 94 bricks tall. Each brick can be oriented so it contributes
4′′ or 10′′ or 19′′ to the total height of the tower. How many different tower heights

s y
can be achieved using all of the ninety-four bricks?

a n l
Clearly, we cannot just count the number of ways to stack the bricks. Indeed, we wish

D
to find a way to have a “representative tower” for each height, so that we do not over-

h O
count. This is the tell-tale sign of a bijection.

t
Walkthrough.

a s e
1. Biject the problem to the number of tower heights achieved using bricks of heights
0, 2, 5. Hint: subtract 4 from the height of each brick, and convince yourself that

M U
this will not affect the answer.

y l
2. Say a tower of height 𝐻 uses at least five blocks of height 2. Show that we may

B rna
make a tower of height 𝐻 with less than five blocks of height 2.

3. Do casework on the number of blocks of height 2.

4. Show that none of these cases overlap.

e
A central theme of this lecture is answering the question: what are we trying to count?

t
In the example that follows, we see that it is not always the most obvious quantity.

In
Example 2.2 (MAT 2021/9)
Alexander is juggling balls. At the start, he has four balls in his left hand: a red ball,
a blue ball, a yellow ball, and a green ball. Each second, he tosses a ball from one
hand to the other. If Alexander juggles for 20 seconds, compute the number of ways
for Alexander to toss the balls such that he has all four balls in his right hand at the
end.

Walkthrough. Let 𝐿 be the number of ways to finish with all four balls in his left hand,
and 𝑅 be the number of ways to finish with all four balls in his right hand. Instead of
calculating 𝑅 directly, we will calculate 𝐿 + 𝑅 and 𝐿 − 𝑅.
1. How many different moves can Alexander perform each second?

2. Show that after 19 seconds, Alexander must have 3 balls in one hand and 1 ball in
the other. Deduce that there is only one way for Alexander to finish with all four
balls in one hand.
7
MathDash (Last updated 2025-01-14) Bijective Arguments

3. Compute 𝐿 + 𝑅.

4. Say Alexander has two balls in each hand at some point during the process. Deduce
that the number of ways for Alexander to finish with all four balls in his left hand
is the same as the number of ways for Alexander to finish with all four balls in his
right hand.

5. What sequences of moves contribute to 𝐿 − 𝑅?

6. Compute 𝐿 − 𝑅 and finish.

We end with another example of the cyclic shifts argument.

Example 2.3 (AMC 10A 2022/24)

h
How many strings of length 5 formed from the digits 0, 1, 2, 3, 4 are there such that
for each 𝑗 ∈ {1, 2, 3, 4}, at least 𝑗 of the digits are less than 𝑗 ? (For example, 02214

s y
satisfies this condition because it contains at least 1 digit less than 1, at least 2 digits

a l
less than 2, at least 3 digits less than 3, and at least 4 digits less than 4. The string
23404 does not satisfy the condition because it does not contain at least 2 digits less

D n
than 2.)

t h O
Walkthrough. Call a string good if it satisfies the condition in the statement. Let 𝑆 be the

a e
set of strings of length 5 formed from the digits 0 through 5.

s
1. Show that the number of good strings does not change when we allow 5 to be a

M U
digit.

y l
2. Let’s build some intuition. Say we have the string 01124. Consider the strings

B rna
formed by adding 𝑘 to each digit then taking modulo 6, where 𝑘 = 0, . . . , 5. For ex-
ample, the set of strings formed from 01124 is {01124, 12235, 23340, 34451, 45502, 50013}.
How many of these strings are good?

3. Try other strings. What do you notice?

te
4. Deduce that the number of good strings is 16 |𝑆| .

In
Remark 2.4 (Parking functions). This is actually a well-known area of combinatorics and can
be bijected to spanning trees.

8
MathDash (Last updated 2025-01-14) Bijective Arguments

3 Problems
There are 136 total points available in this unit, including feedback. Try to complete at
least 21 of the total points.

[2] Required Problem 1 (AIME II 2006/4). Let (𝑎1 , 𝑎2 , 𝑎3 , . . . , 𝑎12 ) be a permutation of

( 1, 2, 3, . . . , 12) for which

𝑎1 > 𝑎2 > 𝑎3 > 𝑎4 > 𝑎5 > 𝑎6 and 𝑎6 < 𝑎7 < 𝑎8 < 𝑎9 < 𝑎10 < 𝑎11 < 𝑎12 .

An example of such a permutation is ( 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12) . Find the number of

such permutations.

[2] Problem 2 (AIME II 2009/6). Let 𝑚 be the number of five-element subsets that can
be chosen from the set of the first 14 natural numbers so that at least two of the five

h
numbers are consecutive. Find the remainder when 𝑚 is divided by 1000.

a s ly
[3] Problem 3 (HMMT February Guts 2011/22). Find the number of ordered triples (𝑎, 𝑏, 𝑐)
of pairwise distinct integers such that −31 ≤ 𝑎, 𝑏, 𝑐 ≤ 31 and 𝑎 + 𝑏 + 𝑐 > 0.

D n
[3] Problem 4 (AIME 1992/12). In a game of Chomp, two players alternately take bites

h O
from a 5-by-7 grid of unit squares. To take a bite, a player chooses one of the remain-

t
ing squares, then removes (“eats”) all squares in the quadrant defined by the left edge

a e
(extended upward) and the lower edge (extended rightward) of the chosen square. For

s
example, the bite determined by the shaded square in the diagram would remove the
shaded square and the four squares marked by ×. (The squares with two or more dotted

M U
edges have been removed form the original board in previous moves.)

y
B rna l
te
In
The objective of the game is to make one’s opponent take the last bite. The diagram
shows one of the many subsets of the set of 35 unit squares that can occur during the
game of Chomp. How many different subsets are there in all? Include the full board and
empty board in your count.

[5] Problem 5 (AIME II 2002/9). Let S be the set {1, 2, 3, . . . , 10}. Find the number of sets
of two non-empty disjoint subsets of S . (Disjoint sets are defined as sets that have no
common elements.)

[3] Problem 6 (AIME II 2008/12). There are two distinguishable flagpoles, and there are
19 flags, of which 10 are identical blue flags, and 9 are identical green flags. Compute
the number of distinguishable arrangements using all of the flags in which each flagpole
has at least one flag and no two green flags on either pole are adjacent.
9
MathDash (Last updated 2025-01-14) Bijective Arguments

[2] Problem 7 (AMC 12A 2021/15). A choir director must select a group of singers from
among his 6 tenors and 8 basses. The only requirements are that the difference between
the number of tenors and basses must be a multiple of 4, and the group must have at
least one singer. Compute the number of different groups that could be selected.
[3] Required Problem 8 (HMMT February 2015/C7). 2015 people sit down at a restaurant.
Each person orders a soup with probability 12 . Independently, each person orders a salad
with probability 12 . What is the probability that the number of people who ordered a soup
is exactly one more than the number of people who ordered a salad?
[3] Problem 9 (AIME 1993/7). Three numbers, 𝑎1 , 𝑎2 , 𝑎3 , are drawn randomly and with-
out replacement from the set {1, 2, 3, . . . , 1000}. Three other numbers, 𝑏1 , 𝑏2 , 𝑏3 , are then
drawn randomly and without replacement from the remaining set of 997 numbers. Com-
pute the probability that, after a suitable rotation, a brick of dimensions 𝑎1 × 𝑎2 × 𝑎3 can
be enclosed in a box of dimensions 𝑏1 × 𝑏2 × 𝑏3 , with the sides of the brick parallel to the

h
sides of the box.

s y
[5] Required Problem 10 (AIME I 2020/9). Let 𝑆 be the set of positive integer divisors of

a l
209 . Three numbers are chosen independently and at random with replacement from

D n
the set 𝑆 and labeled 𝑎1 , 𝑎2 , and 𝑎3 in the order they are chosen. Compute the probability
that both 𝑎1 divides 𝑎2 and 𝑎2 divides 𝑎3 .

t h O
[5] Problem 11 (AIME II 2006/10). Seven teams play a soccer tournament in which each
team plays every other team exactly once. No ties occur, each team has a 50% chance

a e
of winning each game it plays, and the outcomes of the games are independent. In each

s
game, the winner is awarded a point and the loser gets 0 points. The total points are

M
accumilated to decide the ranks of the teams. In the first game of the tournament, team

U
𝐴 beats team 𝐵. Compute the probability that team 𝐴 finishes with more points than

y l
team 𝐵.

B rna
[5] Problem 12 (AMC 10B 2020/25). Let 𝐷(𝑛) denote the number of ways of writing the
positive integer 𝑛 as a product
𝑛 = 𝑓1 · 𝑓2 · · · 𝑓𝑘 ,
where 𝑘 ≥ 1, the 𝑓𝑖 are integers strictly greater than 1, and the order in which the factors

e
are listed matters (that is, two representations that differ only in the order of the factors

t
are counted as distinct). For example, the number 6 can be written as 6, 2 · 3, and 3 · 2,

In
so 𝐷( 6) = 3. What is 𝐷( 96) ?
[3] Problem
13
(AIME I 2017/7). For nonnegative integers 𝑎 and 𝑏 with 𝑎 + 𝑏 ≤ 6, let
6 6 6

𝑇 (𝑎, 𝑏) = 𝑎 𝑏 𝑎+𝑏 . Compute the sum of all 𝑇 (𝑎, 𝑏) , where 𝑎 and 𝑏 are nonnegative
integers with 𝑎 + 𝑏 ≤ 6.
[3] Problem 14 (AIME I 2020/7). A club consisting of 11 men and 12 women needs to
choose a committee from among its members so that the number of women on the com-
mittee is one more than the number of men on the committee. The committee could have
as few as 1 member or as many as 23 members. Compute the number of such committees
that can be formed.
[5] Required Problem 15 (AIME 1986/13). In a sequence of coin tosses, one can keep a
record of instances in which a tail is immediately followed by a head, a head is immedi-
ately followed by a head, and etc. We denote these by TH, HH, and etc. For example, in
the sequence TTTHHTHTTTHHTTH of 15 coin tosses we observe that there are two HH,
three HT, four TH, and five TT subsequences. How many different sequences of 15 coin
tosses will contain exactly two HH, three HT, four TH, and five TT subsequences?
10
MathDash (Last updated 2025-01-14) Bijective Arguments

[5] Problem 16. Prove that for all positive integers 𝑛 and real numbers 0 ≤ 𝑝 ≤ 1, we
have
𝑛  
∑︁ 𝑛 𝑘
𝑘 𝑝 ( 1 − 𝑝) 𝑛−𝑘 = 𝑛𝑝.
𝑘=0
𝑘

[9] Problem 17. Show that the following two problems are equivalent:

• (AIME II 2020/9) While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and
Frank sat in that order in a row of six chairs. During the break, they went to the
kitchen for a snack. When they came back, they sat on those six chairs in such a
way that if two of them sat next to each other before the break, then they did not
sit next to each other after the break. Find the number of possible seating orders
they could have chosen after the break.

h
• (Hertzprung) Find the number of ways to place 6 kings on a 6 × 6 board so that
each row and each column contains exactly one king and no two kings attack each

s y
other.

a l
[9] Problem 18 (IMO 1987/1). Let 𝑝𝑛 (𝑘) be the number of permutations of the set {1, . . . , 𝑛}

D n
which have exactly 𝑘 fixed points, where 𝑛 ≥ 1. Prove that

h O
𝑛

t
∑︁
𝑘 · 𝑝𝑛 (𝑘) = 𝑛!.

e
𝑘=0

a s
[9] Problem 19 (HMMT February 2015/C10). A group of friends, numbered 1, 2, 3, . . . , 16,
take turns picking random numbers. Person 1 picks a number uniformly (at random)

M U
in [ 0, 1] , then person 2 picks a number uniformly (at random) in [ 0, 2] , and so on, with

l
person k picking a number uniformly (at random) in [ 0, 𝑘] . What is the probability that

y
the 16 numbers picked are strictly increasing?

B rna
[9] Problem 20 (Canada MO 2019/3). Let 𝑚 and 𝑛 be positive integers. A 2𝑚 × 2𝑛 grid
of squares is colored in the usual chessboard fashion. Determine the number of ways to
place 𝑚𝑛 counters on the white squares, at most one counter per square, so that no two

e
counters are diagonally adjacent.

t
[5] Problem 21 (AIME I 2018/10). The wheel shown below consists of two circles and

In
five spokes, with a label at each point where a spoke meets a circle. A bug walks along
the wheel, starting at point 𝐴. At every step of the process, the bug walks from one
labeled point to an adjacent labeled point. Along the inner circle the bug only walks in a
counterclockwise direction, and along the outer circle the bug only walks in a clockwise
direction. For example, the bug could travel along the path 𝐴𝐽 𝐴𝐵𝐶𝐻𝐶𝐻𝐼 𝐽 𝐴, which has
10 steps. Compute the number of paths with 15 steps that begin and end at point 𝐴.

𝐼 𝐴 𝐹
𝐵 𝐸
𝐶 𝐷

𝐻 𝐺
11
MathDash (Last updated 2025-01-14) Bijective Arguments

[3] Problem 22 (HMMT February 2023/C3). Richard starts with the string HHMMMMTT. A
move consists of replacing an instance of HM with MH, replacing an instance of MT with
TM, or replacing an instance of TH with HT. Compute the number of possible strings he
can end up with after performing zero or more moves.

[5] Problem 23 (CMIMC 2018/C9). Compute the number of rearrangements 𝑎1 , 𝑎2 , . . . , 𝑎2018

of the sequence 1, 2, . . . , 2018 such that 𝑎𝑘 > 𝑘 for exactly one value of 𝑘.

[3] Problem 24 (CMIMC 2020/C5). Seven cards numbered 1 through 7 lay stacked in a pile
in ascending order from top to bottom (1 on top, 7 on bottom). A shuffle involves picking
a random card of the six not currently on top, and putting it on top. The relative order of
all the other cards remains unchanged. Find the probability that, after 10 shuffles, 6 is
higher in the pile than 3.

[5] Problem 25 (CMIMC 2014/C10). An up-right path from (𝑎, 𝑏) ∈ R2 to (𝑐, 𝑑) ∈ R2 is a

h
finite sequence (𝑥1 , 𝑦𝑧 ), . . . , (𝑥𝑘 , 𝑦𝑘 ) of points in R2 such that (𝑎, 𝑏) = (𝑥1 , 𝑦1 ), (𝑐, 𝑑) =

s y
(𝑥𝑘 , 𝑦𝑘 ) , and for each 1 ≤ 𝑖 < 𝑘 we have that either (𝑥𝑖+1 , 𝑦 𝑦+1 ) = (𝑥𝑖 + 1, 𝑦𝑖 ) or

a l
(𝑥𝑖+1 , 𝑦𝑖+1 ) = (𝑥𝑖 , 𝑦𝑖 + 1) . Two up-right paths are said to intersect if they share any point.
Find the number of pairs (𝐴, 𝐵) where 𝐴 is an up-right path from ( 0, 0) to ( 4, 4) , 𝐵 is

D n
an up-right path from ( 2, 0) to ( 6, 4) , and 𝐴 and 𝐵 do not intersect.

h O
[5] Problem 26 (Hamming codes). I have an 𝑛 × 𝑛 grid, and I will color each square in

t
the grid either red or blue. What is the probability that there are an odd number of red

a e
squares in each column and each row?

s
[3] Problem 27 (LMT Spring 2019/T15). A bored and hungry Goldilocks finds an infinite

M U
number of raisins in her pocket. On the kitchen table lies an infinite number of bowls of

l
porridge. She labels the bowls, numbering the leftmost bowl 1, the second leftmost bowl

y
2, and so on. She then distributes her raisins, starting by adding 1 raisin to Bowl 1. Next,

B rna
if she adds 𝑟 raisins to Bowl 𝑏, then she will add 𝑟 raisins to Bowl 2𝑏, and 𝑟 + 1 raisins to
Bowl 2𝑏 + 1. Into how many of the 22019 leftmost bowls of porridge will Goldilocks add
exactly 2017 raisins?

e
[2] Required Problem 28. How many subsets of the set 𝑆 = {1, 2, . . . , 𝑛} are there such

t
that the sum of the elements in the subset is at least half of the sum of all the elements
in 𝑆 ?

In
[2] Problem 29 (AMC 12B 2022/17). How many 4 × 4 arrays whose entries are 0s and 1s
are there such that the row sums (the sum of the entries in each row) are 1, 2, 3, and 4, in
some order, and the column sums (the sum of the entries in each column) are also 1, 2, 3,
and 4, in some order? For example, the array


 1 1 1 0 


 0 1 1 0 


 1 1 1 1 


 0 1 0 0 

satisfies the condition.

[9] Problem 30 (IMC 2015/8). Consider all 2626 words of length 26 in the Latin alphabet.
Define the weight of a word as 𝑘+1 1 , where 𝑘 is the number of letters not used in this word.
Prove that the sum of the weights of all words is 375 .

12
MathDash (Last updated 2025-01-14) Bijective Arguments

[1] Feedback. Please let me know what you thought of this unit! In particular, I would
like to know:

• which problems you thought were nice, too easy/difficult, helpful, etc.;

• what needs clarification; and

• how this unit could be improved.

s h y
D a n l
a t h e O
M U s
y
B rna l
te
In

13