, 2019

Combinatorics Difficulty 6.4 National olympiad Prove it Netherlands

We consider sequences $a_1, a_2, \dots, a_n$ consisting of $n$ integers. For given $k \le n$ , we can partition the numbers of the sequence into $k$ groups as follows: $a_1$ goes in the first group, $a_2$ in the second group, and so on until $a_k$ which goes in the $k$ -th group. Then $a_{k+1}$ goes in the first group again, $a_{k+2}$ in the second group, and so on. The sequence is called $k$ -composite if this partition has the property that the sums of the numbers in the $k$ groups are equal.

The sequence $1, 2, 3, 4, -2, 6, 13, 12, 17, 8$ , for instance, is 4-composite as
$1 + (-2) + 17 = 2 + 6 + 8 = 3 + 13 = 4 + 12.$
However, this sequence is not 3-composite, as the sums $1 + 4 + 13 + 8$ , $2 + (-2) + 12$ , and $3 + 6 + 17$ do not give equal outcomes.

a. Give a sequence of 6 *distinct* integers that is both 2-composite and 3-composite.

b. Give a sequence of 7 *distinct* integers that is 2-composite, 3-composite, and 4-composite.

c. Find the largest $k \le 99$ for which there exists a sequence of 99 *distinct* integers that is $k$ -composite. (Give an example of such a sequence and prove that such a sequence does not exist for greater values of $k$ .)

Solution

a.
An example of a correct sequence is $5, 7, 6, 3, 1, 2$ . This sequence consists of six distinct numbers and is 2-composite since $5 + 6 + 1 = 7 + 3 + 2$ . It is also 3-composite since $5 + 3 = 7 + 1 = 6 + 2$ .

b.
A possible solution is $8, 17, 26, 27, 19, 10, 1$ . This sequence consists of seven distinct integers and is 2-composite since $8 + 26 + 19 + 1 = 17 + 27 + 10$ . It is 3-composite since $8 + 27 + 1 = 17 + 19 = 26 + 10$ . It is also 4-composite since $8 + 19 = 17 + 10 = 26 + 1 = 27$ .

c.
The largest $k$ for which a $k$ -composite sequence of 99 distinct integers exists, is $k = 50$ . An example of such a sequence is
$1, 2, \dots, 48, 49, 100, 99, 98, \dots, 52, 51.$
The 99 integers in the sequence are indeed distinct and we see that $1 + 99 = 2 + 98 = \dots = 48 + 52 = 49 + 51 = 100$ , so this sequence is 50-composite.

Now suppose that $k > 50$ and that we have a $k$ -composite sequence $a_1, a_2, \dots, a_{99}$ . Consider the group that contains the number $a_{49}$ . Since $49 - k < 0$ and $49 + k > 99$ , this group cannot contain any other number beside $a_{49}$ . Next, consider the group containing the number $a_{50}$ . Since $50 - k < 0$ and $50 + k > 99$ , this group cannot contain any other number beside $a_{50}$ . Hence, the numbers $a_{49}$ and $a_{50}$ each form a group by themselves and must therefore have the same value. But this is not allowed since the 99 numbers in the sequence had to be distinct.

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 and solution reproduced as published; topic and difficulty added by this site.