Maths Olympiad Prep

Library / /38 of 38

Combinatorics Difficulty 8.0 Shortlist Prove it China

Let a1,a2,,a11a_1, a_2, \dots, a_{11} be 1111 distinct positive integers with their sum less than 20072007, and write the numbers 1,2,,20071, 2, \dots, 2007 in order on the blackboard. Now we define a group of 2222 ordered operations:
The ii-th operation is to take any number on the blackboard, and then add aia_i to it, if 1i111 \le i \le 11 or minus ai11a_{i-11} from it, if 12i2212 \le i \le 22.
If the final result after such a group of operations is an even permutation of 1,2,,20071, 2, \dots, 2007, then we call it a "good" group; if the result is an odd permutation of 1,2,,20071, 2, \dots, 2007, then we call it a "second good" group.
Our question is: Which is greater? The number of "good" groups or that of "second good" groups? And by how many more?

Solution

The answer is: The "good" groups is more than the "second good" groups by i=111ai\prod_{i=1}^{11} a_i.

More generally, we write numbers 1,2,,n1, 2, \dots, n in order on the blackboard, and define a group of ll ordered operations: The ii-th operation is to take any number on the blackboard, and then add bib_i (biZ,1ilb_i \in \mathbb{Z}, 1 \le i \le l) to it.
If the final result after such a group of operations is an even/odd permutation of 1,2,,n1, 2, \dots, n, then we call it a "good"/"second good" group. And the difference between the number of "good" groups and that of "second good" groups is defined as
f(b1,b2,,bl;n). f(b_1, b_2, \cdots, b_l; n).
Now let us study the property of ff.

Firstly, interchanging bib_i and bjb_j for any 1i,jl1 \le i, j \le l will not affect the value of ff. As a matter of fact, it only results in the exchange of the iith and jjth operations in a group, and will not affect the final result after the group's operations. So the value of ff remains the same.

Secondly, we only need to count the number of "good"/"second good" groups with property PP — a property attributed to any operation group which keeps the numbers on the blackboard distinctive from one another after each operation. We can prove that the difference between the numbers of "good" and "second good" groups with property PP is also equal to ff.

In fact, we only need to prove that the numbers of "good" and "second good" groups without property PP are the same. Suppose the iith operation of a "good"/"second good" group without property PP results in the equal between the ppth and qqth number on the blackboard (1p<qn1 \le p < q \le n). We change the following lil-i operations in this way: operations on the ppth number are changed to operations on the qqth number, and vice versa. It is easy to verify that the resulted permutation on the blackboard of new operation group would be a (p,q)(p, q) transposition of the permutation of the original operation group. Then the parities of the two permutations are in opposite signs. And that means the numbers of "good" and "second good" groups without property PP are the same.

Now, let a1,a2,,ama_1, a_2, \cdots, a_m be mm distinct positive integers with their sum less than nn. We prove by the principle of mathematical induction that
f(a1,a2,,am,a1,a2,,am;n)=i=1mai.(1) f(a_1, a_2, \dots, a_m, -a_1, -a_2, \dots, -a_m; n) = \prod_{i=1}^{m} a_i. \quad (1)
If m=1m=1, consider a "good"/"second good" group with property PP. It must be in such a way: The first operation is to take a number from na1+1,na2+2,,nn - a_1 + 1, n - a_2 + 2, \dots, n on the blackboard, and add a1a_1 to it; next operation is to add a1-a_1 again to it. So the number of "good" groups is a1a_1, while that of "second good" groups is 00. Therefore (1)(1) holds.

Assume that (1)(1) holds for m1m-1. We now consider case mm. According to what discussed above, we may assume that a1<a2<<ana_1 < a_2 < \dots < a_n, and
f(a1,a2,,am,a1,a2,,am;n)=f(a1,a2,a3,,am,a2,a3,,am,a1;n). \begin{aligned} & f(a_1, a_2, \dots, a_m, -a_1, -a_2, \dots, -a_m; n) \\ &= f(a_1, -a_2, -a_3, \dots, -a_m, a_2, a_3, \dots, a_m, -a_1; n). \end{aligned}
For a group with property PP, the first operation must be done on the last a1a_1 numbers on the blackboard; the second operation be done on the first a2a_2 numbers; the third operation done on the first a2+a3a_2 + a_3 numbers; ... the mmth operation done on the first a2++am<na1a_2 + \dots + a_m < n - a_1 numbers. And the m+12m1m+1 \sim 2m-1 th operations will also be done on the first na1n - a_1 numbers. Otherwise the sum of the first na1n - a_1 numbers will be less than 1+2++(na1)1 + 2 + \dots + (n - a_1), a contradiction to property PP.

Therefore, the 22m22 \sim 2m-2 operations must be done on the first na1n-a_1 numbers, and the result must be an even/odd permutation of 1,2,,(na1)1, 2, \dots, (n-a_1), which corresponds to each one of a1a_1 even/odd permutations of 1,2,,n1, 2, \dots, n derived from original operation groups. therefore
f(a1,a2,a3,,am,a2,a3,,am,a1;n)=a1f(a2,a3,,am,a2,a3,,am;na1). \begin{aligned} & f(a_1, -a_2, -a_3, \dots, -a_m, a_2, a_3, \dots, a_m, -a_1; n) \\ &= a_1 f(-a_2, -a_3, \dots, -a_m, a_2, a_3, \dots, a_m; n - a_1). \end{aligned}
By induction we have
f(a2,a3,,am,a2,a3,,am;na1)=f(a2,a3,,am,a2,a3,,am;na1)=j=2maj. \begin{aligned} & f(-a_2, -a_3, \cdots, -a_m, a_2, a_3, \cdots, a_m; n - a_1) \\ &= f(a_2, a_3, \cdots, a_m, -a_2, -a_3, \cdots, -a_m; n - a_1) \\ &= \prod_{j=2}^{m} a_j. \end{aligned}
That means (1)(1) holds for mm.

Now take n=2007n = 2007 and m=11m = 11 in (1)(1). Thus arriving at the value of j=111aj\prod_{j=1}^{11} a_j.

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.