COMBINATORICS IOQM 5M&RMO

Instructions

1. Try to attempt all

2. Section D is optional

3. All solutions are available on AoPS

Section A: 5 Marker Problems (1-10)

1. Let V be the set of vertices of a regular 24-gon. Find the number of ways to draw 12 segments of
equal lengths so that each vertex in V is an endpoint of exactly one of the 12 segments.

2. Sixteen chairs are arranged in a row. Eight people each select a chair in which to sit so that no
person sits next to two other people. Let N be the number of subsets of 16 chairs that could be
selected. Find the remainder when N is divided by 1000.

3. Find the number of rectangles that can be formed inside a fixed regular dodecagon (12-gon) where
each side of the rectangle lies on either a side or a diagonal of the dodecagon. The diagram below
shows three of those rectangles.

4. Each vertex of a regular octagon is independently colored either red or blue with equal probability.
The probability that the octagon can then be rotated so that all of the blue vertices end up at
positions where there had been red vertices is m n , where m and n are relatively prime positive
integers. Find m + n.

5. Find the number of collections of 16 distinct subsets of {1, 2, 3, 4, 5} with the property that for
any two subsets X and Y in the collection, X ∩ Y ̸= ∅.

6. The following analog clock has two hands that can move independently of each other. Initially,
both hands point to the number 12. The clock performs a sequence of hand movements so that on
each movement, one of the two hands moves clockwise to the next number on the clock face while
the other hand does not move. Let N be the number of sequences of 144 hand movements such
that during the sequence, every possible positioning of the hands appears exactly once, and at the
end of the 144 movements, the hands have returned to their initial position. Find the remainder
when N is divided by 1000.

1
COMBINATORICS IOQM 5M&RMO PROBLEM SET

7. There are 1024 players, ranked from 1 (most skilled) to 1024 (least skilled), participating in a single
elimination tournament. In each of the 10 rounds, the remaining players are paired uniformly at
random. In each match, the player with a lower rank always wins, and the loser is eliminated
from the tournament. For each positive integer n ∈ [1, 1024], let f (n) be the expected number of
rounds that the participant with rank n participates in. Estimate the minimum positive integer
N such that f (N ) < 2.

8. Dorothea has a 3×4 grid of dots. She colors each dot red, blue, or dark gray. Compute the number
of ways Dorothea can color the grid such that there is no rectangle whose sides are parallel to the
grid lines and whose vertices all have the same color.

9. For each i ∈ {1, . . . , 10}, ai is chosen independently and uniformly at random from (0, i2 ]. Let P
be the probability that a1 < a2 < . . . < a10 . Estimate P .

10. A 5×5 table is called regular if each of its cells contains one of four pairwise distinct real numbers,
such that each of them occurs exactly once in every 2 × 2 subtable. The sum of all numbers of
a regular table is called the total sum of the table. With any four numbers, one constructs all
possible regular tables, computes their total sums, and counts the distinct outcomes. Determine
the maximum possible count.

Section B: Tough 5 Marker Problems (11-20)

11. Anna and Bob, with Anna starting first, alternately color the integers of the set S = {1, 2, ..., 2022}
red or blue. At their turn each one can color any uncolored number of S they wish with any color
they wish. The game ends when all numbers of S get colored. Let N be the number of pairs
(a, b), where a and b are elements of S, such that a, b have the same color, and b − a = 3. Anna
wishes to maximize N . What is the maximum value of N that she can achieve regardless of how
Bob plays?

12. We call an even positive integer n nice if the set {1, 2, ..., n} can be partitioned into 4 two-element
subsets, such that the sum of the elements in each subset is a power of 3. For example, 6 is
nice, because the set {1, 2, 3, 4, 5, 6} can be partitioned into subsets {1, 2}, {3, 6}, {4, 5}. Find the
number of nice positive integers which are smaller than 3772 .

13. You are given that 1000! has 2568 decimal digits. Call a permutation π of length 1000 good if
π(2i) > π(2i − 1) for all 1 ≤ i ≤ 500 and π(2i) > π(2i + 1) for all 1 ≤ i ≤ 499. Let N be the
number of good permutations. Estimate D, the number of decimal digits in N .

2
COMBINATORICS IOQM 5M&RMO PROBLEM SET

14. An economist and a statistician play a game on a calculator which does only one operation.
The calculator displays only positive integers and it is used in the following way: Denote by n
an integer that is shown on the calculator. A person types an integer, m, chosen from the set
{1, 2, ..., 99} of the first 99 positive integers, and if m% of the number n is again a positive integer,
then the calculator displays m% of n. Otherwise, the calculator shows an error message and
this operation is not allowed. The game consists of doing alternatively these operations and the
player that cannot do the operation loses. How many numbers from {1, 2, ..., 2019} guarantee the
winning strategy for the statistician, who plays second?

15. We have a group of n kids. For each pair of kids, at least one has sent a message to the other one.
For each kid A, among the kids to whom A has sent a message, exactly 25% have sent a message
to A. How many possible two-digit values of n are there?

16. Sam chooses 1000 random lattice points (x, y) with 1 ≤ x, y ≤ 100000 such that all pairs (x, y)
are distinct. Let N be the expected size of the maximum collinear set among them. Estimate
⌊100N ⌋.

17. We have a set of 343 closed jars, each containing blue, yellow and red marbles with the number of
marbles from each color being at least 1 and at most 7. No two jars have exactly the same contents.
Initially all jars are with the caps up. To flip a jar will mean to change its position from cap-up to
cap-down or vice versa. It is allowed to choose a triple of positive integers (b, y, r) ∈ {1, 2, ..., 7}3
and flip all the jars whose number of blue, yellow and red marbles differ by not more than 1 from
b, y, r, respectively. After n moves all the jars turned out to be with the caps down. Find the
number of all possible values of n, if n ≤ 2021.

