Existência / inexistência de uma sequência com subsequência crescente e diminuindo subsequência?

Question

Pode existir qualquer sequência inteira $ a $ de comprimento $ n $ com todos os elementos exclusivosque a duração de sua maior subsequência crescente, bem como a de sua mais longa subsequência diminuindo é menor que $ \ displaystyle \ lFlor \ frac {n} {2} \ rfloor $ ?

Se sim, então dê um exemplo de tal seqüência.Caso contrário, alguém pode apresentar uma prova de que não pode existir uma sequência?

(apenas para adicionar alguma substância, pode ser mostrado que pode existir tais sequências, dado qualquer valor arbitrário de $ n> 1 $ ?)

Answer 1

A resposta para a pergunta da OP é, não se $ n \ le 7 $ e sim, caso contrário.

---

.

Para dado qualquer inteiro positivo $ R $ e $ s $ , O celebrado ERDős-Szekeres Teorem mostra que para qualquer seqüência de números reais distintos com comprimento pelo menos $ (R - 1) (S - 1) + 1 $ contém uma subsequência crescente de comprimento $ R $ < / span> ou uma subsequência decrescente de comprimento $ s $ .

Acontece que o limite, $ (R-1) (S-1) +1 $ é apertado. Isto é, para qualquer número positivo $ R $ e $ S $ , há uma seqüência de números distintos com comprimento $ (R-1) (s-1) $ que não contém aumentar subsequência de comprimento $ R $ e sem diminuir subsequência de comprimento $ s $ .

Aqui está um exemplo.

$$ \ begin {array} {} & s-1, & s-2, & \ cdots, & 2, & 1 \\ & 2 (S-1), & (S-1) + S-2, & \ CDOts, & (S-1) + 2, & (S-1) + 1 \\ & \ vDOTS & \ VDOTS & \ VDOTS & \ VDOTS & \ VDOTS \\ & (R-2) (S-1), & (R-3) (S-1) + S-2, & \ CDOts, & (R-3) (S-1) +2, & (R- 3) (S-1) +1 \\ & (R-1) (S-1), & (R-2) (S-1) + S-2, & \ CDOts, & (R-2) (S-1) +2, & (R- 2) (S-1) +1 \\ \ end {matry} $$

Considere os números acima, lendo da esquerda para a direita e depois de cima para baixo. Em outras palavras, a sequência é $ s-1 $ para baixo para $ 1 $ , seguido por $ 2 (s-1) $ para baixo para $ (S-1) +1 $ , etc e finalmente seguido por < span class="recipiente de matemática"> $ (R-1) (s-1) $ para baixo para $ (R-2) (S-1) +1 $ , tudo em etapa de $ 1 $ .

É fácil ver que não há aumento de subsequência de comprimento r e sem subsequência decrescente de comprimento $ s $ .

Por exemplo, quando $ r= s= 5 $ , temos $$ 4,3,2,1, \ \, 8,7,6,5, \ \, 12,11,10,9,9, \ \, 16,15,14,13 $$ que não tem subsequência crescente de comprimento $ 5 $ nem diminuindo subsequência de comprimento $ 5 $ .

---

.

Se deixarmos $ r= S $ , a seção acima implica que, para qualquer número positivo $ n $ < Existe uma sequência inteira de comprimento $ n $ com todos os elementos exclusivos, tal que o comprimento de sua subsequência mais longa, bem como a de sua mais longa subsequência diminuindo é no máximo $ \ lceil \ sqrt n \ rceil $ . E $ \ lceil \ sqrt n \ rceil $ é o limite superior apertado.

desde $$ \ lceil \ sqrt n \ rceil \ g \ lFlor \ frac n2 \ rfloor \ \ rfloor {para todos} n \ le 7 $$ e $$ \ lceil \ sqrt n \ rceil \ lt \ lfloor \ frac n2 \ rfloor \ \ text {para todos} n \ gt 7, $$ A resposta para a pergunta da OP é, não, se $ n \ le 7 $ e sim, caso contrário.

Por exemplo, para $ n= 8 $ , temos sequência $ 3,2,1,6,5, 4,9,8,7 $ .

Answer 2

Aqui está uma construção direta de tal seqüência para qualquer múltiplo de quatro. É composto de quatro corridas igualmente dimensionadas de inteiros consecutivos.

As primeiras e terceiras corridas estão aumentando. A segunda e quarta corridas estão diminuindo. As corridas usam intervalos de números de modo que $ r_2 . Por exemplo, com $ 4N= 16 $ ,

$$ 9,10,11,12 | 4,3,2,1 | 5,6,7,8 | 16, 15,14,13 $$

A subsequência crescente mais longa é o comprimento $ n + 2 $ . Por exemplo, no acima, onde $ 4N= 16 $ , o maior aumento da subsequência tem comprimento $ 6 $ ( $ 1 | 5, 6, 7, 8 | 16 $ ). Nenhuma subsequência crescente é maior:

• Não é possível escolher um elemento de ambas as execuções crescentes, uma vez que qualquer elemento na primeira execução crescente desqualifica todos os segundos aumentando.
• Não é possível escolher mais de um elemento de decrescimento de execução

Um argumento simétrico aplica-se para as subsequências decrescentes.

Como $ n + 2 << 2N $ , isso funciona como um contraexemplo para qualquer sequência múltipla de quatro. Você pode facilmente pad com elementos de seqüência extra para diferentes comprimentos não múltiplos.

Eu me deparei com esta construção considerando uma sequência que era uma "colina" (aumentando, depois diminuindo), que atende perfeitamente sua condição. Quebrar essas longas corridas pode ser feito fazendo duas colinas (aumentando, diminuindo, aumentando, diminuindo), que essa sequência faz, garantindo que a inclinação para cima / para baixo de uma 'colina' não seja continuada pela outra.

Answer 3

Há também sequências curtas que satisfazem sua solicitação. Considerar, por exemplo, os primeiros 16 termos da sequência binária van der corporto $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ Em geral existe uma sequência $ T $ de comprimento $ n \ geq1 $ contendo uma subsequência mais longa decomprimento $ x \ geq 1 $ e uma subsequência mais longa diminuindo do comprimento $ y \ GEQ 1 $ se esomente se os números $ x $ , $ y $ e $ n $ satisfazer as condições $ x \ cdot y \ geq n $ e $ x + y \ leqn + 1 $ , veja aqui .Observe que a referência dá uma prova construtiva.

Answer 4

Essas seqüências existem.É suficiente gerar uma sequência aleatória suficiente.Se você verificar o livro de Dan Romik, a matemática surpreendente de subsequências mais longas aumentando , o Teorema 1.1 afirma que

$$ \ frac {\ ell_n} {\ sqrt n} \ a 2, $$

onde $ \ ell_n $ é um comprimento esperado de aumentar subsequência em uma permutação aleatória de tamanho $ n $ .O mesmo para diminuir.Portanto, para grande o suficiente $ n $ Existem uma sequência com seqüências crescentes e decrescentes de comprimentos na maioria das $ 5 \ sqrtn $ , caso contrário:

$$ 2 e [\ ell_n]= e [| Decr_n |+ | incr_n |] \ G 5 \ sqrt n, $$

O que contradiz o teorema.