Combinatorics A Solutions

1. Alien Connor starts at (0, 0) and walks around on the integer lattice. Specifically, he takes one
step of length one in a uniformly random cardinal direction every minute, unless his previous
four steps were all in the same direction in which case he randomly picks a new direction to
step in. Every time he takes a step, he leaves toxic air on the lattice point he just left, and the
toxic cloud remains there for 150 seconds. After taking 5 steps in total, the probability that
he has not encountered his own toxic waste can be written as ab for relatively prime positive
integers a, b. Find a + b.
Proposed by Ben Zenker
Answer: 505
Due to parity, we can see that the only way he can encounter his own toxic waste is by walking
directly backwards. The toxic waste stays in the air for 2 full step sizes, but disappears after
3, and there’s no way to take two more steps and return to where you started.
First, suppose his first four steps are all in the same direction, which happens with probability
1 2
43 . Then, the probability he avoids his own toxic waste with his last step is 3 , contributing a
2 1
probability of 3 · 43 . Otherwise, we see the probability he makes it four steps without hitting

3
is own toxic waste while also not going the same direction every step is 34 − 413 = 13 32 .
Conditioned on this, we see the probability his last step also avoids the toxic air is again
3 2 1 13 3 4 117 121
4 . Thus, our final answer is 3 · 43 + 32 · 4 = 3·128 + 3·128 = 384 , giving a final answer of
121 + 384 = 505.
2. Let ⊕ denote the xor binary operation. Define x ⋆ y = (x + y) − (x ⊕ y). Compute
63
X
(k ⋆ 45).
k=1

(Remark: The xor operator works as follows: when considered in binary, the kth binary
digit of a ⊕ b is 1 exactly when the kth binary digits of a and b are different. For example,
5 ⊕ 12 = 01012 ⊕ 11002 = 10012 = 9.)
Proposed by Julian Shah
Answer: 2880
Solution 1: Consider pairing the kth term with the (63 − k)th term:
(k ⋆ 45) + ((63 − k) ⋆ 45) = 63 + 2 · 45 − [k ⊕ 45 + (63 − k) ⊕ 45]
k and 63 − k differ in every binary digit, so the values of k ⊕ 45 and (63 − k) ⊕ 45 will
be completely complementary; hence, they add to 63 (when performing the addition k ⊕ 45,
switching a 0 to a 1 in k’s representation will switch the result of that output digit).
63
P
So, when we pair k and 63 − k, the result is 2 · 45. This means (k ⋆ 45) = 64 · 45, but
k=0
(0 ⋆ 45) = 45 − 45 = 0, so our final answer is actually 64 · 45 = 2880 .
Solution 2: For any x and y, we can obtain the relationship: (x ⊕ y) + 2(x&y) = x + y, where
x&y is the bitwise-and operator: x&y has a 1 in a place only if both x and y do.
This occurs since x ⊕ y returns 0 in all places where x and y are both 1, whereas under normal
addition this should contribute 2 times that place value. Adding 2(x&y) covers this difference.
Therefore, x ⋆ y = (x + y) − (x ⊕ y) = 2(x&y).
Again, note that ((63 − k)&45) + (k&45) = 45. Collectively, k and 63 − k will ‘select’ all the
1’s places of 45, so adding them will return exactly 45.
63
P
Using the same trick as earlier, (k&45) = 32·45, so our answer is twice this, 2·32·45 = 2880 .
k=0

1
3. The integers from 1 to 25, inclusive, are randomly placed into a 5 by 5 grid such that in
each row, the numbers are increasing from left to right. If the columns from left to right are
numbered 1, 2, 3, 4, and 5, then the expected column number of the entry 23 can be written
as ab where a and b are relatively prime positive integers. Find a + b.
Proposed by Rishi Dange
Answer: 17
14
The answer is 3 . We proceed using casework, seeing pretty easily that 23 cannot be in columns
1 or 2.
Case 1: 23 is in column 5 In a given row, by putting 23 as the rightmost item, there are now
22

(22
4)
4 ways to fill in the rest of the row. This makes for a probability of 5 rows × (25) .
5

