Averages in a sequence

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

Let x1, ..., x100 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 xi are equal.

Solution

The solution has 4 steps:

  1. Initially we prove that x1 = x2 = ... = x9;
  2. Assuming the xi are integer, we prove the averages condition imply that the sequence is constant;
  3. We extend the result to rational xi;
  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 xi.

STEP 1

Since the order of the terms has no relevance to the problem, we can rename the xi so that we have: x1≤ x2 ≤ ... ≤ x100.

Let's consider x1, ..., x8. Call their average M.

Given the ordering of the xi, the 9-subset with smallest average is {x1, ..., x8, x9}.

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

Suppose now that x1 < x8. Then x1 < M < x8. But since x9≤ M, we have x8 > x9. Contradiction. Therefore, x1 = x8 = M = x9.

We have thus established that x1 = ... = x8 = x9.

STEP 2

As before, we can reorder the xi so that x1≤ x2 ≤ ... ≤ x100. Also, it's true that the average condition implies that x1 = ... = x9.

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

    x1 = ... = x9 = 0 and
    LCM(x1, ..., x100) = 1.

Suppose the sequence is not constant. In this case there must exist an index k such that xk = 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: x1, x2, x3, x4, x5, x6, x7, xk. 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 (xi). 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 {r1, r2, ..., rn}.

It follows that for 1≤ i ≤ 100, we have: xi = ai, 1×r1 + ai, 2×r2 + ... + ai, n×rn, where the ai, j are uniquely determined rational numbers.

Now, the average condition on the xi 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) xi = (1/9)×SUM(j in B) xj.

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

    (1/8)×SUM(i in A) [ai, 1×r1 + ai, 2×r2 + ... + ai, n×rn] =
    (1/9)×SUM(j in B) [aj, 1×r1 + aj, 2×r2+ ... + aj, n×rn],

so that

    [(1/8)×SUM(i in A) ai, 1 - (1/9)×SUM(j in B) aj, 1]×r1
    + [(1/8)×SUM(i in A) ai, 2 - (1/9)×SUM(j in B) aj, 2]×r2
    + ...
    + [(1/8)×SUM(i in A) ai, n - (1/9)×SUM(j in B) aj, n]×rn = 0.

But {r1, r2, ..., rn } is a basis (in particular, it's a linearly independent set). Therefore, for each k (1≤ k ≤ n):

    (1/8)×SUM(i in A) ai, k - (1/9)×SUM(j in B) aj, 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) ai, k = (1/9)×SUM(j in B) aj, k.

In other words, for each k (1≤ k ≤ n) the sequence {a1, k, a2, k, ..., a100, k} satisfies the average condition.

But, for each k (1≤ k ≤ n) and each i (1 ≤ i ≤ 100), ai, 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 {a1, k, a2, k, ..., a100, k} is constant.

This, in turn, implies that all the xi have the same coordinates relative to the basis {r1, r2, ..., rn}. In other words, the sequence {x1, x2, ..., x100 } is constant.

Evolution of a Solution


Related material
Read more...

  • The Means
  • Averages, Arithmetic and Harmonic Means
  • Expectation
  • The Size of a Class: Two Viewpoints
  • Averages of divisors of a given integer
  • Family Statistics: an Interactive Gadget
  • Arithmetic and Geometric Means
  • Geometric Meaning of the Geometric Mean
  • A Mathematical Rabbit out of an Algebraic Hat
  • AM-GM Inequality
  • The Mean Property of the Mean
  • Harmonic Mean in Geometry
  • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2017 Alexander Bogomolny

     62687347

    Search by google: