Maths Olympiad Prep

Library / /16 of 45

Combinatorics Difficulty 8.4 Shortlist Prove it United States

Determine all positive integers nn, n2n \ge 2, such that the following statement is true:
If (a1,a2,,an)(a_1, a_2, \ldots, a_n) is a sequence of positive integers with a1+a2++an=2n1a_1 + a_2 + \cdots + a_n = 2n - 1, then there is a block of (at least two) consecutive terms in the sequence with their (arithmetic) mean being an integer.

Solution

The statement is true for all n4n \ge 4 but not for n=2n = 2 or n=3n = 3. In those two cases, the sequences (1,2)(1, 2) and (2,1,2)(2, 1, 2) provide counterexamples.

Now, let (a1,,an)(a_1, \dots, a_n) be any sequence of positive integers, and let sk=a1++ak2ks_k = a_1 + \dots + a_k - 2k for k=1,2,,nk = 1, 2, \dots, n, and define s0=0s_0 = 0. Let us say that a sequence is good if it satisfies the property in the problem (no block of length at least two has an integer arithmetic mean). Define (i,j)(i, j) to be a divisible pair if jisjsij - i \mid s_j - s_i. It is clear that (a1,,an)(a_1, \dots, a_n) is good if and only if there is no divisible pair (i,j)(i, j) such that ji2|j - i| \ge 2.

We will show that (a1,,an)(a_1, \dots, a_n) is not good if n4n \ge 4. Note that sn=a1++an2n=1s_n = a_1 + \dots + a_n - 2n = -1, and for each kk, sk+1sk=ak+121s_{k+1} - s_k = a_{k+1} - 2 \ge -1. We consider several possible values of s2s_2.

* Suppose s22s_2 \le -2. Since s1s01=1s_1 \ge s_0 - 1 = -1 and s2s11s_2 \ge s_1 - 1, it follows that s1=1s_1 = -1. Then n1sns1n-1 \mid s_n - s_1.

* Suppose s2=1s_2 = -1. Then n2sns2n-2 \mid s_n - s_2.

* Suppose s2=0s_2 = 0. Then 20s2s02-0 \mid s_2 - s_0.

* Suppose s21s_2 \ge 1. Since sn=1s_n = -1, and sk+1s_{k+1} can be no smaller than sks_k, there must be some ii between 2 and nn such that si=0s_i = 0. Then i0sis0i-0 \mid s_i - s_0.

We have thus shown that there is at least one divisible pair among the pairs (1,n)(1, n), (2,n)(2, n), (0,2)(0, 2), and (0,i)(0, i), for some 2<i<n2 < i < n. Note that if n4n \ge 4, the two numbers in each of those pairs must differ by at least two. Thus, (a1,,an)(a_1, \dots, a_n) is not good when n4n \ge 4, finishing the proof.

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.