18. There is a pack of 27 distinct cards, and each card has three values on it. The first value is a
shape from {∆, □, ⊙}; the second value is a letter from {A, B, C}; and the third value is a number
from {1, 2, 3}. In how many ways can we choose an unordered set of 3 cards from the pack, so
that no two of the chosen cards have two matching values.

19. Consider a colored board with dimensions 2023 × 2023, in which each unit cell is colored either
blue or red. The majority of cells are blue, and exactly 1012 columns have a majority of red cells.
Determine the maximum possible side length of the largest monochromatic square.

20. The following image is 1024 pixels by 1024 pixels, and each pixel is either black or white. The
border defines the boundaries of the image, but is not part of the image. Let a be the proportion
of pixels that are black. Estimate A = ⌊10000a⌋.

3
COMBINATORICS IOQM 5M&RMO PROBLEM SET

Section C: RMO-ish Problems (21-25)

21. Lucy starts by writing s integer-valued 2022-tuples on a blackboard. After doing that, she can
take any two (not necessarily distinct) tuples v = (v1 , . . . , v2022 ) and w = (w1 , . . . , w2022 ) that
she has already written, and apply one of the following operations to obtain a new tuple:

v + w = (v1 + w1 , . . . , v2022 + w2022 )

v ∨ w = (max(v1 , w1 ), . . . , max(v2022 , w2022 ))

and then write this tuple on the blackboard. It turns out that, in this way, Lucy can write
any integer-valued 2022-tuple on the blackboard after finitely many steps. What is the smallest
possible number s of tuples that she initially wrote?

22. An antelope is a chess piece which moves similarly to the knight: two cells (x1 , y1 ) and (x2 , y2 )
are joined by an antelope move if and only if

{|x1 − x2 |, |y1 − y2 |} = {3, 4}.

The numbers from 1 to 1012 are placed in the cells of a 106 × 106 grid. Let D be the set of all
absolute differences of the form |a − b|, where a and b are joined by an antelope move in the
arrangement. How many arrangements are there such that D contains exactly four elements?

23. The set A = {1, 2, 3, . . . , 10} contains the numbers 1 through 10. A subset of A of size n is
competent if it contains n as an element. A subset of A is minimally competent if it itself is
competent, but none of its proper subsets are. Find the total number of minimally competent
subsets of A.

24. Let p be a permutation of the set Sn = {1, 2, . . . , n}. An element j ∈ Sn is called a fixed point
of p if p(j) = j. Let fn be the number of permutations having no fixed points, and gn be the
number with exactly one fixed point. Find |fn − gn |.

25. A site is any point (x, y) in the plane such that x and y are both positive integers less than or
equal to 20. Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones
with Amy going first. On her turn, Amy places a new red stone on an unoccupied
√ site such that
the distance between any two sites occupied by red stones is not equal to 5. On his turn, Ben
places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to
be at any distance from any other occupied site.) They stop as soon as a player cannot place a
stone. Find the greatest K such that Amy can ensure that she places at least K red stones, no
matter how Ben places his blue stones.

4
COMBINATORICS IOQM 5M&RMO PROBLEM SET

Section D: Challenging Section [Optional] (26-28)

26. Let n be a positive integer. Eric and a squid play a turn-based game on an infinite grid of unit
squares. Eric’s goal is to capture the squid by moving onto the same square as it. Initially, all the
squares are colored white. The squid begins on an arbitrary square in the grid, and Eric chooses
a different square to start on. On the squid’s turn, it performs the following action exactly 2020
times: it chooses an adjacent unit square that is white, moves onto it, and sprays the previous
unit square either black or gray. Once the squid has performed this action 2020 times, all squares
colored gray are automatically colored white again, and the squid’s turn ends. If the squid is ever
unable to move, then Eric automatically wins. Moreover, the squid is claustrophobic, so at no
point in time is it ever surrounded by a closed loop of black or gray squares. On Eric’s turn, he
performs the following action at most n times: he chooses an adjacent unit square that is white
and moves onto it. Note that the squid can trap Eric in a closed region, so that Eric can never
win. Eric wins if he ever occupies the same square as the squid. Suppose the squid has the first
turn, and both Eric and the squid play optimally. Both Eric and the squid always know each
other’s location and the colors of all the squares. Find all positive integers n such that Eric can
win in finitely many moves.

27. 2500 chess kings have to be placed on a 100 × 100 chessboard so that: (1) No king can capture
any other one (i.e. no two kings are placed in two squares sharing a common vertex); (2) Each
row and each column contains exactly 25 kings. Find the number of such arrangements. (Two
arrangements differing by rotation or symmetry are supposed to be different.)

28. Esmeralda has created a special knight to play on quadrilateral boards that are identical to
chessboards. If a knight is in a square then it can move to another square by moving 1 square in
one direction and 3 squares in a perpendicular direction (which is a diagonal of a 2 × 4 rectangle
instead of 2 × 3 like in chess). In this movement, it doesn’t land on the squares between the
beginning square and the final square it lands on. A trip of the length n of the knight is a
sequence of n squares C1 , C2 , . . . , Cn which are all distinct such that the knight starts at the C1
square and for each i from 1 to n − 1 it can use the movement described before to go from the
Ci square to the Ci+1 . Determine the greatest N ∈ N such that there exists a path of the knight
with length N on a 5 × 5 board.

Thank you for attempting the problem set!