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 $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$ .

Combinatorics Solution and answer checking →
Suppose there are 101 persons sitting around a round table in an arbitrary order. The $k$ th person possesses $k$ pieces of cards, $k = 1, \dots, 101$ . We call it a transition if one transits one of his cards to one of his adjacent persons. Find the minimum positive number $k$ , such that whatever the order of the seating, there is a way of no more than $k$ transitions so that each person possesses 51 cards.

Combinatorics Solution and answer checking →
On a board with $2024$ rows and $2023$ columns, Turbo the snail tries to move from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then moves one step at a time to an adjacent cell sharing a common side. He wins if he reaches any cell in the last row. However, there are $2022$ predetermined, hidden monsters in $2022$ of the cells, one in each row except the first and last rows, such that no two monsters share the same column. If Turbo unfortunately reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move.
Suppose Turbo is allowed to take $n$ attempts. Determine the minimum value of $n$ for which he has a strategy that guarantees reaching the last row, regardless of the locations of the monsters.
(Hong Kong)
Comment. One of the main difficulties of solving this question is in determining the correct expression for $n$ . Students may spend a long time attempting to prove bounds for the wrong value for $n$ before finding better strategies.
Students may incorrectly assume that Turbo is not allowed to backtrack to squares he has already visited within a single attempt. Fortunately, making this assumption does not change the answer to the problem, though it may make it slightly harder to find a winning strategy.

Combinatorics Solution and answer checking →
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)

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.

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?

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)$ .

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.

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