Problem:
In how many different ways can the numbers 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 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 is completely determined once that of the first four elements has been chosen.
Indeed, since the arrangement is good, both and and are divisible by three; moreover, so that must also be. This means that and , when divided by 3, give the same remainder.
Similarly we can say the same thing for the pairs and .
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:
In the set available to us, however, we have only 3 numbers of type (), only two () of type 1 and only two () 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 must be identical to those of the elements 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 , 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 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: