For teachers / Printable sets /Stage 7 · Combinatorics

Stage 7 · Combinatorics

10 problems · National Olympiad second round; IMO P1/P4 · mathsolympiadprep.com

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

Let $n \geq 3$ be an integer. Rowan and Colin play a game on an $n \times n$ grid of squares, where each square is colored either red or blue. Rowan is allowed to permute the rows of the grid and Colin is allowed to permute the columns. A grid coloring is orderly if:
- no matter how Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and
- no matter how Colin permutes the columns of the coloring, Rowan can then permute the rows to restore the original grid coloring. In terms of $n$ , how many orderly colorings are there?

USAJMO

Combinatorics Solution and answer checking →
Does there exist a function $s\colon \mathbb{Q} \rightarrow \{-1,1\}$ such that if $x$ and $y$ are distinct rational numbers satisfying ${xy=1}$ or ${x+y\in \{0,1\}}$ , then ${s(x)s(y)=-1}$ ? Justify your answer.
*

IMO Shortlist

Combinatorics Solution and answer checking →
Let $n$ be a positive integer. Initially, a $2n \times 2n$ grid has $k$ black cells and the rest white cells. The following two operations are allowed :
(1) If a $2\times 2$ square has exactly three black cells, the fourth is changed to a black cell;
(2) If there are exactly two black cells in a $2 \times 2$ square, the black cells are changed to white and white to black.
Find the smallest positive integer $k$ such that for any configuration of the $2n \times 2n$ grid with $k$ black cells, all cells can be black after a finite number of operations.

China Team Selection Test

Combinatorics Solution and answer checking →
Six children are evenly spaced around a circular table. Initially, one has a pile of $n > 0$ sweets in front of them, and the others have nothing. If a child has at least four sweets in front of them, they may perform the following move: eat one sweet and give one sweet to each of their immediate neighbours and to the child directly opposite them. An arrangement is called perfect if there is a sequence of moves which results in each child having the same number of sweets in front of them. For which values of $n$ is the initial arrangement perfect?

BMO Round 1 2020

Combinatorics Solution and answer checking →
Some lattice points in the Cartesian coordinate system are colored red, the rest of the lattice points are colored blue. Such a coloring is called finitely universal, if for any finite, non-empty $A \subset \mathbb{Z}$ there exists $k\in \mathbb{Z}$ such that the point $(x,k)$ is colored red if and only if $x\in A$ .

KöMaL problem A 2022

Combinatorics Solution and answer checking →
Is it true that for every infinite sequence $x_1,x_2,\ldots$ of integers satisfying $|x_{k+1}-x_k|=1$ for every positive integer $k$ , there exists a sequence $k_1<k_2<\ldots<k_{2014}$ of positive integers such that as well the indices $k_1,k_2,\ldots,k_{2014}$ as the numbers $x_{k_1},x_{k_2},\ldots,x_{k_{2014}}$ (in this order) form arithmethic progressions?
Proposed by: E. Csóka, Warwick and Ben Green, Oxford
(5 pont)

KöMaL problem A 2014

Combinatorics Solution and answer checking →
There are $2n-1$ light bulbs in a row. Initially the middle (the $n$ -th) one is lit, and all the others are off. In one step it is allowed to choose two non-adjacent off bulbs between which all the bulbs are lit, and to change the state of these two bulbs as well as of all the bulbs between them (for example, from the configuration $\cdot$ ооо $\cdot$ one obtains о $\cdot$ $\cdot$ ). What is the maximum number of steps that can be performed?
(Dušan Đukić)

Serbian Mathematical Olympiad

Combinatorics Solution and answer checking →
Let $N$ be a positive integer. A cube $(2N+1) \times (2N+1) \times (2N+1)$ is made of $(2N+1)^3$ unit cubes; each unit cube is either black or white. It turned out that among any 8 unit cubes which form a cube $2 \times 2 \times 2$ the number of black unit cubes is not greater than 4. Find the greatest possible total number of black unit cubes.

Serbian Mathematical Olympiad

Combinatorics Solution and answer checking →
Five teams play in a soccer competition where each team plays one match against each of the other four teams. A winning team gains 5 points and a losing team 0 points. For a 0-0 draw both teams gain 1 point, and for other draws (1-1, 2-2, etc.) both teams gain 2 points. At the end of the competition, we write down the total points for each team, and we find that they form five consecutive integers. What is the minimum number of goals scored?

Irish Mathematical Olympiad

Combinatorics Solution and answer checking →
Martino thinks he has discovered a method to win at roulette, or at least not to lose too much money. He always bets on red. He starts by betting 1 euro; every time he loses he doubles the previous bet, while every time he wins he bets 1 euro on the next play. One day he has 31 euros with him and goes to play, deciding that he will leave as soon as either he has lost 5 times in a row, or he has won 5 times in a row, or he has run out of money before one of these two possibilities has occurred.
a. What will be the minimum number of plays he must make in order to finish playing with 31 euros, if he leaves after 5 losses?
b. What will be the minimum number of plays he must make in order to finish playing with 31 euros, if he leaves after 5 wins?
c. If he leaves after 5 wins, what will be his minimum final capital?

Olimpiadi di Matematica

Combinatorics Solution and answer checking →

Answer key — Stage 7 · Combinatorics

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

$2(n! + 1)$ open
$\text{Yes}$ open
$n^2 + n + 1$ open
Not recorded — 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.