Maths Olympiad Prep

Library / /58 of 87

Combinatorics Difficulty 6.1 National Olympiad Prove it Austria

A postman has nn parcels of weights 11, 22, 33, 44, \ldots, nn. He wants to divide the parcels into three groups of equal weight. Is this possible for

a. n=2011n = 2011

b. n=2012n = 2012?

Solution

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

In the second case, we distribute the first 88 parcels as follows: Parcels 11, 22, 33, 66 (of total weight 1212) are put into the first group. Parcels 44 and 88 (also of total weight 1212) are put into the second group. Parcels 55 and 77 (of total weight 1212) are put into the third group.

The remaining 20042004 parcels 99, \ldots, 20122012 are first divided into 334334 blocks of consecutive integers 6k+36k + 3, 6k+46k + 4, 6k+56k + 5, 6k+66k + 6, 6k+76k + 7, 6k+86k + 8 for 1k3341 \le k \le 334. Of each block, 6k+36k + 3 and 6k+86k + 8 (of weight 12k+1112k + 11) are put into the first group. Parcels 6k+46k + 4 and 6k+76k + 7 are put into the second group. Finally, parcels 6k+56k + 5 and 6k+66k + 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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