For teachers / Printable sets /Stage 10 · Combinatorics

Stage 10 · Combinatorics

8 problems · Hardest shortlist tier · mathsolympiadprep.com

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

Let $N$ be a positive integer. Geoff and Ceri play a game in which they start by writing the numbers $1, 2, \ldots, N$ on a board. They then take turns to make a move, starting with Geoff. Each move consists of choosing a pair of integers $(k, n)$ , where $k \geqslant 0$ and $n$ is one of the integers on the board, and then erasing every integer $s$ on the board such that $2^{k} \mid n-s$ . The game continues until the board is empty. The player who erases the last integer on the board loses.
Determine all values of $N$ for which Geoff can ensure that he wins, no matter how Ceri plays.
(Indonesia)

IMO Shortlist

Combinatorics Solution and answer checking →
There are $2010$ students and $100$ classrooms in the Olympiad High School. At the beginning, each of the students is in one of the classrooms. Each minute, as long as not everyone is in the same classroom, somebody walks from one classroom into a different classroom with at least as many students in it (prior to his move). This process will terminate in $M$ minutes. Determine the maximum value of $M$ .

United States — Team Selection Test

Combinatorics Solution and answer checking →
Let $m$ and $n$ be positive integers with $mn$ even. Jetze is going to cover an $m \times n$ -board (with $m$ rows and $n$ columns) with domino tiles, in such a way that every domino tile covers exactly two squares, domino tiles do not protrude out of the board or overlap one another, and every square is covered by a domino tile. Merlijn then is going to colour all domino tiles on the board either red or blue. Determine the smallest non-negative integer $V$ (depending on $m$ and $n$ ) such that Merlijn can always make sure that in each row, the number of squares covered by a red domino tile and the number of squares covered by a blue domino tile differ by at most $V$ , no matter in what way Jetze covers the board.

IMO Team Selection Test 3

Combinatorics Solution and answer checking →
Player Zero and player One play a game on an $n \times n$ -board ( $n \ge 1$ ). The columns of this $n \times n$ -board are numbered by powers of two, so we have column 1, column 2, column 4 through column $2^{n-1}$ . Alternately, players put their own number (i.e. Zero a 0 and One a 1) in one of the empty squares. Player Zero starts. When the board is full, the game ends and a (reverse binary) number is created in each row by adding the values of the boxes with a 1 in them. So if $n = 4$ , then a row with 0101 contains the number $0 \cdot 1 + 1 \cdot 2 + 0 \cdot 4 + 1 \cdot 8 = 10$ .
a) For which natural numbers $n$ can player One always ensure that at least one of the rows is divisible by 4?
b) And for which natural numbers $n$ can player One always ensure that at least one of the rows is divisible by 3?

IMO Team Selection Test 1

Combinatorics Solution and answer checking →
Let $m$ and $n$ be fixed positive integers. Tsvety and Freyja play a game on an infinite grid of unit square cells. Tsvety has secretly written a real number inside of each cell so that the sum of the numbers within every rectangle of size either $m \times n$ or $n \times m$ is zero. Freyja wants to learn all of these numbers.
One by one, Freyja asks Tsvety about some cell in the grid, and Tsvety truthfully reveals what number is written in it. Freyja wins if, at any point, Freyja can simultaneously deduce the number written in every cell of the entire infinite grid. (If this never occurs, Freyja has lost the game and Tsvety wins.)
In terms of $m$ and $n$ , find the smallest number of questions that Freyja must ask to win, or show that no finite number of questions can suffice.

USA TST

Combinatorics Solution and answer checking →
Given positive integers $n$ and $k \le n$ . Consider an equilateral triangular board with side $n$ , which consists of circles: in the first (top) row there is one circle, in the second row there are two circles, ..., in the bottom row there are $n$ circles (see the figure below). Let us place checkers on this board so that any line parallel to a side of the triangle (there are $3n$ such lines) contains no more than $k$ checkers. Denote by $T(k, n)$ the largest possible number of checkers in such a placement.

a) Prove that the following upper bound is true:
$T(k, n) \le \left\lfloor \frac{k(2n + 1)}{3} \right\rfloor .$
b) Find $T(1, n)$ and $T(2, n)$ .

Selection Tests of the Belarusian Team to the IMO

Combinatorics Solution and answer checking →
Given positive integers $k$ and $n$ ( $n \ge 2$ ), find the minimum constant $c$ satisfying this assertion: if $G$ is a simple $kn$ -regular graph (the degree of each vertex is $kn$ ) with $m$ vertices, then each vertex can be coloured one of $n$ colours, such that the number of “mono edges” is at most $cm$ . Here, a mono edge is an edge incident to two vertices of the same colour.

China National Team Selection Test

Combinatorics Solution and answer checking →
Six stacks $S_{1}, \ldots, S_{6}$ of coins are standing in a row. In the beginning every stack contains a single coin. There are two types of allowed moves:
Move 1: If stack $S_{k}$ with $1 \leq k \leq 5$ contains at least one coin, you may remove one coin from $S_{k}$ and add two coins to $S_{k+1}$ .
Move 2: If stack $S_{k}$ with $1 \leq k \leq 4$ contains at least one coin, then you may remove one coin from $S_{k}$ and exchange stacks $S_{k+1}$ and $S_{k+2}$ .
Decide whether it is possible to achieve by a sequence of such moves that the first five stacks are empty, whereas the sixth stack $S_{6}$ contains exactly $2010^{2010^{2010}}$ coins.

IMO Shortlist

Combinatorics Solution and answer checking →

Answer key — Stage 10 · Combinatorics

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

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.

CC-BY-4.0