Combinatorics A Solutions

1. In the country of PUMaC-land, there are 5 villages and 3 cities. Vedant is building roads
between the 8 settlements according to the following rules:
a) There is at most one road between any two settlements;
b) Any city has exactly three roads connected to it;
c) Any village has exactly one road connected to it;
d) Any two settlements are connected by a path of roads.
In how many ways can Vedant build the roads?
Proposed by Sunay Joshi
Answer: 90
If a village is connected to another village, then neither village is connected to the rest of the
settlements, so this cannot be possible. Thus, every village is connected to a city. If some city
is connected to three villages, then these four settlements cannot be connected to the other
four, which means this is impossible. Thus, each city is connected to at most two villages,
which is only possible if two cities are connected to two villages and one city is connected to
one village. The only possible such configuration has the one-village city connected to both
other cities. There are 3 ways to choose which city is the one-village city, then 5 ways to
choose which village is connected to this city. Finally, there are 42 = 6 ways to choose the

two villages connected to one of the other cities. Thus, our total number of possibilities is
3 · 5 · 6 = 90.
2. Ten evenly spaced vertical lines in the plane are labeled ℓ1 , ℓ2 , . . . , ℓ10 from left to right. A set
{a, b, c, d} of four distinct integers a, b, c, d ∈ {1, 2, . . . , 10} is squarish if some square has one
vertex on each of the lines ℓa , ℓb , ℓc , and ℓd . Find the number of squarish sets.
Proposed by Ben Zenker
Answer: 50
Without loss of generality, assume that a < b < c < d. Then, it is easy to see that {a, b, c, d} is
squarish if and only if the distance between ℓa and ℓb equals the distance between ℓc and ℓd . In
other words, we must count the number of subsets {a, b, c, d} of {1, 2, . . . , 10} with d−c = b−a.
To do this, we proceed by casework on k = d − c.
• If k = 1, we find that for each value of d, the maximum possible value for a is d − 3, so
there are d − 3 possible combinations of the four numbers. Then, d ranges from 4 to 10
inclusive, for a total of 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 combinations.
• If k = 2, each value of d gives d − 5 possible combinations. Then, d ranges from 6 to 10
inclusive, for a total of 5 + 4 + 3 + 2 + 1 = 15 combinations.
• If k = 3, each value of d gives d − 7 possible combinations. Then, d ranges from 8 to 10
inclusive, for a total of 3 + 2 + 1 = 6 combinations.
• If k = 4, there is only 1 combination a = 1, b = 5, c = 6, d = 10.
Summing yields a total of 28 + 15 + 6 + 1 = 50 sets {a, b, c, d}.
3. Randy has a deck of 29 distinct cards. He chooses one of the 29! permutations of the deck
and then repeatedly rearranges the deck using that permutation until the deck returns to its
original order for the first time. What is the maximum number of times Randy may need to
rearrange the deck?

1
 Proposed by Aditya Gollapudi and Owen Yang
Answer: 2520
Every permutation can be decomposed into disjoint cycles, so the number of times Randy
shuffle the deck for a given permutation is equal to the least common multiple of the lengths of
these cycles. Thus, we want to maximize the LCM of these lengths under the constraint that
the lengths sum to 29. Since length 1 cycles do not increase the LCM, we may instead assume
that the lengths are greater than one and have sum at most 29 (which we can compensate for
by creating many cycles of length 1). We may also assume that these lengths are relatively
prime, since removing a common factor from one of the lengths does not change the LCM and
decreases the total sum.
If we have three cycle lengths that are not equal to 1, say a, b, c, then by AM-GM we have
lcm(a, b, c) = abc ≤ ( a+b+c
3 )3 < 103 = 1000. Similar proofs show that we cannot have only
one or two cycle lengths. On the other hand, if we have five cycle lengths not equal to 1,
then the set of 5 relatively prime numbers with smallest sum is 2, 3, 5, 7, 11 which has sum 28,
which has LCM 2310. Any other set of 5 relatively prime numbers has a sum larger than 29.
Furthermore, the smallest sum of 6 or more relatively prime numbers is more than 29.
Thus, we need only consider sets of four cycle lengths; call them a, b, c, d. Note that 5 + 7 + 8 +
9 = 29 and these four numbers have LCM 2520. Since a ̸= b ̸= c ̸= d and each number is as close
to the mean 294 as possible, the only other possible maximum is at {a, b, c, d} = {5, 6, 8, 10},
which gives a smaller LCM. Thus, the answer is 2520.
4. Let Cn denote the n-dimensional unit cube, consisting of the 2n points

{(x1 , x2 , . . . , xn )|xi ∈ {0, 1} for all 1 ≤ i ≤ n}.

A tetrahedron is equilateral if all six side lengths are equal. Find the smallest positive integer
n for which there are four distinct points in Cn that form a non-equilateral tetrahedron with
integer side lengths.
Proposed by Ryan Alweiss
Answer: 11
Note that the square of the Euclidean distance between any two points in Cn equals the
Hamming distance dH between the points, which is defined as dH (x, y) = |{i | 1 ≤ i ≤ n, xi ̸=
yi }|. Note that dH (x, y) + dH (y, z) ≥ dH (x, z) for all x, y, z ∈ Cn .
I claim that if A and B are vertices of the tetrahedron, then dH (A, B) > 1. If not, then given
a third vertex z of the tetrahedron, dH (z, x) and dH (z, y) are two squares that differ by 1. The
only such squares are 0 and 1, which implies that either z = x or z = y, which is impossible.
Therefore, we have dH (x, y) ≥ 4. We cannot have n < 9, because otherwise the only possible
integer side length would be 2 and the tetrahedron would be equilateral.
For a construction when n = 11, consider the vertices given by (0, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1), (1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1), (1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0).
It suffices to rule out any possibilities for n = 9 and n = 10. Since one of the side lengths of the
tetrahedron must be 3, we must have that dH (A, B) = 9 for some points A, B ∈ Cn . Thus, for
any other vertex C, we cannot have dH (A, C) = dH (B, C) = 4 because dH (A, C)+dH (C, B) ≥
dH (A, B) = 9. Since the only other possible side length is 9, we can assume without of loss
of generality that dH (A, C) = 9. If n = 9, then there is exactly one point with Hamming
distance 9 away from A, which implies that B = C, a contradiction. If n = 10, then B and C
must have at least 9 + 9 − 10 = 8 coordinates in common, which means they have Hamming
distance at most 2. But we know that dH (B, C) ≥ 4, which is a contradiction.
It follows that n = 11 is minimal.

2
5. An n-folding process on a rectangular piece of paper with sides aligned vertically and horizon-
tally consists of repeating the following process n times:
• Take the piece of paper and fold it in half vertically (choosing to either fold the right side
over the left, or the left side over the right).
• Rotate the paper 90◦ degrees clockwise.
A 10-folding process is performed on a piece of paper, resulting in a 1-by-1 square base consist-
ing of many stacked layers of paper. Let d(i, j) be the Euclidean distance between the center
of the ith square from the top and the center of the jth square from the top before the paper
1023
P
was folded. Determine the maximum possible value of d(i, i + 1).
i=1
Proposed by Frank Lu
Answer: 14043
We will determine the answer by inducting on n, the index of the folding process that results
in a 1-by-1 square. Let Sn be the answer for n, so that our answer is S10 . Note that S1 = 1
since we have two adjacent squares, whose centers are clearly 1 apart.
It is easy to see that S1 = 1, as we only have one pair of consecutive labels, and they are
adjacent. Now, consider a piece of paper P such that, after performing a k + 1-folding process,
we get a 1-by-1 square. Let Q be another piece of paper with half the size of P , so that Q is
identical to the top of P after the first step in the folding process. Perform the same remaining
k steps in the folding process on both P and Q, label the ith square from the top with i, then
unfold P and Q k times, so that Q is completely unfolded and P is still folded once.
By preserving the orientations of P and Q and placing Q directly over P , each square labeled
a in Q is directly over the squares labeled 2a − 1 and 2a in P . Furthermore, considering
consecutive squares a and a + 1 on Q, if we flip P so that squares 2a − 1 and 2a are on opposite
halves of the fold, and squares 2a and 2a + 1 are on the same half of the fold. Thus, the
distance between the centers of squares 2a and 2a + 1 in P is the same as the distance between
the centers of squares a and a + 1 in Q, and the distance between the centers of squares 2a − 1
and 2a is twice the distance from the center of square a in Q to the edge corresponding to the
fold.
P2k+1 −1
Note that Sk+1 = i=1 d(i, i + 1) can be split up into two sums, one for all terms where
i is odd and one for all terms where i is even. The sum where i is even is just Sk , and the
sum where i is odd is twice the sum of the distances from all centers of squares to the edge
k k
of the fold. Since Q has dimensions 2⌊ 2 ⌋ by 2⌈ 2 ⌉ , and the fold is the edge of Q with length
k
k k P2⌊ 2 ⌋ k k k k k
2⌈ 2 ⌉ , we have that this sum is 2 · 2⌈ 2 ⌉ j=1 2j−1
2 = 2⌈ 2 ⌉ (2⌊ 2 ⌋ )2 = 2⌈ 2 ⌉+2⌊ 2 ⌋ = 2k+⌊ 2 ⌋ . Thus,
k
Sk+1 = Sk + 2k+⌊ 2 ⌋ .
P9 j P9 j P4
Starting from S1 = 1, we see that S10 = 1 + j=1 2j+⌊ 2 ⌋ = 3 + j=2 2j+⌊ 2 ⌋ = 3 + l=1 23l +
P4 P4 15
−1
23l+1 = 3 + 3 l=1 23l = 3 l=0 23l . This is 3 · 223 −1 = 3 · 32767
7 = 3 · 4681 = 14043. (In
particular, it doesn’t matter which sides were folded over at each step, the sum is always the
same!)
6. Fine Hall has a broken elevator. Every second, it goes up a floor, goes down a floor, or stays
still. You enter the elevator on the lowest floor, and after 8 seconds, you are again on the lowest
floor. If every possible such path is equally likely to occur, the probability you experience no
stops is ab , where a, b are relatively prime positive integers. Find a + b.
Proposed by Adam Huang
Answer: 337

3
 Suppose there are u ups, d downs, and s seconds at which the elevator stays still. Since the
elevator returns to its original height, u = d. Since 8 seconds elapse, u + d + s = 2u + s = 8.
It is clear that s is even, so s ∈ {0, 2, 4, 6, 8}, and u = d = 8−s
2 . We do casework based on the
value of s.
Given a path with s stops, delete all seconds at which the elevator stays still to obtain a
“reduced” path. The resulting path corresponds to a walk in the u-d plane by sending each up
step to (1, 0) and each down step to (0, 1), such that the walk goes from (0, 0) to ( 8−s 8−s
2 , 2 )
without crossing the line u = d. The number of such paths is the Catalan number C 8−s . Now,
2
we count how many ways there are to insert the stops into the path. Suppose we insert xi
stops before the i-th move in the reduced path, as well as x9−s after the last move. We must
count the number of
solutions to x1 + . . . + x9−s = s over the nonnegative integers. By stars
8
and bars, this is 8−s .
We can explicitly compute that P C0 = 1, C1 8=
1, C2 = 2, C3 = 5, C4 = 14. Then, the total
number of possible paths is s∈{0,2,4,6,8} 8−s C 8−s = 323. The number of paths with no
2
stops is simply the term corresponding to s = 0, namely 88 C4 = 14. It follows that the


14
desired probability is 323 , so our answer is 323 + 14 = 337.
7. Kelvin has a set of eight vertices. For each pair of distinct vertices, Kelvin independently
draws an edge between them with probability p ∈ (0, 1). A set S of four distinct vertices is
called good if there exists an edge between v and w for all v, w ∈ S with v ̸= w. The variance
of the number of good sets can be expressed as a polynomial f (p) in the variable p. Find the
sum of the absolute values of the coefficients of f (p).
(The variance of random variable X is defined as E[X 2 ] − E[X]2 .)
Proposed by Sunay Joshi
Answer: 7420
For convenience, let n = 8 and let X denote the number of good subsets. Note that X =
P
|S|=4 IS , where IS denotes the indicator random variable that S is a good subset, and where
the sum runs over all subsets of size 4. Writing Var(X) = Cov(X, X) and expanding using
bilinearity, we find
X X
Var(X) = Var(IS ) + 2 Cov(IS , IT ),
|S|=4 |S|,|T |=4,S̸=T

