Dejemos que $$ G_n:=\max\{length(S), \ \text{such that $ S $ is a solid sequence and } S\subset\{1,\dots,n\}\}. $$ Entonces uno tiene $G_1=1$ , $G_2=3$ , $G_3=7$ .
Su afirmación es que $G_{2^{m-1}-1}<2^m$ . Esto es falso. El siguiente ejemplo muestra que $$ G_{F_n}\ge 2^{n-1}-1,\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad (Ex) $$ donde $F_n$ es el $n$ término de la secuencia de Fibonacci. En particular, para $m=5$ tenemos $15=2^{m-1}-1>F_7=13$ y así $$ G_{15}=G_{2^{m-1}-1}\ge G_{F_7}\ge 2^{6}-1>2^m=32. $$ En particular, la secuencia sólida de longitud $63$ sin un plazo superior a $15$ es $$ (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), $$
Tenga en cuenta que $(Ex)$ proporciona un límite inferior (como lo hará cualquier familia de ejemplos), en lugar del límite superior deseado.
Sospecho que este límite inferior es también un límite superior asintótico, pero no tengo pruebas.
$\bf{The\ Example}:$ Para cada $n\ge 1$ proporcionaremos inductivamente un ejemplo de una secuencia $S^{(n)}$ con $length(S^{(n)})=2^{n}$ , de tal manera que $(S^{(n)}_1,\dots,S^{(n)}_{2^n-1})$ es una secuencia sólida, y tal que $S^{(n)}\subset\{1,\dots,F_{n+1}\}$ .
Primeros términos:
Para $n=1$ claramente $S^{(1)}=(1,1)$ satisface la hipótesis.
Para $n=2$ la secuencia es $S^{(2)}=(1,2,1,2)$ .
Para $n=3$ tenemos $S^{(3)}=(1,3,2,3,1,3,2,3)$ y
para $n=4$ tenemos $S^{(4)}=(1,5,3,5,2,5,3,5,1,5,3,5,2,5,3,5)$ .
La construcción inductiva es la siguiente:
Hemos establecido $$ 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} $}. $$
Ahora demostramos inductivamente que $(S^{(n)}_1,\dots,S^{(n)}_{2^n-1})$ es una secuencia sólida.
Para ello probamos un poco más:
(1.) Para cada $S=S^{(n)}$ y dos conjuntos consecutivos cualesquiera $A,B\subset S^{(n)}$ Si $\#A>\#B$ entonces $\sum_{i\in A}S_i> \sum_{i\in B}S_i$ .
(2.) Para cada $S=S^{(n)}$ y dos conjuntos consecutivos cualesquiera $A,B\subset S^{(n)}$ Si $\#A=\#B+1$ entonces $\sum_{i\in A}S_i- \sum_{i\in B}S_i<F_{n+2}$ .
(3.) Para cada $S=S^{(n)}$ y dos conjuntos consecutivos cualesquiera $A,B\subset S^{(n)}$ Si $\#A=\#B$ entonces $|\sum_{i\in A}S_i- \sum_{i\in B}S_i|<F_{n+1}$ .
(4.) Para cada $S=S^{(n)}$ y dos conjuntos consecutivos cualesquiera $A,B\subset S^{(n)}$ Si $\#A=\#B$ entonces $\sum_{i\in A}S_i\ne \sum_{i\in B}S_i$ , excepto cuando $\#A=\#B=2^{n-1}$ (y así $A\cup B=S^{(n)}$ ).
Aquí consideramos al mismo tiempo los dos casos en los que $A$ se encuentra por encima de $B$ y viceversa.
Para $n=1,2,3$ se puede verificar (1.)--(4.) a mano.
Supongamos que (1.), (2.), (3.), (4.) son ciertos para $n-1$ .
Primero demostramos (3.) y (4.).
Si $\#A=\#B =2k$ , entonces (3.) y (4.) están claros por la hipótesis inductiva, ya que ambos conjuntos tienen el mismo número de $F_{n+1}$ 's. Una vez que se eliminan por hipótesis inductiva las sumas satisfacen las condiciones requeridas (hay que tener cuidado con el caso $A\cup B= S^{(n)}$ ).
Si $\#A=\#B =2k-1$ , entonces uno de ellos tiene un término más con valor $F_{n+1}$ y el otro tiene un término más de $S^{(n-1)}$ . Supongamos que $A$ tiene un término más con valor $F_{n+1}$ y escribir $A_{n-1}$ y $B_{n-1}$ para los conjuntos $A$ y $B$ con todos los términos $F_{n+1}$ eliminado. Entonces $$ 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}, $$ lo que demuestra (3.) y (4.) en este caso. De hecho, la igualdad es clara, y la última desigualdad se desprende del punto de la hipótesis inductiva (1.), ya que $\#A_{n-1}<\#B_{n-1}$ . La primera desigualdad se desprende del punto de la hipótesis inductiva (2.), ya que $\#B_{n-1}=\#A_{n-1}+1$ y así $$ \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}. $$
Ahora demostramos (1.).
Supongamos que $\#A>\#B$ y definir $A_{n-1}$ y $B_{n-1}$ como antes. Entonces $$ \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 $$ y hay dos casos:
a) $\#A_{n-1}>\# B_{n-1}$ y $\#\{F_{n+1}\ \text{ in }A\}$ es mayor o igual que $\#\{F_{n+1}\ \text{ in }B\}$ . En este caso claramente $\sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i>0$ por hipótesis inductiva el punto (1.) y así el punto (1.) para $n$ sigue directamente.
b) $\#A_{n-1}=\# B_{n-1}$ y $\#\{F_{n+1}\ \text{ in }A\}$ es mayor que $\#\{F_{n+1}\ \text{ in }B\}$ . En este caso, si $\sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i>0$ , entonces el punto (1.) para $n$ sigue directamente. Si no $0<\sum_{i\in B_{n-1}}S^{(n-1)}_i-\sum_{i\in A_{n-1}}S^{(n-1)}_i<F_n$ por el punto de la hipótesis inductiva (3.), y así $$ \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. $$
Finalmente demostramos (2.).
Supongamos que $\#A=\#B+1$ y definir $A_{n-1}$ y $B_{n-1}$ como antes. Entonces $$ \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 $$ y hay dos casos:
a) $\#A_{n-1}>\# B_{n-1}$ y $\#\{F_{n+1}\ \text{ in }A\}$ es igual a $\#\{F_{n+1}\ \text{ in }B\}$ . En este caso claramente $\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}$ por hipótesis inductiva el punto (2.) y así el punto (2.) para $n$ sigue directamente.
b) $\#A_{n-1}=\# B_{n-1}$ y $\#\{F_{n+1}\ \text{ in }A\}$ es $\#\{F_{n+1}\ \text{ in }B\}$ más uno. En este caso, por la hipótesis inductiva punto (3.) tenemos $$ \sum_{i\in A_{n-1}}S^{(n-1)}_i-\sum_{i\in B_{n-1}}S^{(n-1)}_i< F_n $$ y así $$ \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}, $$ como se desee.
Claramente $(1.)$ y $(4.)$ juntos implican que $(S^{(n)}_1,\dots,S^{(n)}_{2^n-1})$ es una secuencia sólida.
