Maths Olympiad Prep

Library / /8 of 8

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Italy

Problem:
In how many different ways can the numbers {21,31,41,51,61,71,81}\{21,31,41,51,61,71,81\} be arranged in a row so that, however four of them in consecutive positions are chosen, their sum is divisible by three?

Solution

Solution:
The answer is 144.
For brevity we will call good an arrangement of the given numbers a1,,a7a_{1}, \ldots, a_{7} that satisfies the required properties. Let us try to establish some properties of good arrangements.

i) for an arrangement to be good it does not matter which numbers are chosen from the given set but only what the remainder of their division by 3 is.

ii) the remainder of each of the elements of a good arrangement (a1,,a7)(a_{1}, \ldots, a_{7}) is completely determined once that of the first four elements has been chosen.
Indeed, since the arrangement is good, both a2++a5=(a1++a4)+(a5a1)a_{2}+\ldots+a_{5}=(a_{1}+\ldots+a_{4})+(a_{5}-a_{1}) and a2++a5a_{2}+\ldots+a_{5} and a1++a4a_{1}+\ldots+a_{4} are divisible by three; moreover, a2++a5=(a1++a4)+(a5a1)a_{2}+\ldots+a_{5}=(a_{1}+\ldots+a_{4})+(a_{5}-a_{1}) so that (a5a1)(a_{5}-a_{1}) must also be. This means that a5a_{5} and a1a_{1}, when divided by 3, give the same remainder.
Similarly we can say the same thing for the pairs a2,a6a_{2}, a_{6} and a3,a7a_{3}, a_{7}.

iii) The remainder of the division by three of an integer can only be 0, 1 or 2. For brevity we will speak of numbers of type 0, 1 or 2 depending on which of the three possibilities occurs.
The sum of four numbers is divisible by three only if (up to order) the four numbers are of the following types:
0,0,0,0or1,2,0,0or1,2,1,2. 0,0,0,0 \quad \text{or} \quad 1,2,0,0 \quad \text{or} \quad 1,2,1,2.
In the set available to us, however, we have only 3 numbers of type 00 (21,51,8121,51,81), only two (31,6131,61) of type 1 and only two (41,7141,71) of type 2. This excludes the first and the third possibility. The latter because, by property ii), we would necessarily have to continue with other elements of type 1 or 2 which, however, we do not have available.

iv) Not all arrangements of 1,2,0,0 are possible: again by property ii), there cannot be two numbers of type "0" among the first three places. If this were not the case we would find again two numbers of type "0" among the last three places for a total of four, but we have only three available.
Consequently the number in the fourth position must necessarily be of type "0" and the types of the elements a1,a2,a3a_{1}, a_{2}, a_{3} must be identical to those of the elements a5,a6,a7a_{5}, a_{6}, a_{7} respectively.
At this point we are able to compute how many good arrangements there are:
- the element in the fourth position can only be chosen among 21,51,8121, 51, 81, that is, in three different ways;
- in the first three positions there must be a number of type 0, one of type 1 and one of type 2. The possible ways to order the types of numbers are 6.
- for each of the types of the first three elements of the sequence it is possible to choose between two different numbers of the set. So for each of the ways of ordering the types there are 2×2×2=82 \times 2 \times 2=8 different ways of choosing.
- once the choices in the previous points have been made, the elements in the last three positions are uniquely determined.

Summing up, the number of good arrangements is:
3×6×8=144. 3 \times 6 \times 8=144.

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 translated into English from it; metadata (topic, difficulty) added by this project.