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?

Combinatorics Solution and answer checking →
Dexter's Laboratory has $2024$ robots, each with a program setup by Dexter. One day, his naughty sister Dee Dee intrudes and writes an integer in $\{1, 2, \dots, 113\}$ on each of the robot's forehead. Each robot detects the numbers on all other robots' foreheads, and guess its own number base on its program, individually and simultaneously.
Find the largest positive integer $k$ such that Dexter can setup the programs so that, no matter how the numbers distribute, there are always at least $k$ robots who guess their numbers right.

Combinatorics Solution and answer checking →
A $k$ -set is a set with exactly $k$ elements. For a 6-set $A$ and any collection $\mathcal{F}$ of 4-sets, we say that $A$ is $\mathcal{F}$ -good if there are exactly three elements $B_1, B_2, B_3$ in $\mathcal{F}$ that are subsets of $A$ , and they furthermore satisfy
$(A \setminus B_1) \cup (A \setminus B_2) \cup (A \setminus B_3) = A.$
Find all $n \ge 6$ so that there exists a collection $\mathcal{F}$ of 4-subsets of $\{1, 2, \dots, n\}$ such that every 6-set $A \subset \{1, 2, \dots, n\}$ is $\mathcal{F}$ -good.

Combinatorics Solution and answer checking →
Consider an infinite sequence $a_{1}, a_{2}, \ldots$ of positive integers with $a_{i} \leqslant 2015$ for all $i \geqslant 1$ . Suppose that for any two distinct indices $i$ and $j$ we have $i+a_{i} \neq j+a_{j}$ .
Prove that there exist two positive integers $b$ and $N$ such that
$\left|\sum_{i=m+1}^{n}\left(a_{i}-b\right)\right| \leqslant 1007^{2}$
whenever $n>m \geqslant N$ .

Combinatorics Solution and answer checking →
An $(n, k)$ -tournament is a contest with $n$ players held in $k$ rounds such that:
(i) Each player plays in each round, and every two players meet at most once.
(ii) If player $A$ meets player $B$ in round $i$ , player $C$ meets player $D$ in round $i$ , and player $A$ meets player $C$ in round $j$ , then player $B$ meets player $D$ in round $j$ .
Determine all pairs $(n, k)$ for which there exists an $(n, k)$ -tournament.

Combinatorics Solution and answer checking →
Find all integers $n \geqslant 3$ with the following property: for all real numbers $a_{1}, a_{2}, \ldots, a_{n}$ and $b_{1}, b_{2}, \ldots, b_{n}$ satisfying $\left|a_{k}\right|+\left|b_{k}\right|=1$ for $1 \leqslant k \leqslant n$ , there exist $x_{1}, x_{2}, \ldots, x_{n}$ , each of which is either $-1$ or $1$ , such that
$\left|\sum_{k=1}^{n} x_{k} a_{k}\right|+\left|\sum_{k=1}^{n} x_{k} b_{k}\right| \leqslant 1$

Combinatorics Solution and answer checking →
Let $n$ be a positive integer. Given an $n \times n$ board, the unit cell in the top left corner is initially coloured black, and the other cells are coloured white. We then apply a series of colouring operations to the board. In each operation, we choose a $2 \times 2$ square with exactly one cell coloured black and we colour the remaining three cells of that $2 \times 2$ square black.
Determine all values of $n$ such that we can colour the whole board black.
(Peru)

Combinatorics Solution and answer checking →
Find all positive integers $n$ for which we can fill in the entries of an $n \times n$ table with the following properties:
- each entry can be one of $I$ , $M$ and $O$ ;
- in each row and each column, the letters $I$ , $M$ and $O$ occur the same number of times; and
- in any diagonal whose number of entries is a multiple of three, the letters $I$ , $M$ and $O$ occur the same number of times.

Combinatorics Solution and answer checking →
A cube of side length $2021$ is given. In how many ways can we place a $1 \times 1 \times 1$ cubelet on the border of this cube in such a way that the newly formed solid can be completely filled using $k \times 1 \times 1$ , $1 \times k \times 1$ and $1 \times 1 \times k$ cuboids, for some $k \in \mathbb{N} \setminus \{1\}$ ?

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.

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 and are reproduced from open datasets under their licences; every problem page names its source. Free to copy for classroom use.