HMMT February 2024

February 17, 2024

Combinatorics Round
1. Compute the number of ways to divide a 20 × 24 rectangle into 4 × 5 rectangles. (Rotations and
reflections are considered distinct.)
Proposed by: Derek Liu
Answer: 6
Solution: For convenience, say the edge of length 20 is vertical.
Consider some vertical line inside the rectangle. It must pass through rectangles of some heights adding
to 20. In particular, these heights correspond to ways to add up to 20 with fours and fives, which is
either 4 + 4 + 4 + 4 + 4 or 5 + 5 + 5 + 5. These options correspond to columns of rectangles with width
5 or 4, respectively. In particular, we need to span the width of the original 20 × 24 rectangle using
these columns, meaning that we can just count the number of ways to add to 24 with fours and fives.

4 4 4 4 4 4 4 5 5 5 5

There are two ways to do this: either 4 + 4 + 4 + 4 + 4 + 4 or 4 + 5 + 5 + 5 + 5. Considering the orders

in which the second sum can be written, we get an answer of 1 + 5 = 6 .

2. A lame king is a chess piece that can move from a cell to any cell that shares at least one vertex with
it, except for the cells in the same column as the current cell.
A lame king is placed in the top-left cell of a 7 × 7 grid. Compute the maximum number of cells it can
visit without visiting the same cell twice (including its starting cell).
Proposed by: Arul Kolla
Answer: 43
Solution: Color the columns all-black and all-white, alternating by column. Each move the lame king
takes will switch the color it’s on. Assuming the king starts on a black cell, there are 28 black and 21
white cells, so it can visit at most 22 + 21 = 43 cells in total, which is easily achievable:
3. Compute the number of ways there are to assemble 2 red unit cubes and 25 white unit cubes into a
3 × 3 × 3 cube such that red is visible on exactly 4 faces of the larger cube. (Rotations and reflections
are considered distinct.)
Proposed by: Albert Wang
Answer: 114
Solution:
We do casework on the two red unit cubes; they can either be in a corner, an edge, or the center of
the face.
• If they are both in a corner, they must be adjacent – for each configuration, this corresponds to
an edge, of which there are 12.

• If one is in the corner and the other is at an edge, we have 8 choices to place the corner. For the
edge, the red edge square has to go on the boundary of the faces touching the red corner square,
and there are six places here. Thus, we get 8 · 6 = 48 configurations.

• If one is a corner and the other is in the center of a face, we again have 8 choices for the corner and
3 choices for the center face (the faces not touching the red corner). This gives 8·3 = 8+8+8 = 24
options.

• We have now completed the cases with a red corner square! Now suppose we have two edges: If
we chose in order, we have 12 choices for the first cube. For the second cube, we must place the
edge so it covers two new faces, and thus we have five choices. Since we could have picked these
edges in either order, we divide by two to avoid overcounting, and we have 12 · 5/2 = 30 in this
case.
 Now, since edges and faces only cover at most 2 and 1 face respectively, no other configuration works.
Thus we have all the cases, and we add: 12 + 48 + 24 + 30 = 114 .

4. Sally the snail sits on the 3 × 24 lattice of points (i, j) for all 1 ≤ i ≤ 3 and 1 ≤ j ≤ 24. She wants to
visit every point in the lattice exactly once. In a move, Sally can move to a point in the lattice exactly
one unit away. Given that Sally starts at (2, 1), compute the number of possible paths Sally can take.
Proposed by: Isabella Zhu
Answer: 4096

Solution 1:
On her first turn, Sally cannot continue moving down the middle row. She must turn either to the
bottom row or the top row. WLOG, she turns to the top row, and enters the cell (3, 1) and we will
multiply by 2 later. Then, we can see that the path must finish in (1, 1). So, we will follow these two
branches of the path, one for the start and one for the end. These branches must both move one unit
up, and then one of the paths must move into the center row. Both branches move up one unit, and
then the path in the middle row must go back to fill the corner. After this, we have exactly the same
scenario as before, albeit with two fewer rows. So, for each additional two rows, we have a factor of
two and thus there are 212 = 4096 paths.
Solution 2:
We solve this problem for a general 3 by 2n grid.
On her first turn, Sally cannot continue moving down the middle row. She must turn either to the
topmost row or the bottommost row. WLOG, she turns to the top row.
Suppose Sally returns to the middle row k times. There are k ”blocks”. However, 2k of the squares are
already occupied by Sally’s row shifts. Thus, we are solving

2(x1 + x2 + . . . xk ) = 2(n − k).

There are
n (
∑ )
n−k+k−1
= 2n−1
k−1
k=1

solutions. We multiply by 2 to get 2n .

