Maths Olympiad Prep

Library / /22 of 24

Combinatorics Difficulty 6.1 National Olympiad Prove it Philippines

Problem:

Prove that the set {1,2,,2007}\{1,2, \ldots, 2007\} can be expressed as the union of disjoint subsets AiA_{i} (i=1,2,,223i=1,2, \ldots, 223) such that

a. each AiA_{i} contains 9 elements, and

b. the sum of all the elements in each AiA_{i} is the same.

Solution

Solution:

We first arrange the numbers 670,671,,2007670, 671, \ldots, 2007 into 223 rows and 6 columns in the following way:

Figure 1

Let CiC_{i} represent the set containing the numbers in the iith\text{th} row of the above arrangement. It is easy to check that the numbers in each CiC_{i} add up to a constant sum.

We now need to arrange the numbers 1,2,,6691, 2, \ldots, 669 into 223 rows and 3 columns in such a way that the sum of the numbers in each row is the same for all the rows:

1335669
2336667
3337665
\downarrow\downarrow\downarrow
111445449
112446447
113224668
114225666
115226664
\downarrow\downarrow\downarrow
221332452
222333450
223334448

Note that the sum of the numbers in the first and second columns of one row is different from the sum of the numbers in the first and second columns of another row. Since we expect that the sum of the numbers in each row is (669)(670)÷(2)(223)=1005(669)(670) \div (2)(223) = 1005, we choose the number in the third column of a row to be the difference between 1005 and the sum of its numbers in the first and second columns. Thus, the numbers in the third column are distinct. Since the sum of the numbers in the first and second columns in each row ranges from 336 to 558, we expect that the numbers in the third column are the numbers from 1005558=4471005 - 558 = 447 to 1005336=6691005 - 336 = 669.

Let BiB_{i} be the set containing the numbers in the iith\text{th} row of the above arrangement.

The desired decomposition of the set {1,2,,2007}\{1,2, \ldots, 2007\} is Ai=BiCiA_{i} = B_{i} \cup C_{i}, i=1,2,,223i = 1, 2, \ldots, 223.

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.