Say we have an infinite sequence of natural numbers $A$ such that no $k$ subsequences can be found adjacent such that the average of the elements in any subsequence is equal for all $k$ subsequences. Sorry about my poor description, an example would be that $\{2, 3, 4, 1\}$ wouldn't work for $k=2$ because $\{2, 3\}$ and $\{4, 1\}$ are adjacent and both their averages are $\frac{5}{2}$. $\{2, 3, 10, 4, 1\}$ would work however because $\{2, 3\}$ and $\{4, 1\}$ are no longer adjacent. Anyway, my question is: which sequence that follows this has the lowest sum for $k$? If that's too general, then which for $k=2$? Honestly, any information on the behavior of this sequence would be great. To me, it looks like for $k=2$ is $\{1, 2, 1, 3, 1, 2, 1, 4 ...\}$ but I have no idea how to prove that it is. Thanks.

  • $\begingroup$ "which sequence that follows this has the lowest sum?" Any infinite sequence of natural numbers has infinite sum, so it's not clear what you mean by "lowest sum". $\endgroup$ – Gerry Myerson Jan 24 '13 at 2:57
  • $\begingroup$ Also, if you carry out your $k=2$ sequence one more term, I assume your intention is for the next term to be $1$, but $3,1,2$ and $1,4,1$ have the same sum (whence, same average). $\endgroup$ – Gerry Myerson Jan 24 '13 at 3:01
  • $\begingroup$ Huh, thanks for pointing that out. Didn't see that initially. And also, is it not true that an infinite sequence of natural numbers has a countably infinite sum, such that $\{1, 1, 1...\}$ is less than $\{2, 2, 2...\}$? $\endgroup$ – user1825464 Jan 24 '13 at 3:06
  • $\begingroup$ If anything, what I really need to know is if I can show how the sequence can be written in big O notation, maybe it follows $O(x^{1 +n})$? $\endgroup$ – user1825464 Jan 24 '13 at 3:29
  • $\begingroup$ I don't know of any consistent system in which it can be stated that $1+1+\dots\lt2+2+\dots$. I don't know what you mean by $O(x^{1+n})$ in this context. Do you mean something like, the $n$th term can be taken to be $O(n^k)$? $\endgroup$ – Gerry Myerson Jan 24 '13 at 5:30

Let's try to sharpen the question:

Your example shows that you are considering non-overlapping subsequences of $A$, i.e., you partition $A$ into fragments of fixed length. So let's try some definitions:

  1. For any sequence $s$, let $W_k(s)$ be the sequence whose $n$th term (counting from 0) is given by $s_{kn} + s_{kn+1} + s_{kn+2} + ... + s_{kn+k-1}$. Note that since the average of $k$ numbers is just their sum divided by $k$, we can consider sums instead of averages. ($W$ is for window: A fixed-length fragment).

  2. For any sequence $s$, define $\Sigma s$ to be the sequence whose $n$th term is the sum of the first $n$ terms of $s$.

  3. For two sequences $s$ and $t$, we say that $s < t$ if there is some $m \in N$ such that $s_n < t_n$ for all $n > m$ (I.e., $s<t$ "in the limit").

So, for any $k$ you want to find the sequence $A$ that satisfies the following:

  1. $W_k(A)$ has no adjacent terms that are equal.

  2. If $B$ is another sequence for which $W_k(B)$ has no repeated terms, $\Sigma A < \Sigma B$ (in the sense of definition 2).

If all this is correct, my candidate for minimum at $k=2$ would be the following periodic sequence (I have bracketed the period):

$$A = [ 1, 1, 1, 2, ] 1, 1, 1, 2, ...$$

This matches the condition, since $W_2(A) = 2, 3, 2, 3, ...$.

I believe it's pretty easy to see how to construct similar sequences for $k > 2$. A more interesting problem would be if you misunderstood the conditions, and the adjacent subsequences are overlapping rather than disjoint. (E.g., terms $s_0s_1, s_1s_2, s_2s_3, ...$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.