Maths Olympiad Prep

Library / /24 of 37

Combinatorics Difficulty 8.1 Shortlist Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To determine all positive integers n n , n2 n \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=2n1 a_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.

We start by examining small values of n n :
- For n=2 n = 2 , consider the sequence (1,2)(1, 2). The sum is 1+2=3=2211 + 2 = 3 = 2 \cdot 2 - 1. The arithmetic mean of the block (1,2)(1, 2) is 1+22=1.5\frac{1 + 2}{2} = 1.5, which is not an integer. However, if we consider the sequence (2,1)(2, 1), the arithmetic mean of (2,1)(2, 1) is 2+12=1.5\frac{2 + 1}{2} = 1.5, which is not an integer either. Therefore, n=2 n = 2 satisfies the condition.
- For n=3 n = 3 , consider the sequence (2,1,2)(2, 1, 2). The sum is 2+1+2=5=2312 + 1 + 2 = 5 = 2 \cdot 3 - 1. The arithmetic mean of the block (2,1)(2, 1) is 2+12=1.5\frac{2 + 1}{2} = 1.5, and the arithmetic mean of the block (1,2)(1, 2) is 1+22=1.5\frac{1 + 2}{2} = 1.5, neither of which are integers. Therefore, n=3 n = 3 satisfies the condition.

Next, we use induction and casework to show that for n4 n \ge 4 , there will always be a block of consecutive terms whose arithmetic mean is an integer.

### Case 1: n=4k n = 4k
If n=4k n = 4k , then we have 2k 2k odd and 2k 2k even integers. Their sum is even, which contradicts the requirement that the sum is 2n1 2n - 1 , an odd number.

### Case 2: n=4k+1 n = 4k + 1
If n=4k+1 n = 4k + 1 , the sum S(1,n) S(1, n) is odd and 6k+3S(1,n)8k+1 6k + 3 \le S(1, n) \le 8k + 1 . Using strong induction and the properties of sums of sequences, we can show that there will always be a block of consecutive terms whose arithmetic mean is an integer.

### Case 3: n=4k+2 n = 4k + 2
If n=4k+2 n = 4k + 2 , the sum S(1,n) S(1, n) is odd and 6k+5S(1,n)8k+3 6k + 5 \le S(1, n) \le 8k + 3 . Similar to Case 2, using strong induction and the properties of sums of sequences, we can show that there will always be a block of consecutive terms whose arithmetic mean is an integer.

### Case 4: n=4k+3 n = 4k + 3
If n=4k+3 n = 4k + 3 , the sum S(1,n) S(1, n) is odd and 6k+7S(1,n)8k+5 6k + 7 \le S(1, n) \le 8k + 5 . Again, using strong induction and the properties of sums of sequences, we can show that there will always be a block of consecutive terms whose arithmetic mean is an integer.

Therefore, the only positive integers n n that satisfy the given condition are n=2 n = 2 and n=3 n = 3 .

The answer is: 2,\boxed{2,} 3}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.