For teachers / Printable sets /Stage 9 · Combinatorics

Stage 9 · Combinatorics

10 problems · IMO P2/P5; hard shortlist · mathsolympiadprep.com

The answer key prints on its own page at the end.

Let $n$ be a positive integer. A Nordic square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:
(i) the first cell in the sequence is a valley,
(ii) each subsequent cell in the sequence is adjacent to the previous cell, and
(iii) the numbers written in the cells in the sequence are in increasing order.
Find, as a function of $n$ , the smallest possible total number of uphill paths in a Nordic square.
Author: Nikola Petrovi?

International Mathematical Olympiad

Combinatorics Solution and answer checking →
Let $n$ and $T$ be positive integers. James has $4 n$ marbles with weights $1,2, \ldots, 4 n$ . He places them on a balance scale, so that both sides have equal weight. Andrew may move a marble from one side of the scale to the other, so that the absolute difference in weights of the two sides remains at most $T$ .
Find, in terms of $n$ , the minimum positive integer $T$ such that Andrew may make a sequence of moves such that each marble ends up on the opposite side of the scale, regardless of how James initially placed the marbles.

IMO Shortlist

Combinatorics Solution and answer checking →
A cake has the form of an $n \times n$ square composed of $n^2$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$ .
Let $\mathcal{B}$ be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement $\mathcal{B}$ than of arrangement $\mathcal{A}$ . Prove that arrangement $\mathcal{B}$ can be obtained from $\mathcal{A}$ by performing a number of switches, defined as follows:
A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

IMO Shortlist 2006

Combinatorics Solution and answer checking →
On a square table of $2011$ by $2011$ cells we place a finite number of napkins that each cover a square of $52$ by $52$ cells. In each cell we write the number of napkins covering it, and we record the maximal number $k$ of cells that all contain the same nonzero number. Considering all possible napkin configurations, what is the largest value of $k$ ?

IMO Shortlist 2011

Combinatorics Solution and answer checking →
Let $n$ be a positive integer. Consider sequences $a_0, a_1, \dots, a_n$ such that $a_i \in \{1, 2, \dots, n\}$ for each $i$ and $a_n = a_0$ .
a. Call such a sequence good if for all $i = 1, 2, \dots, n$ , $a_i - a_{i-1} \not\equiv i \pmod n$ . Suppose that $n$ is odd. Find the number of good sequences.
b. Call such a sequence great if for all $i = 1, 2, \dots, n$ , $a_i - a_{i-1} \not\equiv i, 2i \pmod n$ . Suppose that $n$ is an odd prime. Find the number of great sequences.

USA IMO

Combinatorics Solution and answer checking →
Integers are written in the cells of a table $2010 \times 2010$ . Adding $1$ to all the numbers in a row or in a column is called a move. We say that the table is equilibrium if one can obtain after finitely many moves a table in which all the numbers are equal.
a) Find the largest positive integer $n$ , for which there exists an equilibrium table containing the numbers $2^0, 2^1, \dots, 2^n$ .
b) For this $n$ , find the maximal number that may be contained in such a table.

BMO Shortlist 2010

Combinatorics Solution and answer checking →
The kingdom of Anisotropy consists of $n$ cities. For every two cities there exists exactly one direct one-way road between them. We say that a path from $X$ to $Y$ is a sequence of roads such that one can move from $X$ to $Y$ along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection.
Let $A$ and $B$ be two distinct cities in Anisotropy. Let $N_{A B}$ denote the maximal number of paths in a diverse collection of paths from $A$ to $B$ . Similarly, let $N_{B A}$ denote the maximal number of paths in a diverse collection of paths from $B$ to $A$ . Prove that the equality $N_{A B}=N_{B A}$ holds if and only if the number of roads going out from $A$ is the same as the number of roads going out from $B$ .

IMO Shortlist 2021

Combinatorics Solution and answer checking →
Let $n_1, n_2, \dots, n_{26}$ be pairwise distinct positive integers, satisfying:
(1) In the decimal representation of each $n_i$ , each digit belongs to the set $\{1, 2\}$ ;
(2) For any $i, j$ , $n_j$ cannot be obtained from $n_i$ by adding some digits on the right.
Find the least possible value of $\sum_{i=1}^{26} S(n_i)$ , where $S(m)$ denotes the sum of all digits of $m$ in decimal representation.

China National Team Selection Test

Combinatorics Solution and answer checking →
The columns and the rows of a $3n \times 3n$ square board are numbered $1, 2, \ldots, 3n$ . Every square $(x, y)$ with $1 \leq x, y \leq 3n$ is colored asparagus, byzantium or citrine according as the modulo $3$ remainder of $x+y$ is $0$ , $1$ or $2$ respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are $3n^{2}$ tokens of each color.
Suppose that one can permute the tokens so that each token is moved to a distance of at most $d$ from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most $d+2$ from its original position, and each square contains a token with the same color as the square.

IMO Shortlist

Combinatorics Solution and answer checking →
Let $A_{0} = (a_{1}, \ldots, a_{n})$ be a finite sequence of real numbers. For each $k \geq 0$ , from the sequence $A_{k} = (x_{1}, \ldots, x_{n})$ we construct a new sequence $A_{k+1}$ in the following way.
1. We choose a partition $\{1, \ldots, n\} = I \cup J$ , where $I$ and $J$ are two disjoint sets, such that the expression
$\left|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}\right|$
attains the smallest possible value. (We allow the sets $I$ or $J$ to be empty; in this case the corresponding sum is $0$ .) If there are several such partitions, one is chosen arbitrarily.
2. We set $A_{k+1} = (y_{1}, \ldots, y_{n})$ , where $y_{i} = x_{i} + 1$ if $i \in I$ , and $y_{i} = x_{i} - 1$ if $i \in J$ .
Prove that for some $k$ , the sequence $A_{k}$ contains an element $x$ such that $|x| \geq n / 2$ .

IMO Shortlist 2007

Combinatorics Solution and answer checking →

Answer key — Stage 9 · Combinatorics

Worked solutions for every problem are on the site, one page per problem.

$2n(n - 1) + 1$ open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open
Prove it — see the worked solution open

Problems belong to the competitions that set them. Each question on this sheet names the competition it came from, and the licences the material is used under are listed below. Free to copy for classroom use.

Apache-2.0 · CC-BY-4.0