Case 2: 23 is in column 4 The right two elements in the row with 23 are either 23 and 24 or 23
and 25, which makes the “rows” coefficient above 5 × 2 = 10. Thus we now have a probability
(22
3)
of 10 × 25 .
(5)
Case 3: 23 is in column 3 The right three elements must be 23, 24, and 25, so the coefficient is
(22
2)
5 again to represent the number of possible rows. Thus we now have a probability of 5 × 25 .
(5)
Computing the expected value using these probabilities (quite a bit of stuff cancels out), we
find the expected value to be 14
3 .

4. A sequence of integers a1 , a2 , . . . , an is said to be sub-Fibonacci if a1 = a2 = 1 and ai ≤

ai−1 + ai−2 for all 3 ≤ i ≤ n. How many sub-Fibonacci sequences are there with 10 terms such
that the last two terms are both 20?
Proposed by Daniel Carter
Answer: 238
The number of sequences of length 10 that end in 20, 20 is just the number of sequences of
length 9 which end in 20, since it is impossible for it to be the case that a8 < 0 and a9 = 20,
as the seventh Fibonacci number (i.e. the maximum possible value for a7 ) is only 13.
Let Fn be the Fibonacci numbers, where F1 = F2 = 1. Suppose we chose the maximum value
ai−1 + ai−2 for every term ai in our sequence except for some aj , which we made k less than
the maximum possible value. Then an = Fn − kFn−j+1 . This works similarly if we make
Pn less than their maximum; if we define di = ai − ai−1 − ai−2 , then we find
multiple terms
an = Fn − i=3 di Fn−i+1 . Since F9 = 34, the question is equivalent to asking for the number
P9
of choices of di which make i=3 di F10−i = 14.
In order to compute this, let’s define f (k, t) to be the number of choices of di such that
P t
i=1 di Fi = k. By convention, f (0, t) = 1 for all t and f (k, t) = 0 if k is negative. We are
looking for f (14, 7). We have f (k, t) = f (k, t − 1) + f (k − Ft , t), i.e. we either stop increasing
dt and move on to smaller t or increment dt . With this recurrence, we can quickly fill up a
table of values for f until we hit f (14, 7), which we find to be 238.
5. There are n assassins numbered from 1 to n, and all assassins are initially alive. The assassins
play a game in which they take turns in increasing order of number, with assassin 1 getting
the first turn, then assassin 2, etc., with the order repeating after assassin n has gone; if an
assassin is dead when their turn comes up, then their turn is skipped and it goes to the next
assassin in line. On each assassin’s turn, they can choose to either kill the assassin who would
otherwise move next or to do nothing. Each assassin will kill on their turn unless the only
option for guaranteeing their own survival is to do nothing. If there are 2023 assassins at the

2
 start of the game, after an entire round of turns in which no one kills, how many assassins
must remain?
Proposed by Ben Lemkin
Answer: 1023
We show by induction that number of the form n = 2k −1 are stable, being no one shoots, while
all others are not. n = 1, 2 are trivial; for n = 3, we observe it’s stable for the following reason;
if person 1 shoots person 2, then person 3 will kill person 1, so to avoid dying person 1 will not
shoot; by symmetry, this means none of them will shoot. Indeed, note by symmetry that we
only need to assess the first person’s behavior, as if person 1 shoots then it’s not stable, while
if person 1 does not shoot then it is stable. With the base case proven, suppose n = 2k − 1 is
stable. Consider n = 2k ; the first person will shoot the second person, because then there are
2k − 1 people remaining, and by assumption no one will shoot in this scenario. Similarly, for
n = 2k + 1, if the first person shoots the second person, then 2k people will remain standing,
whence the third person will proceed to shoot the fourth person after which 2k − 1 people are
left and everyone ceases. Thus, the first person will shoot the second person as long as the
first person is not also the fourth person (meaning 4 ≡ 1 (mod 2k − 1)). Continuing like so,
we see that for n = 2k + a for a ≥ 0 that person 1 will shoot, then person 3 will shoot, etc.,
all the way up to person 2(a + 1) − 1 shooting person 2(a + 1), after which there are 2k − 1
people left and no one else shoots. This sequence of events will hold up until the point when
2(a + 1) ≡ 1 (mod 2k + a), because that would means person 1 gets shot; the smallest a this
holds for, and thus the next smallest stable position, is a = 2k − 1, implying n = 2k+1 − 1.
Thus, by induction, stable n are of the form 2k − 1, and our answer is 1023.
6. For a positive integer n, let Pn be the set of sequences of 2n elements, each 0 or 1, where
there are exactly n 1’s and n 0’s. I choose a sequence uniformly at random from Pn . Then, I
partition this sequence into maximal blocks of consecutive 0’s and 1’s. Define f (n) to be the
expected value of the sum of squares of the block lengths of this uniformly random sequence.
What is the largest integer value that f (n) can take on?
Proposed by Kevin Ren
Answer: 121
P a

It’s easier to compute the expected value of 2 , where the a’s are the block lengths. Note
that      
hX i X a a
2
E a =E 2 + a = 2E + 2n,
2 2
= 2 · n(n−1)
P a

since the sum of block lengths is clearly 2n. Hence, it suffices to show E 2 n+2 .
P a

Note that 2 equals the number of pairs of indices (i, j) such that (i, j) belong to the same
block. We take advantage of this by instead computing the expectation that (i, j) belong to
the same block, and sum over (i, j) (this amounts to a change of summation). The probability
that (i, j) belong to the same block is 2 · 2n−|j−i+1|

2n

n / n . And then by various binomial
identities,
X 2n − |j − i + 1| X 2n   X 2n  
2n − k 2n − k + 1
2· = 2(2n − k + 1) = 2(n + 1)
i<j
n n n+1
k=2 k=2
 
2n
= 2(n + 1) .
n+2
P a

 2n

2n

n(n−1)
Finally, E 2 = 2(n + 1) n+2 / n = 2· n+2 , as desired. This gives the actual desired
2 6(n−2)(n+2)
6n 24
expected value as n+2 . In order for this to be an integer, note that it equals n+2 + n+2 ,

3
 which is an integer precisely when n + 2|24. It is evidently maximized for n = 22, giving an
2
answer of 6·22
24 = 121.

7. A utility company is building a network to send electricity to fifty houses, with addresses
0, 1, 2, . . . , 49. The power center only connects directly to house 0, so electricity reaches all
other houses through a system of wires that connects specific pairs of houses. To save money,
the company only lays wires between as few pairs of distinct houses as possible; additionally,
two houses with addresses a and b can only have a wire between them if at least one of the
following three conditions is met:
• 10 divides both a and b.
• 10
b a
≡ 10 (mod 5).
• 10 ≡ 10 (mod 5).
b a

Letting N be the number of distinct ways such a wire system can be configured so that every
house receives electricity, find the remainder when N is divided by 1000.
Proposed by Austen Mazenko
Answer: 810
Interpreting the network as a graph G, with houses as vertices and wires as edges, we see
that the conditions reduce to the graph being comprised of five K11 cliques and one K5
clique. Specifically, the groups of houses {0, ..., 10}, {10, ..., 20}, {20, ..., 30}, {30, ..., 40}, and
{40, ..., 49, 0} are all fully connected within themselves forming K11 cliques, and the vertices
{0, 10, 20, 30, 40} form a K5 clique. Now, a connected subgraph with a minimal number of
edges, which is precisely what any valid configuration of the wire network is, is by definition
just a spanning tree of the graph. Thus, we seek the number of spanning trees. Call the
vertices 0, 10, 20, 30, 40 connectors, because any path in a spanning tree between two vertices
in different K11 cliques must include a connector. Let C be an auxiliary K5 graph with vertices
that are phantom copies of the connectors. Recall that on a tree, there is a unique shortest
path between any two vertices; the crucial observation is that any spanning tree T on G can
be associated with a spanning tree f (T ) on C in which two connectors are adjacent if the
shortest path between those connectors on T doesn’t pass through another connector.
To count the number of spanning trees on G, we will split into casework based on which
spanning tree on C they correspond to (namely, based on the image of the map f taking
spanning trees on G to spanning trees on C). Call two connectors near if they are in a K11
clique together, and far otherwise (e.g. 0 is near 10 and 40 and far from 20 and 30). Note that
two far connectors will share an edge in T iff they do in f (T ). Next, if two near connectors
share an edge in f (T ), then the shortest path in T connecting them lies in the K11 containing
both of them. Moreover, because these connectors silo off this K11 from the rest of G, we
see that T forms a spanning tree on this K11 ; the number of ways this can happen is 119 by
Cayley’s formula. Finally, if two near connectors don’t share an edge in f (T ), then there can
be no path between them in the K11 containing both of them. However, every vertex in this
K11 must be path-connected to one of these connectors via T , so the restriction of T to this
K11 looks like two disjoint spanning trees, one for each of the two connectors. We claim that
the number of ways to choose two disjoint spanning trees on K11 rooted at two fixed vertices
v1 , v2 (the connectors) is 2 · 118 . Note that every such pair of disjoint spanning trees can be
uniquely associated with a single spanning tree on K11 by adding the edge v1 v2 . Thus, it’s
equivalent to counting the number of spanning trees on K11 containing a fixed edge. Now, if
we pick a spanning tree at random, by Cayley’s formula there are 119 to pick from, and by
symmetry the probability a given edge is in the spanning tree is 10 2
= 11 (the number of edges
(11
2)

4
 2
in each spanning tree divided by the number of edges in K11 ). Hence, there are 11 ·119 = 2·118
ways to pick two disjoint spanning trees rooted at two fixed vertices, as claimed.
Putting this all together, for a given spanning tree on C, the number of spanning trees T of
G that map to it will be (119 )a · (2 · 118 )5−a , where a is the number of edges between near
connectors in the spanning tree on C. Doing casework on the spanning trees of C ≃ K5 , we
see that a = 4 in 5 of them, a = 3 in 2 · 5 + 4 · 5 = 30, a = 2 in 4 · 5 + 7 · 5 = 55, a = 1 in 30,
and a = 0 in 5 of them.
In conclusion, the total number of configurations is
N = 5 · 1136 · 2 · 118 + 30 · 1127 · 22 · 1116 + 55 · 1118 · 23 · 1124 + 30 · 119 · 24 · 1132 + 5 · 25 · 1140 ,
and taking modulo 1000 gives 410 + 720 + 240 + 280 + 160 = 810.
8. A spider is walking on the boundary of equilateral triangle △ABC (vertices labelled in coun-
terclockwise order), starting at vertex A. Each second, she moves to one of her two adjacent
vertices with equal probability. The windiness of a path that starts and ends at A is the net
number of counterclockwise revolutions made. For example, the windiness of the path ABCA
is 1, and the windiness of the path ABCACBACBA is −1. What is the remainder modulo
1000 of the sum of the squares of the windiness values taken over all possible paths that end
back at vertex A after 2025 seconds?
Proposed by Atharva Pathak
Answer: 50
Pn 3n


