IMO 2020 · Problem 3

There are \(4n\) pebbles of weights \(1,2,3,\ldots,4n\). Each pebble is coloured in one of \(n\) colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied:

  • The total weights of both piles are the same.
  • Each pile contains two pebbles of each colour.

Official text of the problem. Official problem paper (PDF)

Solution

Partition the pebbles into the \(2n\) pairs \[ \{1,4n\},\ \{2,4n-1\},\ \ldots,\ \{2n,2n+1\}, \] where the numbers denote weights. Every pair has total weight \(4n+1\). We will assign each pair wholly to one pile.

Construct a multigraph whose vertices are the \(n\) colours. Each pair gives an edge joining the colours of its two pebbles. Multiple edges are allowed, and a pair of the same colour gives a loop. Counting a loop twice towards the degree, every vertex has degree \(4\), because there are four pebbles of each colour.

Consider any connected component with \(v\) vertices. The sum of its degrees is \(4v\), so it has \(2v\) edges; in particular, its number of edges is even.

Furthermore, this component has an Euler circuit: a closed trail using every edge exactly once. Here is a proof of this fact. Start at any vertex and follow unused edges until no further edge is available. Since all degrees are even, the trail can stop only at its starting vertex. Removing the edges of this closed trail leaves even degrees at every vertex. If some edges remain unused, connectedness ensures that some vertex on the trail is incident with an unused edge. Starting there, construct another closed trail of unused edges and insert it into the first trail. Repeating this procedure eventually gives the required Euler circuit.

Label the edges of this circuit alternately \(A,B,A,B,\ldots\). Its length is even, so the last and first edges also have different labels.

At each vertex, pair each arriving edge incidence with the outgoing edge incidence immediately following it in the circuit, treating the circuit cyclically. These pairs partition the four incidences at that vertex, and each pair contains one incidence labelled \(A\) and one labelled \(B\). Thus every vertex has exactly two incidences of each label. This includes loops, whose two incidences correspond to their two pebbles.

Do this independently in every connected component. Now put both pebbles of each edge labelled \(A\) into the first pile, and both pebbles of each edge labelled \(B\) into the second pile.

The incidence count shows that each pile contains exactly two pebbles of every colour. Consequently, each pile contains \(2n\) pebbles, forming \(n\) of our original pairs. Since every pair weighs \(4n+1\), both piles have total weight \[ n(4n+1). \] Both required conditions hold.

The solution was checked against the official IMO shortlist solutions.