For teachers / Printable sets /Stage 8 · Combinatorics

Stage 8 · Combinatorics

10 problems · IMO Shortlist mid-range; USAMO P2/P5 · mathsolympiadprep.com

Print or save as PDF The answer key prints on its own page at the end.

1. Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.

   IMO Shortlist

   Combinatorics Solution and answer checking →

2. Let $S$ be a finite set of points in the plane. A linear partition of $S$ is an unordered pair $\{A,B\}$ of subsets of $S$ such that $A \cup B = S$, $A \cap B = \emptyset$, and $A$ and $B$ lie on opposite sides of some straight line disjoint from $S$ ($A$ or $B$ may be empty). Let $L_S$ be the number of linear partitions of $S$. For each positive integer $n$, find the maximum of $L_S$ over all sets $S$ of $n$ points.

   Putnam

   Combinatorics Solution and answer checking →

3. For each integer $n\ge 1,$ compute the smallest possible value of $$\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor$$ over all permutations $(a_1,\dots,a_n)$ of $\{1,\dots,n\}.$

   *

   IMO Shortlist

   Combinatorics Solution and answer checking →

4. Consider $9$ points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $\,n\,$ such that whenever exactly $\,n\,$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

   International Mathematical Olympiad

   Combinatorics Solution and answer checking →

5. Let $n > 1$ be a given integer. An $n \times n \times n$ cube is composed of $n^3$ unit cubes. Each unit cube is painted with one colour. For each $n \times n \times 1$ box consisting of $n^2$ unit cubes (in any of the three possible orientations), we consider the set of colours present in that box (each colour is listed only once). This way, we get $3n$ sets of colours, split into three groups according to the orientation.

   It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$, the maximal possible number of colours that are present.

   IMO Shortlist

   Combinatorics Solution and answer checking →

6. Denote by $\mathbb{Z}^2$ the set of all points $(x,y)$ in the plane with integer coordinates. For each integer $n \geq 0$, let $P_n$ be the subset of $\mathbb{Z}^2$ consisting of the point $(0,0)$ together with all points $(x,y)$ such that $x^2 + y^2 = 2^k$ for some integer $k \leq n$. Determine, as a function of $n$, the number of four-point subsets of $P_n$ whose elements are the vertices of a square.

   Putnam

   Combinatorics Solution and answer checking →

7. For an integer $n>2$, the tuple $(1, 2, \ldots, n)$ is written on a blackboard. On each turn, one can choose two numbers from the tuple such that their sum is a perfect square and swap them to obtain a new tuple. Find all integers $n > 2$ for which all permutations of $\{1, 2,\ldots, n\}$ can appear on the blackboard in this way.

   Balkan MO Shortlist

   Combinatorics Solution and answer checking →

8. Let $\mathbb{Z}_{\ge 0}$ be the set of all nonnegative integers. Find all the functions $f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0}$ satisfying the relation
   $$f(f(f(n))) = f(n+1 ) +1$$
   for all $n\in \mathbb{Z}_{\ge 0}$.

   IMO Shortlist

   Combinatorics Solution and answer checking →

9. Given $n$ countries with three representatives each, $m$ committees $A(1),A(2), \ldots, A(m)$ are called a cycle if

   (i) each committee has $n$ members, one from each country;
   (ii) no two committees have the same membership;
   (iii) for $\text{i 1, 2, ,m}$, committee $A(i)$ and committee $\text{A(i 1)}$ have no member in common, where $\text{A(m 1)}$ denotes $A(1);$
   (iv) if $\text{1 < |i j| < m 1,}$ then committees $A(i)$ and $A(j)$ have at least one member in common.

   Is it possible to have a cycle of 1990 committees with 11 countries?

   IMO Shortlist

   Combinatorics Solution and answer checking →

10. Superchess is played on on a $12 \times 12$ board, and it uses superknights, which move between opposite corner cells of any $3\times4$ subboard. Is it possible for a superknight to visit every other cell of a superchessboard exactly once and return to its starting cell ?

    IMO Longlist

    Combinatorics Solution and answer checking →

Answer key — Stage 8 · Combinatorics

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

1. $\text{[ 1 if n is a power of 2 2 otherwise . ]}$ open
2. $\binom{n}{2} + 1$ open
3. $\lfloor \log_2(n) \rfloor + 1$ open
4. $33$ open
5. ${\frac{n(n+1)(2n+1)}{6}}$ open
6. $5n+1$ open
7. $n \geq 14$ open
8. $f(n)=n+1,\ f(n)=\begin{cases}n+1,\ n=2k\\ n+5,\ n=4k+1\\ n-3,\ n=4k+3 \end{cases}$ open
9. $\text{yes}$ open
10. $No$ 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.

Apache-2.0