Library / Austrian Mathematical Olympiad /34 of 54

Austrian Mathematical Olympiad

Combinatorics Difficulty 6.1 National Olympiad Prove it Austria

A postman has $n$ parcels of weights $1$ , $2$ , $3$ , $4$ , $\ldots$ , $n$ . He wants to divide the parcels into three groups of equal weight. Is this possible for

a. $n = 2011$

b. $n = 2012$ ?

Solution

In the first case, the total weight
$1 + 2 + \cdots + 2010 + 2011 = \frac{2011 \cdot 2012}{2}$
is not a multiple of $3$ . Therefore, there is no solution in this case.

In the second case, we distribute the first $8$ parcels as follows: Parcels $1$ , $2$ , $3$ , $6$ (of total weight $12$ ) are put into the first group. Parcels $4$ and $8$ (also of total weight $12$ ) are put into the second group. Parcels $5$ and $7$ (of total weight $12$ ) are put into the third group.

The remaining $2004$ parcels $9$ , $\ldots$ , $2012$ are first divided into $334$ blocks of consecutive integers $6k + 3$ , $6k + 4$ , $6k + 5$ , $6k + 6$ , $6k + 7$ , $6k + 8$ for $1 \le k \le 334$ . Of each block, $6k + 3$ and $6k + 8$ (of weight $12k + 11$ ) are put into the first group. Parcels $6k + 4$ and $6k + 7$ are put into the second group. Finally, parcels $6k + 5$ and $6k + 6$ are put into the third group. This yields a valid partition. $\square$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.