For n = 12, this evaluates to 212 = 4096 .
5. The country of HMMTLand has 8 cities. Its government decides to construct several two-way roads
between pairs of distinct cities. After they finish construction, it turns out that each city can reach
exactly 3 other cities via a single road, and from any pair of distinct cities, either exactly 0 or 2 other
cities can be reached from both cities by a single road. Compute the number of ways HMMTLand
could have constructed the roads.
Proposed by: Derek Liu
Answer: 875
Solution: Let the cities be numbered 1, 2, 3, 4, 5, 6, 7, 8. WLOG, 1 is connected to 2, 3, and 4. First
suppose 2 and 3 are connected; then 3 and 1 share a second common neighbor, which must be 4 (as
1 is not connected to anything else). Likewise 2 and 4 are connected, and so 5, 6, 7, 8 are pairwise
connected as well, so the graph consists of two disjoint copies of K4 :

1 2 5 6

4 3 8 7

()
1 8
There are 2 4 = 35 ways to partition the 8 vertices into two groups of 4, so there are 35 such graphs.
Otherwise, none of 2, 3, 4 are connected to each other. Then 2 and 3 must share a common neighbor, as
must 3 and 4, and 2 and 4. If these are the same neighbor, this vertex would share all three neighbors
with 1, so they must be pairwise distinct. The last vertex must then be connected to these three,
creating a cube graph.

4 5

1 3

8 6

2 7

8!
A cube has 48 symmetries, so the number of such graphs is 48 = 840.
The total is 35 + 840 = 875 .

6. In each cell of a 4 × 4 grid, one of the two diagonals is drawn uniformly at random. Compute the
probability that the resulting 32 triangular regions can be colored red and blue so that any two regions
sharing an edge have different colors.
Proposed by: Derek Liu
1
Answer: 512

Solution: Give each cell coordinates from (1, 1) to (4, 4).

Claim. The grid has a desired coloring if and only if every vertex not on the boundary meets an even
number of edges and diagonals.
Proof. If this were not the case, the odd number of regions around the vertex would have to alternate
between the two colors, which is clearly impossible. In the event that every vertex has an even number
of incident edges, it is not hard to show that the grid is always colorable.
 We claim the diagonals drawn in the cells of form (1, a) and (a, 1) for 1 ≤ a ≤ 4 uniquely determine
the rest (for a valid coloring to exist). Indeed, given the diagonals for any three cells around a vertex,
we can uniquely determine the fourth one using the parity in the claim above. If (1, 1), (1, 2), (2, 1)
are fixed, so is (2, 2); likewise so are (2, 3) and (2, 4), etc. until the whole grid is fixed.

The solid lines force the dotted lines as described above.

Thus, once the seven cells along the top row and leftmost column are determined, the remaining nine
1
have a 219 = chance of being selected in a way that admits a coloring.
512

7. There is a grid of height 2 stretching infinitely in one direction. Between any two edge-adjacent cells
of the grid, there is a door that is locked with probability 12 independent of all other doors. Philip
starts in a corner of the grid (in the starred cell). Compute the expected number of cells that Philip
can reach, assuming he can only travel between cells if the door between them is unlocked.

···
···
···
Proposed by: Jacob Paltrowitz
32
Answer: 7

Solution: For clarity, we will number our grid, with (0,0) being the corner that Philip starts in, and
the grid stretching in the positive x direction, i.e. all elements of the grid are of the form (x, y), with
y ∈ {0, 1} and x ∈ N.
We will use recursion and casework. Let A be the expected number of reachable cells given that the
door between (0, 0) and (0, 1) is unlocked, and B be the expected number of cells given that door is
closed. Since that door is locked 12 of the time, our answer is A+B
2 .
We can write recurrence relations by considering the different configurations of the doors in the first 4
cells.
For the sake of writing, let W be the (0, 0) − (0, 1) door, X be the (0, 0) − (1, 0) door, Y be the
(0, 1) − (1, 1) door, and Z be the (1, 0) − (1, 1) door.
Let’s start with the case where W is unlocked and compute A:

Y Y Y

W ? W ? W ?

X X X
 Case 1: W is unlocked. Shaded cells represent inaccessible cells, and the arrows show Philip’s
movements between cells.

• If X, Y are both locked, then Philip can reach exactly 2 rooms. This occurs with probability 14 .
• If both of X, Y are unlocked, then we have exactly the same case of A, except with the ability to
reach two extra cells. This occurs with probability 14 .
• If exactly one of X, Y are unlocked, we have back to the original case, except with the ability to
access two more cells, which occurs with probability 12 .

So, we get the equation:

( )
1 1 1 A+B
A = (2) + (A + 2) + +2
4 4 2 2

Now, let’s consider when W is locked.

Y Y Y

W ? W ? W ?

X X X

Case 2: W is locked.

