Combinatorics Solutions Packet

1. Robert colors each square in an empty 3 by 3 grid either red or green. Find the number of colorings such that
no row or column contains more than one green square.

Proposed by Patrick Lin

Solution. Let the grid have k green squares. Then 0 ≤ k ≤ 3, otherwise by Pigeonhole some row must
contain two green squares. Note also that order does not matter. k = 0 gives one solution and k = 1 gives
nine solutions, clearly. k = 2 gives 12 (9 · 4) = 18 since there are only four choices remaining after coloring the
first square green, and k = 3 similarly gives 16 (9 · 4 · 1) = 6 solutions. This gives a total of 1 + 9 + 18 + 6 = 34
colorings.
2. Let S be a subset of {1, 2, . . . , 2017} such that for any two distinct elements in S, both their sum and product
are not divisible by seven. Compute the maximum number of elements that can be in S.

Proposed by Patrick Lin

Solution. Note that 7 | 2016, and so there 288 numbers that are i (mod 7) for i 6= 1, and 289 for i = 1.
From the product condition, it follows that S cannot contain anything divisible by seven. From the sum
condition, if x ∈ S and x ≡ 1 (mod 7), then nothing that is 6 (mod 7) is allowed, and similarly for the other
pairs; hence, from each of the pairs (1, 6), (2, 5), (3, 4) we can only choose one residue class. We can take
everything of a residue class, and so the maximum is 289 + 288 + 288 = 865 .
3. Annie stands at one vertex of a regular hexagon. Every second, she moves independently to one of the two
vertices adjacent to her, each with equal probability. Determine the probability that she is at her starting
position after ten seconds.

Proposed by Phillip Wang

Solution. Call a clockwise move L and a counter-clockwise move R. Then she is at her starting position
after ten seconds if the moves have 5 L’s and 5 R’s, 8 L’s and 2 R’s, or 2 L’s and 8 R’s, which can occur in
10 10 342 171



5 + 2 · 8 = 342 ways. The answer is hence 210 = 512 .

4. At a certain pizzeria, there are five different toppings available and a pizza can be ordered with any (possibly
empty) subset of them on it. In how many ways can one order an unordered pair of pizzas such that at most
one topping appears on both pizzas and at least one topping appears on neither?

Proposed by Patrick Lin

Solution. If no topping appears on both pizzas, then there are 35 − 25 = 211 ordered pairs, since each
topping is either on the first, second, or neither pizza and at least one must be on neither. If one topping
appears on both pizzas, then there are five ways to choose that one and 34 − 24 = 65 ways to assign the rest,
for 325 ordered pairs total.
To account for ordering, note that the only way to order two identical pizzas if they have the same sin-
gular topping or have no toppings; these contribute 6 pairs. Hence the total number of unordered pairs is
211+325+6
2 = 271 .
5. Emily draws six dots on a piece of paper such that no three lie on a straight line, then draws a line segment
connecting each pair of dots. She then colors five of these segments red. Her coloring is said to be red-triangle-
free if for every set of three points from her six drawn points there exists an uncolored segment connecting
two of the three points. In how many ways can Emily color her drawing such that it is red-triangle-free?

Proposed by David Altizio

Solution. We instead count the complement, i.e. the number of colorings that do contain a red triangle.
We first show that Emily’s coloring can result in at most two red triangles. Note that any two triangles can
share at most one side - otherwise, the two triangles would be identical. Hence if N is the number of triangles
in the coloring, then the number of edges E must satisfy
 
N N (N − 1) N (7 − N )
E ≥ 3N − = 3N − = .
2 2 2

This is at most 5 when N ≤ 2 or N ≥ 5, but clearly N ≥ 5 is absurd, so indeed N ≤ 2 as desired. It is also

worth noting that at N = 2 equality holds, so in that case exactly one side must be common to both triangles.
We now use the Principle of Inclusion-Exclusion to find the number
of colorings with at least one red triangle.
Choose one of the 63 = 20 possible right triangles. There are 62 − 3 = 12 edges left to choose from, and

we can choose them in 12

2 = 66 ways. Thus, the number of colorings with at least one red triangle is
66 · 20 = 1320 using this analysis. However, this overcounts the number of colorings that contain two red
triangles. To tackle this case, recall that in our combinatorial analysis above we determined that such a case
holds when exactly one side is common to both triangles. There are 15 ways to choose this side. From here,
note that the coloring is determined by choosing two of the other four dots and connecting each endpoint
of the chosen side to each of the two chosen dots. There are 6 ways to choose the dots, and so there are
15 · 6 = 90 colorings with two red triangles. Thus the true number of colorings with at least one red triangle
is 1320 − 90 = 1230.
Since the total number of possible colorings is
 
15 15 · 14 · 13 · 12 · 11
= = 7 · 13 · 3 · 11 = 3003,
5 5·4·3·2·1

the requested answer is 3003 − 1230 = 1773 .

6. Boris plays a game in which he rolls two standard four-sided dice independently and at random, and at the
end of the game receives a number of dollars equal to the product of the two rolled numbers. After the initial
roll of both dice, however, he can pay two dollars to reroll one die of choice, and he is allowed to pay to reroll
as many times as he wishes. If Boris plays to maximize his expected gain, how much money, in dollars, can
he expect to win by playing once?

Proposed by Patrick Lin

Solution. For 1 ≤ i, j ≤ 4, let Eij be the expected value of this game given the initial roll was (i, j). Note
that Eij = Eji , so assume for now that i ≤ j. Since it is clear that if a reroll should be used it should be used
to reroll the smaller number, we have
 
1 X
Eij = max ij, −2 + Ekj  ,
4
1≤k≤4

where it is the left expression when we do not reroll and the right one if we do. Begin by noting that E44 = 16,
since we can do no better. E34 = 12, since rolling until we obtain a pair of fours loses six dollars in expectation.
Similarly, E33 = 9, since in expectation we lose eight dollars for a gain of E34 − 9 = 3. We should reroll on
pairs (1, 4) and (2, 4) since even rerolling exactly once does no worse and being able to reroll multiple times
is better, which gives E14 = E24 = 10.
 Similarly, we find that rerolling on pairs (1, 3) and (2, 3) is optimal (clearly we should reroll on the former, and
either through intuition or trying out the two strategies gives us the latter). Finally, we can also determine
that on pairs (1, 1), (1, 2), (2, 2) we should reroll, allowing us to compute
 17

 4 (i, j) = (1, 1), (1, 2), (2, 2)
13

 2 (i, j) = (1, 3), (2, 3)




9 (i, j) = (3, 3)
Eij =
10 (i, j) = (1, 4), (2, 4)


12 (i, j) = (3, 4)





16 (i, j) = (4, 4).


The expected value of the game is hence

1 X 33
Eij = .
16 4
1≤i,j≤4

7. Given a finite set S ⊂ R3 , define f (S) to be the mininum integer k such that there exist k planes that divide
R3 into a set of regions, where no region contains more than one point in S. Suppose that
M (n) = max{f (S) : |S| = n} and m(n) = min{f (S) : |S| = n}.
Evaluate M (200) · m(200).

Proposed by Patrick Lin

Solution. First, it is clear that M (200) = 199; every plane adds one region at minimum, and equality is
achieved when S consists of 200 collinear points.
Now, note that m(n) is equal to the minimum integer k such that the maximum number of regions that k
planes

can divide R3 in is at least n. We claim that k planes can divide the space into at most k3 + k2 + k1 + k0

regions; this follows from the fact that every region can be associated with a unique subset of the k planes of
size at most three via the planes that bound the region from below (this, in turn, comes from the fact that
three non-parallel planes intersect at a point). Noting that
               
10 10 10 10 11 11 11 11
+ + + = 176 < 200 < 232 = + + + ,
3 2 1 0 3 2 1 0

it then follows that m(200) = 11, and so the answer is 199 · 11 = 2189 .
8. Andrew generates a finite random sequence {an } of distinct integers according to the following criteria:
• a0 = 1, 0 < |an | < 7 for all n, and ai 6= aj for all i < j.
• an+1 is selected uniformly at random from the set {an − 1, an + 1, −an }, conditioned on the above rule.
The sequence terminates if no element of the set satisfies the first condition.
1
For example, if (a0 , a1 ) = (1, 2), then a2 would be chosen from the set {−2, 3}, each with probability 2.
Determine the probability that there exists an integer k such that ak = 6.

Proposed by Patrick Lin

Solution. Equivalently, consider a random walk on a 2-by-6 grid of squares, where we begin at the upper
left corner. We then wish to find the probability that we reach the upper right corner; note, however, that
this is equal to the probability that we ever make it to the last column, for if we reach the lower right corner
first the next move must be to the upper right corner.
Define An to be the probability that we reach the last column of a 2-by-n grid, and Bn to be the same except
where it is possible to move left via moving to the other row then left, as depicted below. Then we wish to
find A6 , and note that moving to the left at any point guarantees that we can no longer make it to the last
column.
 Using the diagram above, we find the recurrence relations
1 1
An = An−1 + Bn−1
2 2
1 1
Bn = An−1 + Bn−1 ,
4 2
where A1 = B1 = 1. The relation for An is obvious, and for Bn we get the Bn−1 term when moving right, and
the An−1 term when moving along the column, accounting for the probability that we move left and can no
longer reach the last column without duplicating a square. Either through direction computation, rearranging
the equations to get the recurrence
1
An − An−1 = − An−2 ,
8
or by solving the characteristic to get
√ 
2 √ √ 
An = n (2 + 2)n − (2 − 2)n ,
4
35
we obtain A6 = 64 .

9. At a conference, six people place their name badges in a hat, which is shaken up; one badge is then distributed
to each person such that each distribution is equally likely. Each turn, every person who does not yet have
their own badge finds the person whose badge they have and takes that person’s badge. For example, if Alice
has Bob’s badge and Bob has Charlie’s badge, Alice would have Charlie’s badge after a turn. Compute the
probability that everyone will eventually end up with their own badge.

Proposed by Patrick Lin

Solution. We treat each assignment of badges as a permutation, which we can then decompose uniquely
into cycles. Note that if one member of a cycle obtains their own badge after some number of turns, then
every other member in the same cycle also has their own badge. For each cycle τ , one turn is the equivalent
of applying the cycle, and so in one turn it becomes τ 2 , which becomes τ 4 on the next turn, and so on.
Hence, this process will terminate if and only if the cycle decomposition consists only of cycles whose lengths
are powers of two. This gives rise to the recurrence

(n − 1)!
f (n) = f (n − 1) + (n − 1)f (n − 2) + f (n − 4),
(n − 4)!

where we ignore cycles of length larger than 4, since we only care about n = 6. Substituting f (0) = f (1) = 1
256 16
and f (2) = 2 yields f (6) = 256, and so the answer is 6! = 45 .
Alternatively, we can simply count based on the number of ways to partition 6 as a sum of powers of two, of
which there are six, namely {(1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1), (2, 2, 1, 1), (2, 2, 2), (4, 1, 1), (4, 2)}. These give
           
6 1 6 4 1 6 4 6 6
1+ + + + · 3! + · 3! = 256
2 2 2 2 6 2 2 4 4

possible permutations, which is the same as above.

10. Ryan stands on the bottom-left square of a 2017 by 2017 grid of squares, where each
square is colored either black, gray, or white according to the pattern as depicted to the
right. Each second he moves either one square up, one square to the right, or both one
up and to the right, selecting between these three options uniformly and independently.
Noting that he begins on a black square, find the probability that Ryan is still on a
black square after 2017 seconds.

Proposed by Patrick Lin

Solution. Index the grid by x and y coordinates, and consider the quantity k = x + y, such that a square
(x, y) is black iff 3 divides k. Then in each turn, k increases by 1 with probability 2/3 and by 2 with probability
1/3. We can hence consider the generating function

(2k + k 2 )2017
f (k) = ,
32017
where we wish to find the sum of the coefficients of the terms with exponents a multiple of 3.
√
−1+i 3
Define ω = 2 and observe that computing 13 (f (ω) + f (ω 2 ) + f (1)) will give us the desired answer. Then

32017 (f (ω) + f (ω 2 )) = (ω − 1)2017 + (ω 2 − 1)2017

= 32017/2 ((e5πi/6 )2017 + (e−5πi/6 )2017 )
= 2 · 32017/2 · cos(5π/6)
= −31009 .

Since f (1) = 1, it follows that the desired answer is

31008 − 1
 
1 1 1
(−3−1008 + 1) = 1− = .
3 3 31008 31009