7
$\begingroup$

Call a finite sequence $\{a_1,a_2,..,a_n\}\in \mathbb{N}_{≥1}$ solid if, for all contiguous subsequences $S=\{a_i,a_{i+1},\dots,a_{i+j}\}$, there does not exist an adjacent contiguous subsequence $S'=\{a_{(i+j)+1},a_{(i+j)+2},\dots,a_{(i+j)+k}\}$ such that $$\sum_{a\in S}a=\sum_{b\in S'}b$$ For example, the sequences $\{1,3,2,3,4,2,4\}$ and $\{1,3,2,3,1,3,2,8\}$ are solid. However, $\{1,2,1,3,2\}$ and $\{1,3,2,3,5\}$ are not. Here is what I am trying to show...

Claim: If for some solid sequence $\{a_1,a_2,..,a_n\}$ we have $n\geq2^m$ for some positive integer $m$, then there exits $i\leq n$ such that $a_i\geq2^{m-1}$

This feels like it should have a neat inductive proof. The base case is clear (as any four term sequence must include a $3$). I just can't seem to see the trick for the induction (though it is possible that the proof may not even involve the technique at all). So, first of all, is this claim correct? And, if so, what's the proof? Can a stronger lower bound than $2^{m-1}$ be demonstrated? If the claim is not correct, what bounds can we put on the greatest term of a solid sequence of length $n$?

Update:It seems like a bound of $2^{m-1}$ is indeed quite weak. What better (possibly asymptotic) bound could be proved?

$\endgroup$
4
  • $\begingroup$ how many sums are there possible ... $\endgroup$ – user451844 Aug 9 '17 at 1:45
  • $\begingroup$ @RoddyMacPhee I don't know, it seems like finding the number of possible sums would be harder than finding a lower bound on the maximal term though... $\endgroup$ – Romain S Aug 9 '17 at 1:47
  • $\begingroup$ Answer to your last question for small $n$ can be easily obtained by a simple computer program. $\endgroup$ – Alex Ravsky Aug 13 '17 at 3:36
  • 1
    $\begingroup$ @AlexRavsky Yes, I have ran such a program and confirmed it for small cases as well, but the question is does this hold for all positive integers $n$? $\endgroup$ – Romain S Aug 13 '17 at 3:58
3
+50
$\begingroup$

Let $$ G_n:=\max\{length(S), \ \text{such that $S$ is a solid sequence and } S\subset\{1,\dots,n\}\}. $$ Then one has $G_1=1$, $G_2=3$, $G_3=7$.

Your claim is that $G_{2^{m-1}-1}<2^m$. This is false. The example below shows that $$ G_{F_n}\ge 2^{n-1}-1,\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (Ex) $$ where $F_n$ is the $n$th term in the Fibonacci sequence. In particular, for $m=5$, we have $15=2^{m-1}-1>F_7=13$, and so $$ G_{15}=G_{2^{m-1}-1}\ge G_{F_7}\ge 2^{6}-1>2^m=32. $$ In particular, the solid sequence of length $63$ with no term higher than $15$ is $$ (1,13,8,13,5,13,8,13,3,13,8,13,5,13,8,13,2,13,8,13,5,13,8,13,3,13,8,13,5,13,8,13, $$ $$ 1,13,8,13,5,13,8,13,3,13,8,13,5,13,8,13,2,13,8,13,5,13,8,13,3,13,8,13,5,13,8), $$

Note that $(Ex)$ provides a lower bound (as will do any family of examples), instead of the desired upper bound.

I suspect that this lower bound is also an asymptotic upper bound, but I have no proof.

$\bf{The\ Example}:$ For each $n\ge 1$ we will provide inductively an example of a sequence $S^{(n)}$ with $length(S^{(n)})=2^{n}$, such that $(S^{(n)}_1,\dots,S^{(n)}_{2^n-1})$ is a solid sequence, and such that $S^{(n)}\subset\{1,\dots,F_{n+1}\}$.

First terms:

For $n=1$ clearly $S^{(1)}=(1,1)$ satisfies the hypothesis.

For $n=2$ the sequence is $S^{(2)}=(1,2,1,2)$.

For $n=3$ we have $S^{(3)}=(1,3,2,3,1,3,2,3)$ and

for $n=4$ we have $S^{(4)}=(1,5,3,5,2,5,3,5,1,5,3,5,2,5,3,5)$.

The inductive construction is the following:

We set $$ S^{(n)}_{2k}:=F_{n+1}\quad\text{and}\quad S^{(n)}_{2k-1}:=S^{(n-1)}_{k}\quad\text{for $k=1,\dots, 2^{n-1}$}. $$

Now we prove inductively that $(S^{(n)}_1,\dots,S^{(n)}_{2^n-1})$ is a solid sequence.

For this we prove a little more:

(1.) For each $S=S^{(n)}$ and any two consecutive sets $A,B\subset S^{(n)}$, if $\#A>\#B$, then $\sum_{i\in A}S_i> \sum_{i\in B}S_i$.

(2.) For each $S=S^{(n)}$ and any two consecutive sets $A,B\subset S^{(n)}$, if $\#A=\#B+1$, then $\sum_{i\in A}S_i- \sum_{i\in B}S_i<F_{n+2}$.

(3.) For each $S=S^{(n)}$ and any two consecutive sets $A,B\subset S^{(n)}$, if $\#A=\#B$, then $|\sum_{i\in A}S_i- \sum_{i\in B}S_i|<F_{n+1}$.

(4.) For each $S=S^{(n)}$ and any two consecutive sets $A,B\subset S^{(n)}$, if $\#A=\#B$, then $\sum_{i\in A}S_i\ne \sum_{i\in B}S_i$, except when $\#A=\#B=2^{n-1}$ (and so $A\cup B=S^{(n)}$).

Here we consider at the same time the two cases in which $A$ lies above $B$ and viceversa.

For $n=1,2,3$ one can verify (1.)--(4.) by hand.

Assume (1.), (2.), (3.), (4.) are true for $n-1$.

We first prove (3.) and (4.).

If $\#A=\#B =2k$, then (3.) and (4.) are clear form the inductive hypothesis, since both sets have the same number of $F_{n+1}$'s. Once you remove them, by inductive hypothesis the sums satisfy the required conditions (one has to be careful with the case $A\cup B= S^{(n)}$).

If $\#A=\#B =2k-1$, then one of them has one term more with value $F_{n+1}$, and the other has one term more of $S^{(n-1)}$. Assume $A$ has one term more with value $F_{n+1}$ and write $A_{n-1}$ and $B_{n-1}$ for the sets $A$ and $B$ with all the terms $F_{n+1}$ removed. Then $$ 0<\sum_{i\in A}S^{(n)}_i-\sum_{i\in B}S^{(n)}_i=F_{n+1}-(\sum_{i\in B_{n-1}}S^{(n-1)}_i-\sum_{i\in A_{n-1}}S^{(n-1)}_i)<F_{n+1}, $$ which proves (3.) and (4.) in this case. In fact, the equality is clear, and the last inequality follows from the inductive hypothesis item (1.), since $\#A_{n-1}<\#B_{n-1}$. The first inequality follows from the inductive hypothesis item (2.), since $\#B_{n-1}=\#A_{n-1}+1$, and so $$ \sum_{i\in B_{n-1}}S^{(n-1)}_i-\sum_{i\in A_{n-1}}S^{(n-1)}_i<F_{(n-1)+2}=F_{n+1}. $$

Now we prove (1.).

Assume $\#A>\#B$ and define $A_{n-1}$ and $B_{n-1}$ as before. Then $$ \sum_{i\in A}S_i-\sum_{i\in B}S_i=F_{n+1}(\#\{F_{n+1}\ \text{ in }A\}-\#\{F_{n+1}\ \text{ in }B\})+ \sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i $$ and there are two cases:

a) $\#A_{n-1}>\# B_{n-1}$ and $\#\{F_{n+1}\ \text{ in }A\}$ is greater than or equal to $\#\{F_{n+1}\ \text{ in }B\}$. In this case clearly $\sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i>0$ by inductive hypothesis item (1.) and so item (1.) for $n$ follows directly.

b) $\#A_{n-1}=\# B_{n-1}$ and $\#\{F_{n+1}\ \text{ in }A\}$ is greater than $\#\{F_{n+1}\ \text{ in }B\}$. In this case, if $\sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i>0$, then item (1.) for $n$ follows directly. Else $0<\sum_{i\in B_{n-1}}S^{(n-1)}_i-\sum_{i\in A_{n-1}}S^{(n-1)}_i<F_n$ by inductive hypothesis item (3.), and so $$ \sum_{i\in A}S_i-\sum_{i\in B}S_i\ge F_{n+1}-\left( \sum_{i\in B_{n-1}}S^{(n-1)}_i-\sum_{i\in A_{n-1}}S^{(n-1)}_i\right)>F_{n+1}-F_n>0. $$

Finally we prove (2.).

Assume $\#A=\#B+1$ and define $A_{n-1}$ and $B_{n-1}$ as before. Then $$ \sum_{i\in A}S_i-\sum_{i\in B}S_i=F_{n+1}(\#\{F_{n+1}\ \text{ in }A\}-\#\{F_{n+1}\ \text{ in }B\})+ \sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i $$ and there are two cases:

a) $\#A_{n-1}>\# B_{n-1}$ and $\#\{F_{n+1}\ \text{ in }A\}$ is equal to $\#\{F_{n+1}\ \text{ in }B\}$. In this case clearly $\sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i<F_{n+1}<F_{n+2}$ by inductive hypothesis item (2.) and so item (2.) for $n$ follows directly.

b) $\#A_{n-1}=\# B_{n-1}$ and $\#\{F_{n+1}\ \text{ in }A\}$ is $\#\{F_{n+1}\ \text{ in }B\}$ plus one. In this case, by inductive hypothesis item (3.) we have $$ \sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i< F_n $$ and so $$ \sum_{i\in A}S_i-\sum_{i\in B}S_i = F_{n+1}+\left( \sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i\right)<F_{n+1}+F_n=F_{n+2}, $$ as desired.

Clearly $(1.)$ and $(4.)$ together imply that $(S^{(n)}_1,\dots,S^{(n)}_{2^n-1})$ is a solid sequence.

$\endgroup$
4
  • $\begingroup$ Thank you very much! Do you know if this can be used to create a upper bound on $G_n$, perhaps asymptotically? How long of a solid sequence can I create using only the first $n$ naturals? $\endgroup$ – Romain S Aug 14 '17 at 18:46
  • $\begingroup$ For $n=3$ one can prove that any solid sequence of length 7 using only 1,2,3, necessarily is a cyclic permutation of $S^{(3)}$ minus one entry. By computer one should be able to prove something similar for $n=4$: That is, any solid sequence of length 15 using only 1,2,3,4,5 necessarily is a cyclic permutation of $S^{(4)}$ minus one entry (this would imply that 4 doesn't appear). If one could prove this in general, it would provide an upper bound. $\endgroup$ – san Aug 14 '17 at 18:55
  • $\begingroup$ Any idea as to how that would be done? $\endgroup$ – Romain S Aug 14 '17 at 19:56
  • $\begingroup$ I have absolutely no idea. But doing it by computer in some cases might give some clues. You tried it for $n=4$? $\endgroup$ – san Aug 14 '17 at 20:21

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.