where the second sum runs over all pairs of distinct sets S, T of size 4. Since Var(IS ) =
P(S good)−P(S good)2 and since P(S good) = p6 , we have Var(IS ) = p6 −p12 . We now consider
the second sum. Note that Cov(IS , IT ) = P(S and T good) − P(S good)P(T good). From the
12
above, this reduces
1 T good) − p . If |S ∩ T | = 2, then P(S and T good) =

to
P(S and p11 ,
n n−2 n−4 9
and there are 2 · 2 such pairs. If |S ∩ T | = 3, then P(S and T good) = p , and
n n−3


2 2
there are 3 2 such pairs. Plugging this into our sum, we find
         
n 6 12 n n−2 n−4 1 11 12 n n−3 9 12
Var(X) = (p − p ) + 2 · (p − p ) + (p − p )
4 2 2 2 2 3 2
Rewriting, we find the polynomial
            
12 n n n−2 n−4 n n−3 11 n n−2 n−4
f (p) = −p + +2 +p
4 2 2 2 3 2 2 2 2
     
n n−3 n
+p9 2 + p6
3 2 4
Plugging in n = 8 and summing the absolute values of the coefficients, we find 7420, our
answer.

4
8. A permutation π : {1, 2, . . . , N } → {1, 2, . . . , N } is very odd if the smallest positive integer k
such that π k (a) = a for all 1 ≤ a ≤ N is odd, where π k denotes π composed with itself k
times. Let X0 = 1, and for i ≥ 1, let Xi be the fraction of all permutations of {1, 2, . . . , i} that
are very odd. Let S denote the set of all ordered 4-tuples (A, B, C, D) of nonnegative integers
such that A + B + C + D = 2023. Find the last three digits of the integer
X
2023 XA XB XC XD .
(A,B,C,D)∈S

Proposed by Daniel Carter

Answer: 116
A permutation is very odd if and only if its cycle decomposition consists only of odd cycles.
Letting ck be the number of cycles of length k, the number of very odd permutations for a
∞
P
given n is therefore equal the sum over all solutions to the equation n = (2i − 1)c2i−1 of the
i=1
number of ways there are to create a permutation with those cycle lengths. Given any fixed
ck , there are
ck −1  
1 Y n − ik 1 n!
= ·
ck ! i=0 k ck ! (n − kck )!(k!)ck
ways to choose the numbers in ck cycles of length k where the cycles are indistinguishable, and
(k − 1)! ways to order each cycle given the k numbers in a cycle, for a total of

((k − 1)!)ck n! n!
· =
ck ! (n − kck )!(k!)ck (n − kck )!ck !k ck

ways to form the ck cycles of length k Now, we can repeat the process on ck+2 using the new
n′ = n − kck . Multiplying this over all k, the product

n! (n − k1 )! (n − 3k3 )!
· · ...
(n − k1 )! (n − 3k3 )! (n − 5k5 )!
n! n!
telescopes to 0! = n!, which gives that there are ∞ ways to create a permuta-
c2i−1 !(2i−1)c2i−1
Q
i=1
tion with c2i−1 cycles of length 2i − 1 for all i ∈ N. Therefore, the generating function of the
sequence Xn is given by
∞ ∞ ∞ ∞
!  2n+1 
X
n
Y X 1 m(2n+1)
Y t t3 t5
Xn t = t = exp = exp(t + + + . . .)
n=0 n=0 m=0
m!(2n + 1)m n=0
2n + 1 3 5

Let Sn denote the set of all ordered

P 4-tuples of nonnegative integers satisfying a + b + c + d = n.
Consider the sequence Yn = (a,b,c,d)∈Sn Xa Xb Xc Xd . Our answer is 2023Y2023 . But the
generating function of Yn is the fourth power of the generating function of Xn , so since the
∞
P (−1)n+1 xn
generating function of log(1 + x) is n , we have
n=1

∞ 2
4t3 4t5

X
n 1+t
Yn t = exp(4t + + + . . .) = exp(2 log(1 + t) − 2 log(1 − t)) =
n=0
3 5 1−t
 2
2 4 4 4t
= −1 =1− + =1+
1−t 1 − t (1 − t)2 1−t

5
 ∞
1
tn , the generating function for this is equal to
P
Since the generating function for 1−t is
n=0
∞
ntn . The coefficient of t2023 is Y2023 = 4 · 2023, so our answer is 4 · 20232 , the last
P
1+4
n=1
three digits of which are 116.