Averages in a sequence
Cláudio Buffara and William McWorter, Jr.
Tue, 25 Mar 2003
Let x_{1}, ..., x_{100} 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:
 Initially we prove that x_{1} = x_{2} = ... = x_{9};
 Assuming the x_{i} are integer, we prove the averages condition imply that the sequence is constant;
 We extend the result to rational x_{i};
 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_{1}≤ x_{2} ≤ ... ≤ x_{100}.
Let's consider x_{1}, ..., x_{8}. Call their average M.
Given the ordering of the x_{i}, the 9subset with smallest average is
Suppose x_{9} > M. Then [x_{1} + ... + x_{9}]/9 = [8·M + x_{9}]/9 > M implies that every other 9subset will have average > M. Contradiction. Therefore,
Suppose now that x_{1} < x_{8}. Then x_{1} < M < x_{8}. But since x_{9}≤ M, we have x_{8} > x_{9}. Contradiction. Therefore,
STEP 2
As before, we can reorder the x_{i} so that
By subtracting x_{1} from each element of the sequence and then dividing out any common factor, we obtain a new nondecreasing sequence such that:

x_{1} = ... = x_{9} = 0 and
LCM(x_{1}, ..., x_{100}) = 1.
Suppose the sequence is not constant. In this case there must exist an index k such that
Consider the following 8term subsequence: x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{k}. Its average is
By hypothesis, there is a 9term subsequence whose average is also m + r/8.
Calling the sum of the terms of that 9term 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 100term 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 nset is a basis of the subspace of R spanned by the terms of the sequence.
Let that basis be {r_{1}, r_{2}, ..., r_{n}}.
It follows that for 1≤ i ≤ 100, we have: x_{i} = a_{i, 1}×r_{1} + a_{i, 2}×r_{2} + ... + a_{i, n}×r_{n}, where the
Now, the average condition on the x_{i} implies that for every 8subset A of

(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_{1} + a_{i, 2}×r_{2} + ... + a_{i, n}×r_{n}] =
(1/9)×SUM(j in B) [a_{j, 1}×r_{1} + a_{j, 2}×r_{2}+ ... + 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}
+ [(1/8)×SUM(i in A) a_{i, 2}  (1/9)×SUM(j in B) a_{j, 2}]×r_{2}
+ ...
+ [(1/8)×SUM(i in A) a_{i, n}  (1/9)×SUM(j in B) a_{j, n}]×r_{n} = 0.
But {r_{1}, r_{2}, ..., 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 8subset A of

(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 {
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
Evolution of a Solution
 Tue, 25 Mar 2003
 Sat, 16 July 2005
 Mon, 23 January 2006
Contact Front page Contents Up
Copyright © 19962018 Alexander Bogomolny
71930233