Combinatorial Problems

Every pair of communities in a county is linked directly by exactly one mode of transportation (bus,
train, or airplane). All three transportation methods are used in the county, with:
1. • No community serviced by all three modes

• No three communities pairwise linked by the same mode

Let n be a fixed positive integer and consider an n × n grid of real numbers. Determine the greatest
possible number of cells c in the grid such that:
2. • The entry in c is strictly greater than the average of its column
• The entry in c is strictly less than the average of its row
Source: USEMO 2021

An immortal flea jumps on integer points of the number line, starting at 0. The jumps have lengths
3, 5, 9, . . . , 2k + 1, . . . (choosing direction each time). Can it eventually visit every natural number?
3. Source: Russia 2016

On a connected 2n-vertex graph, Alice and Bob alternately move tokens. With optimal play, what’s
the maximum number of edges allowing Alice to evade indefinitely?
4. Source: STEM 2025

n assistants start from one vertex of a unit cube, moving along edges at speeds 2, 4, . . . , 2n . Find the
maximal n allowing infinite collision-free movement.
5. Source: Korea Winter 2025

For n languages with 2n students (one per subset), find the minimal days needed to teach all languages
through non-repeating pairings.

6. Source: Kivy City MO 2025

On a (2n + 1) × (2n + 1) board with even-row/even-column cells removed, find the minimal ant steps
to visit all remaining cells.
7. Source: Polish MO 2025

Starting with numbers 1 through 2024, players alternately replace pairs with differences. Who can
force a multiple of 3 as the final number?
8. Source: Austria MO 2024

1
 P
For positive reals a1 , . . . , a2024 , prove the final number after operations satisfies c < 2024 ai .

9. Source: Baltic Way 2024

There are n cities, 2 airline companies in a country. Between any two cities, there is exactly one 2-way
flight connecting them which is operated by one of the two companies. A female mathematician plans
a travel route, so that it starts and ends at the same city, passes through at least two other cities,
and each city in the route is visited once. She finds out that wherever she starts and whatever route
she chooses, she must take flights of both companies. Find the maximum value of n.

10. Source: China Girls Math Olympiad 2012, Problem 5

The numbers 1, 2, 3, . . . , 1024 are written on a blackboard. They are divided into pairs. Then each
pair is wiped off the board and non-negative difference of its numbers is written on the board instead.
512 numbers obtained in this way are divided into pairs and so on. One number remains on the
blackboard after ten such operations. Determine all its possible values.

11. Source: Tuymaada 2018, Junior League, Problem 6

Let n ≥ 2 be an integer. Carl has n books arranged on a bookshelf. Each book has a height and
a width. No two books have the same height, and no two books have the same width. Initially,
the books are arranged in increasing order of height from left to right. In a move, Carl picks any
two adjacent books where the left book is wider and shorter than the right book, and swaps their
locations. Carl does this repeatedly until no further moves are possible. Prove that regardless of how
Carl makes his moves, he must stop after a finite number of moves, and when he does stop, the books
are sorted in increasing order of width from left to right.

12. Source: USAJMO 2020, Problem 1

Let n ≥ 5 be an integer. Consider n squares with side lengths 1, 2, . . . , n, respectively. The squares
are arranged in the plane with their sides parallel to the x and y axes. Suppose that no two squares
touch, except possibly at their vertices. Show that it is possible to arrange these squares in a way
such that every square touches exactly two other squares.

13. Source: APMO 2023, Problem 3

Students in a class form groups each of which contains exactly three members such that any two
distinct groups have at most one member in common. Prove that, when the class size is 46, there is
a set of 10 students in which no group is properly contained.

14. Source: APMO 2008, Problem 5

There are n blocks placed on the unit squares of a n × n chessboard such that there is exactly one
block in each row and each column. Find the maximum value k, in terms of n, such that however the
blocks are arranged, we can place k rooks on the board without any two of them threatening each
other.
(Two rooks are not threatening each other if there is a block lying between them.)

15. Source: JBMO 2023 Shortlist, Problem C2

2
 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?

16. Source: JBMO 2023 Shortlist, Problem C5

Let n > 2 be a positive integer. Masha writes down n natural numbers along a circle. Next, Taya
performs the following operation: Between any two adjacent numbers a and b, she writes a divisor of
the number a + b greater than 1, then Taya erases the original numbers and obtains a new set of n
numbers along the circle. Can Taya always perform these operations in such a way that after some
number of operations, all the numbers are equal?
17. Source: Russia 2024

Let n ≥ 3 be an odd integer. In a 2n × 2n board, we colour 2(n − 1)2 cells. What is the largest
number of three-square corners that can surely be cut out of the uncoloured figure?
18. Source: Russia 2024

Given a natural number n > 4 and 2n + 4 cards numbered with 1, 2, . . . , 2n + 4. On the card with
number m a real number am is written such that ⌊am ⌋ = m. Prove that it’s possible to choose 4
cards in such a way that the sum of the numbers on the first two cards differs from the sum of the
1
√n .
numbers on the two remaining cards by less than
n− 2

19. Source: Russia 2021

A teacher and her 30 students play a game on an infinite cell grid. The teacher starts first, then each
of the 30 students makes a move, then the teacher and so on. On one move the person can color one
unit segment on the grid. A segment cannot be colored twice. The teacher wins if, after the move of
one of the 31 players, there is a 1 × 2 or 2 × 1 rectangle, such that each segment from its border is
colored, but the segment between the two adjacent squares isn’t colored. Prove that the teacher can
win.
20. Source: Russia 2021

Some language has only three letters - A, B and C. A sequence of letters is called a word iff it contains
exactly 100 letters such that exactly 40 of them are consonants and other 60 letters are all A. What
is the maximum numbers of words one can pick such that any two picked words have at least one
position where they both have consonants, but different consonants?
21. Source: Russia 2021

Given is a set of n ≥ 5 people and m commissions with 3 persons in each. Let all the commissions
be nice if there are no two commissions A and B, such that | A ∩ B |= 1. Find the biggest possible
m (as a function of n).

22. Source: Bulgaria JBMO TST 2023

3
 The numbers 2, 2, . . . , 2 are written on a blackboard (the number 2 is repeated n times). One step
consists
q of choosing two numbers from the blackboard, denoting them as a and b, and replacing them
with ab+12 .
number left on the blackboard after n − 1 applications of the above operation, prove
23. (a) If x is theq
n+3
that x ≥ n .

(b) Prove that there are infinitely many numbers for which the equality holds and infinitely many
for which the inequality is strict.
Source: JBMO TST 2023

There are 20 students in a high school class, and each student has exactly three close friends in the
class. Five of the students have bought tickets to an upcoming concert. If any student sees that at
least two of their close friends have bought tickets, then they will buy a ticket too.
Is it possible that the entire class buys tickets to the concert?
(Assume that friendship is mutual; if student A is close friends with student B, then B is close friends
with A.)
24. Source: CJMO 2023

Each square of a 100 × 100 board is painted with one of 100 different colours, so that each colour is
used exactly 100 times. Show that there exists a row or column of the chessboard in which at least
10 colours are used.

25. Source: Nordic Mathematical Contest 2006, Problem 4

Count paths from (0, 0) to (2n, 2n) that divide the square into two even-area regions:
4n 2n



2n + n
2
26. Source: BXMO 2024