Comparing the average of a subset of a finite sequence to the overall average

Question

Let:

• $S_n$ be a sequence of $n$ integers: $s_0, s_1, \dots, s_{n-1}$
• $r(S_n,m)$ be a function that returns a new sequence where the order is the same but the first element in the sequence is $(m \% n)$ where % is the modulo operation

Example: $r(S_n,2) = s_2, s_3, \dots, s_{n-1}, s_0, s_1$

• $a(S, n)$ be a function that returns the average of the first $n$ elements of a sequence.

Example: If $S = 1,3,4$, then $a(S,2) = \dfrac{1+3}{2} = 2$

Question:

For any given sequence of integers of length $n$, does there always exist an integer $m < n$ where for all $i \le n$, $a(r(S_n,m),i) \ge a(S_n,n)$

I am interested in either a proof that $m$ always exists or a counter example.

Here's an example:

Let:

• $S = 1,2,3,4,5,6,7,8,9$
• $a(S,9) = \dfrac{(9)(10)}{2(9)} = 5$

For $m = 5$:

• $a(r(S,5),1) = 5$
• $a(r(S,5),2) = 5.5$
• $a(r(S,5),3) = 6$
• $a(r(S,5),4) = 6.5$
• $a(r(S,5),5) = 7$
• $a(r(S,5),6) = 6$
• $a(r(S,5),7) > 5.4$
• $a(r(S,5),8) > 5.1$

It seems to me that it should be possible to find a counter example. I am unable to. I am wondering if my intuition is incorrect in this case.

Answer 1

Let us first ponder this famous puzzle:

Several gas stations on a circular track have between them just enough gas for one car to make a complete round trip. Prove that if you start at the right station with an empty tank you will be able to make it all the way around.

The elegant solution to this puzzle is this. Imagine that you start with enough gas for a full trip at an arbitrary point on this track. Go around and at each station, fill up your tank and then record your tank level. When you are done with your trip, identify the station at which your recorded tank level was the smallest (say, $X$). Now perform a second trip starting at this station, starting with $X$ in your tank, again recording tank levels. Clearly your records on this second trip will match your records on your first trip, merely in a circularly shifted order. So if you now do a third trip starting at this station but with an empty tank of gas, again recording tank levels, you will get the same tank records, but with $X$ deducted from each record. None of those recordings will be negative, making this a viable trip.

Now let us turn to your question. Suppose that each gallon of gas gives us 1 mile of mileage, and consider a track of length $\sum s_i$ miles, with $n$ equally spaced stations providing $s_0, s_1, \ldots, s_{n-1}$ gallons of gas. A starting point on this track is viable iff the average of the first $i$ station amounts is at least as large as the average of all station amounts for all $i$. This translates exactly to the question you ask. The famous puzzle tells us that a viable starting station exists, and thus that the answer to your question is yes.