• If X is locked, Philip can only reach one cell. This occurs with probability 12 .
• If X is unlocked and Y is locked, we have exactly the original problem, except with the ability to
reach one more cell. This occurs with probability 14 .
• In the case where X is unlocked and Y is unlocked, this is the same as the original configuration,
except with the ability to reach one extra cell (the start) and possibly the cell at (0, 1).
Now, let’s compute the probability that Philip can reach (0, 1) in this case. This is the probability
that Philip can reach (1, 1) since Y is unlocked. We can compute that the probability that Philip
can reach (1, 1) from (1, 0) is equal to
∑∞
1
23n+1
n=0

by looking at the minimum distance Philip has to go to the right before getting back to (1, 1).
This is a geometric series with sum 74 . So, in this case, on average Philip can reach 1 + 47 more
cells than the original case. This case occurs with probability 14 .

So, we can write the equation:

( ) ( )
1 1 A+B 1 A+B 4
B = (1) + +1 + +1+
2 4 2 4 2 7

40 24 A+B 32
Solving the system of these two linear equations, we get A = 7 ,B = 7 and 2 = .
7
8. Rishabh has 2024 pairs of socks in a drawer. He draws socks from the drawer uniformly at random,
without replacement, until he has drawn a pair of identical socks. Compute the expected number of
unpaired socks he has drawn when he stops.
Proposed by: Rishabh Das
42024
Answer: (4048) − 2
2024

Solution 1: We solve for the expected number of total socks drawn and subtract two at the end.
Let En be the expected number of socks drawn for n pairs of socks, so that E1 = 2. Suppose there
are n pairs of socks, Rishabh continued to draw socks until the drawer was empty, and without loss of
generality let the last sock drawn be red. If we ignore the two red socks, the process is equivalent to
drawing from a drawer with n − 1 pairs of socks. Let k be the number of socks drawn until a pair of
k
identical socks is found, after ignoring the two red socks. Then the first red sock has probability 2n−1
of being before this stopping point, so the expected value is k + 2n−1 = k · 2n−1 . Since the expected
k 2n

value of k is En−1 , we have

2n
En = · En−1 .
2n − 1
Applying this recurrence, we get
(2n)!! 2n · n! 4n · (n!)2 4n
En = = = = (2n) .
(2n − 1)!! (2n − 1)!! (2n)! n

42024
Subtracting two and plugging in n = 2024 gives a final answer of (4048) − 2 .
2024

Solution 2: Let P (k) denote the probability that Rishabh draws more than k socks. We compute
P (k) for all 0 ≤ k ≤ 2024 (and note P (k) = 0 for larger k).
The number of ways to draw k socks, none identical to each other, is
2024!
4048 · 4046 · · · · (4050 − 2k) = 2k · ,
(2024 − k)!
while the total number of ways to draw k socks is
4048!
4048 · 4047 · · · (4049 − k) = .
(4048 − k)!
Thus,
( )
2k · 2024!
(2024−k)! 2024! 2k (4048 − k)! 1 4048 − k
P (k) = = · = (4048) · 2k .
4048!
(4048−k)!
4048! (2024 − k)! 2024
2024
The expected number of socks drawn is
∑
2024 ( )
1 4048 − k
P (0) + P (1) + · · · + P (2024) = (4048) 2 k
.
2024
2024
k=0

This sum is equivalent to Putnam 2020 A2. We claim that it is equal to 42024 . We do this via a
counting argument: we count how many ways there are to choose at least half of the elements from
4049
the set {1, 2, . . . , 4049}. On the one hand that is 2 2 = 42024 . On the other hand, letting k + 1 be
(4048−k)
the 2025th largest element chosen, there are 2024 ways to choose the elements larger than it, and
2k ways to choose the elements smaller than it. Varying k, we get
∑
2024 ( )
k 4048 − k
2 = 42024 .
2024
k=0
 This means the expected number of socks is
42024
(4048) ,
2024

42024
and subtracting two for the matching pair gives (4048) − 2 .
2024

9. Compute the number of triples (f, g, h) of permutations on {1, 2, 3, 4, 5} such that

f (g(h(x))) = h(g(f (x))) = g(x),

g(h(f (x))) = f (h(g(x))) = h(x), and
h(f (g(x))) = g(f (h(x))) = f (x)

for all x ∈ {1, 2, 3, 4, 5}.

Proposed by: Rishabh Das
Answer: 146
Solution: Let f g represent the composition of permutations f and g, where (f g)(x) = f (g(x)) for all
x ∈ {1, 2, 3, 4, 5}.
Evaluating f ghf h in two ways, we get

f = gf h = (f gh)f h = f ghf h = f (ghf )h = f hh,

so hh = 1. Similarly, we get f , g, and h are all involutions. Then

f gh = g =⇒ f g = gh,

so f g = gh = hf . Let x := f g = gh = hf . Then

x3 = (f g)(gh)(hf ) = 1.

We can also show that f g = gh = hf along with f, g, h being involutions is enough to recover the
initial conditions, so we focus on satisfying these new conditions.
() ( 5 )
If x = 1, then f = g = h is an involution. There are 1 + 52 + 12 2,2,1 = 26 involutions, so this case
gives 26 solutions.
Suppose x ̸= 1. Then since x3 = 1, x is composed of a 3-cycle and two fixed points, of which there are
20 choices. WLOG x = (1 2 3). It can be checked that {1, 2, 3} must map to itself for all of f, g, h and
also {4, 5}. We can either have all of f, g, h map 4 and 5 to themselves or each other. Restricted to
{1, 2, 3}, they are some rotation of (1 2), (2 3), (1 3). Each of the 20 cases thus gives 2 · 3 = 6 triples, so
overall we get 20 · 6 = 120.
The final answer is 26 + 120 = 146 .

10. A peacock is a ten-digit positive integer that uses each digit exactly once. Compute the number of
peacocks that are exactly twice another peacock.
Proposed by: Albert Wang
Answer: 184320
Solution:
We begin with the following observation:

Claim 1. Let x be a peacock. Then, 2x is a peacock if and only if:

 • the multiplication x · 2 uses five carries,
• each of the pairs of digits (0, 5), (1, 6), (2, 7), (3, 8), (4, 9) receives exactly one carry.
• The leading digit is not 5, 6, 7, 8, 9.

Proof. After the multiplication of x · 2, we will have a ten digit number. Let’s first consider the output
without carrying. It consists of the digits 0, 2, 4, 6, 8 twice each, occupying positions where pairs of
digits (0, 5), (1, 6), (2, 7), (3, 8), (4, 9) were in x. However, we guaranteed that one digit from each pair
received a carry, meaning all ten digits are present after adding in the carries.

We will now biject all peacocks to the following combination of objects:

• a queue of low digits 0, 1, 2, 3, 4, in any order with the constraint that 0 is not first,
• a queue of high digits 5, 6, 7, 8, 9, in any order, and
• of each of the pairs of digits (0, 5), (1, 6), (2, 7), (3, 8), (4, 9) mark one of them to receive a carry,
except we are not allowed to mark the final digit in the high queue.
We construct a correspondence from these objects to peacocks by accumulating digits to an initially
empty string. We’ll say that we poll a queue by popping its front entry and appending it to the end of
this string. First, poll the low queue. Then, if we have just polled a marked digit, poll the high queue;
otherwise, poll the low queue. We repeat this until all queues are emptied.
As an example of this process, let our low queue be 1, 4, 0, 2, 3, our high queue be 8, 5, 9, 6, 7, and mark
the digits 0, 1, 2, 3, 9 marked to receive a carry. Our steps are as follows:
• Poll the low queue, so that our string is now 1.
• Since 1 was marked to receive a carry, we poll the high queue, making our string 18.
• Since 8 was not marked, we poll the low queue to reach 184.
• Since 4 was not marked, we poll the low queue to reach 1840.
• Since 0 was marked, we poll the high queue to reach 18405.
• etc.
In the end, we will construct the peacock 1840529637, which is the one shown earlier to work.

Claim 2. Any string of digits x constructed through this process will be a peacock that satisfies
the constraints outlined in Claim 1.

Low queue 1 4 0 2 3

High queue 8 5 9 6 7

The order in which digits get polled to construct 1840529637; note the 4 connected components in the
high queue. The circled digits are those that have been marked for carrying.

Proof. We first argue that all digits end up being polled. In particular, if a high digit is marked, let’s
connect it by an edge to the digit on its right (using the requirement that the last digit is not marked).
If h of the high digits are marked, then we will have 5 − h connected components among these high
digits. However, we then have 5 − h marked digits in the low queue, and every time we poll a marked
low digit we will end up polling all digits from the next connected component in the high queue.
So, all digits end up being polled. Notice that our marked digits will always be followed immediately
by a high digit, satisfying the first and second conditions of the claim. As we do not start with a high
digit, the third constraint is satisfied. Therefore any peacock x output by this process will also have
2x a peacock.

Since we always use all the digits, this process is evidently injective. To map from peacocks back
to these sequences of digits, we can just let the queues be the order of appearances of the low and high
digits in the peacock, and mark the carried digits accordingly. Indeed, we notice that this mapping is
also injective.
Using this bijection, we just need to find the number of initial settings of the queues and marked digits.
There are 4 · 4! ways to order the low number queue. There are then 5! ways to order the high number
queue. Finally, of each of the four pairs of digits not inluding the final high digit, there are 24 ways to
mark them. This gives an answer of

4 · 4! · 5! · 24 = 184320 .