Averages in a sequence

Cláudio Buffara and William McWorter, Jr.
Tue, 25 Mar 2003

Let x₁, ..., x₁₀₀ be a sequence of real numbers. Suppose that for every subsequence of 8 terms, there exists a subsequence of 9 terms with the same average as that of the 8. Show that all x_i are equal.

Solution

The solution has 4 steps:

1. Initially we prove that x₁ = x₂ = ... = x₉;
2. Assuming the x_i are integer, we prove the averages condition imply that the sequence is constant;
3. We extend the result to rational x_i;
4. Finally, we use the fact that R (the set of real numbers) is a vector space over Q (the set of rational numbers) to establish the result for real x_i.

STEP 1

Since the order of the terms has no relevance to the problem, we can rename the x_i so that we have: x₁ x₂ ... x₁₀₀.

Let's consider x₁, ..., x₈. Call their average M.

Given the ordering of the x_i, the 9-subset with smallest average is {x₁, ..., x₈, x₉}.

Suppose x₉ > M. Then [x₁ + ... + x₉]/9 = [8·M + x₉]/9 > M implies that every other 9-subset will have average > M. Contradiction. Therefore, x₉ M.

Suppose now that x₁ < x₈. Then x₁ < M < x₈. But since x₉ M, we have x₈ > x₉. Contradiction. Therefore, x₁ = x₈ = M = x₉.

STEP 2

As before, we can reorder the x_i so that x₁ x₂ ... x₁₀₀. Also, it's true that the average condition implies that x₁ = ... = x₉.

By subtracting x₁ from each element of the sequence and then dividing out any common factor, we obtain a new non-decreasing sequence such that:

x₁ = ... = x₉ = 0 and
LCM(x₁, ..., x₁₀₀) = 1.

Suppose the sequence is not constant. In this case there must exist an index k such that x_k = a > 0, with GCD(a, 8) = 1. Then a = 8m + r, with m a non-negative integer and r in {1, 3, 5, 7}.

Consider the following 8-term subsequence: x₁, x₂, x₃, x₄, x₅, x₆, x₇, x_k. Its average is a/8 = m + r/8 with r in {1, 3, 5, 7}.

By hypothesis, there is a 9-term subsequence whose average is also m + r/8.

Calling the sum of the terms of that 9-term subsequence "n" (an integer), we have:

n/9 = m + r/8, or n = 9m + 9r/8,

which is not an integer since 8 does not divide 9r. Contradiction.

Therefore, we must conclude that the sequence is constant.

STEP 3

The case where the terms are rational can be reduced to the integer case, by multiplying all the terms by the LCM of all the denominators. Therefore, we have established the result for any 100-term sequence with rational terms.

STEP 4

Since R is a vector space over Q, there must be a set of linearly independent real numbers (let's say with n elements) which generates the 100 terms of the sequence (x_i). In other words, the n-set is a basis of the subspace of R spanned by the terms of the sequence.

Let that basis be {r₁, r₂, ..., r_n}.

It follows that for 1 i 100, we have: x_i = a_{i, 1}×r₁ + a_{i, 2}×r₂ + ... + a_{i, n}×r_n, where the a_{i, j} are uniquely determined rational numbers.

Now, the average condition on the x_i implies that for every 8-subset A of {1, 2, ..., 100} there is a 9-subset B of {1, 2, ..., 100} such that

(1/8)×SUM(i in A) x_i = (1/9)×SUM(j in B) x_j.

Expressing the x_i in terms of basis elements, we get:

(1/8)×SUM(i in A) [a_{i, 1}×r₁ + a_{i, 2}×r₂ + ... + a_{i, n}×r_n] =
(1/9)×SUM(j in B) [a_{j, 1}×r₁ + a_{j, 2}×r₂+ ... + a_{j, n}×r_n],

so that

[(1/8)×SUM(i in A) a_{i, 1} - (1/9)×SUM(j in B) a_{j, 1}]×r₁
+ [(1/8)×SUM(i in A) a_{i, 2} - (1/9)×SUM(j in B) a_{j, 2}]×r₂
+ ...
+ [(1/8)×SUM(i in A) a_{i, n} - (1/9)×SUM(j in B) a_{j, n}]×r_n = 0.

But {r₁, r₂, ..., r_n } is a basis (in particular, it's a linearly independent set). Therefore, for each k (1 k n):

(1/8)×SUM(i in A) a_{i, k} - (1/9)×SUM(j in B) a_{j, k} = 0.

It follows that, for each k (1 k n) and every 8-subset A of {1, 2, ..., 100} there is a 9-subset B of {1, 2, ..., 100} such that:

(1/8)×SUM(i in A) a_{i, k} = (1/9)×SUM(j in B) a_{j, k}.

In other words, for each k (1 k n) the sequence {a_{1, k}, a_{2, k}, ..., a_{100, k}} satisfies the average condition.

But, for each k (1 k n) and each i (1 i 100), a_{i, k} is rational.

Given that we already know that any rational sequence which satisfies the average condition is constant, it follows that, for each k (1 k n), the sequence {a_{1, k}, a_{2, k}, ..., a_{100, k}} is constant.

This, in turn, implies that all the x_i have the same coordinates relative to the basis {r₁, r₂, ..., r_n}. In other words, the sequence {x₁, x₂, ..., x₁₀₀ } is constant.

Evolution of a Solution

• Tue, 25 Mar 2003
• Sat, 16 July 2005
• Mon, 23 January 2006

Copyright © 1996-2008 Alexander Bogomolny