Let 3n = 2025. We seek S = k=0 (2k − n)2 . Expanding, this equals
3k
n  
X 3n
S= (4k 2 − 4nk + n2 ) (1)
3k
k=0
P3n
Let p(x) = (1 + x)3n . Note that p(x) = ℓ=0 3n x . Note that xp′ (x) = (3n)x(1 + x)3n−1 =

ℓ
P3n 3n
ℓ ℓ P3n
2 ′′
= ℓ=0 3n
2 3n−2

ℓ
ℓ=0 ℓ ℓx . Note that x p (x) = (3n)(3n − 1)x (1 + x) ℓ ℓ(ℓ − 1)x . (Here,
′ ′ a−1
q (x) denotes the formal derivative of the polynomial q, defined by q (x) = ax for q(x) = xa
and extended linearly.)
Note that 4· 91 [ℓ(ℓ−1)+ℓ]−4n· 13 ℓ+n2 = 94 ℓ2 − 4n 2 2 2
3 ℓ+n . For ℓ = 3k, this equals 4k −4nk +n .
Let ζ = exp(2πi/3). We apply the roots of unity filter to obtain
2
1 X 4 2 ′′ 4n ′
S= [ (x p (x) − xp′ (x)) − xp (x) + n2 p(x)](ζ j ) (2)
3 j=0 9 3

where we evaluate the summand at x = ζ j . The summand simplifies to the expression

1
n(1 + x)3n−2 (3n(x − 1)2 + 4x) (3)
3
For x = 1, the summand is clearly 31 n23n−2 · 4 = 13 n8n . For x = ζ, the summand is
1 1
n(1 + ζ)3n−2 (3n(ζ − 1)2 + 4ζ) = n(−1)n (−9n + 4) (4)
3 3
using the fact that 1 + ζ = −ζ 2 and (ζ − 1)2 = −3ζ. By symmetry the same holds for x = ζ 2 .
It follows that the sum is given by
1 1 n 2 1 2
S=[ n8 + (−1)n (−9n2 + 4n)] = n8n + (−1)n n(4 − 9n)
3 3 3 9 9
We set n = 2025/3 = 675 and compute mod 1000 to obtain the desired answer.