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 →
There are $2025$ people and $66$ given colors. Each person has $66$ balls, one of each color, with a total weight of $1$ for all $66$ balls.
Find the smallest real number $C$ such that, no matter how the balls are weighted, one can always select exactly one ball from each person so that for every color, the total weight of the selected balls of that color does not exceed $C$ .

Combinatorics Solution and answer checking →
At a gala banquet, $12n + 6$ chairs, where $n \in \mathbb{N}$ , are equally arranged around a large round table. A seating will be called a proper seating of rank $n$ if a gathering of $6n + 3$ married couples sit around this table such that each seated person also has exactly one sibling (brother/sister) of the opposite gender present (siblings cannot be married to each other) and each man is seated closer to his wife than his sister. Among all proper seats of rank $n$ find the maximum possible number of women seated closer to their brother than their husband. (The maximum is taken not only across all possible seating arrangements for a given gathering, but also across all possible gatherings.)

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.