Esistenza/non esistenza di una sequenza con sottosequenza crescente breve più lunga e sottosequenza decrescente?

Question

Può esistere una sequenza intera $A$ di lunghezza $N$ con tutti gli elementi unici tali che la lunghezza della sua sottosequenza crescente più lunga così come quella della sua sottosequenza decrescente più lunga sia inferiore a $ \displaystyle \lfloor \frac{N}{2} floor $?

Se sì, fornisci un esempio di tale sequenza.Altrimenti qualcuno può fornire una prova che non possa esistere una tale sequenza?

(Solo per aggiungere un po' di sostanza, si può dimostrare che possono esistere tali sequenze, dato un valore arbitrario di $ N > 1 $?)

Answer 1

La risposta alla domanda dell'OP è, no se $ n \ le 7 $ e sì altrimenti.

---

.

per il dato qualsiasi numero intero positivo $ R $ e $ s $ , Il celebre teorema di Erdős-szekeres mostra che per qualsiasi sequenza di numeri reali distinti con lunghezza Almeno $ (R - 1) (s - 1) + 1 $ contiene una successiva successiva della lunghezza della lunghezza $ r $ < / span> o una riduzione della conseguenza della lunghezza $ s $ .

Si scopre che il rilegato, $ (R-1) (S-1) +1 $ è stretto. Cioè, per qualsiasi numero positivo $ R $ e $ s $ , c'è una sequenza di numeri distinti con lunghezza $ (R-1) (S-1) $ che non contiene la successiva successiva della lunghezza $ r $ e non diminuendo la successiva successiva della lunghezza $ s $ .

Ecco un tale esempio.

$$ \ 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, & \ CDOT, & (R-2) (S-1) +2, & (R- 2) (S-1) +1 \\ \ end {array} $$

Considera i numeri sopra, leggendo da sinistra a destra e poi dall'alto verso il basso. In altre parole, la sequenza è $ S-1 $ fino a $ 1 $ , seguito da $ 2 (S-1) $ fino a $ (S-1) +1 $ , ecc. E infine seguito da < Span Class="Math-Container"> $ (R-1) (S-1) $ giù a $ (R-2) (S-1) +1 $ , tutto in fase di $ 1 $ .

È facile vedere che non vi è alcuna crescente successiva della lunghezza r e non diminuendo la successiva della quota della lunghezza $ s $ .

Ad esempio, quando $ R= S= 5 $ , abbiamo $$ 4,3,2,1, \ \, 8,76,5, \ \, 12,11,10,9, \ \, 16,15,14,13 $$ che non ha aumentato la conseguenza della lunghezza della lunghezza $ 5 $ né diminuendo la sottospetto di lunghezza $ 5 $ .

---

.

Se lasciamo $ R= S $ , la sezione sopra implica che, per qualsiasi numero positivo $ N $ < / span>, esiste una sequenza intera della lunghezza $ N $ con tutti gli elementi unici in tali che la lunghezza della sua più lunga successiva crescente e quella della sua più lunga successiva successiva è al massimo $ \ lceil \ sqrt n \ rceil $ . E $ \ lceil \ sqrt n \ rceil $ è il limite superiore stretto.

poiché $$ \ lceil \ sqrt n \ rceil \ ge \ lfloor \ frac n2 \ rfloor \ \ text {per tutti} n \ le 7 $$ e $$ \ Lceil \ sqrt n \ rceil \ lt \ lfloor \ frac n2 \ rfloor \ \ text {per tutti} n \ gt 7, $$ La risposta alla domanda dell'OP è, no se $ n \ le 7 $ e sì altrimenti.

Ad esempio, per $ n= 8 $ , abbiamo sequence $ 3,2,1,6,5, 4,9,8,7 $ .

Answer 2

Ecco una costruzione diretta di tale sequenza per qualsiasi multiplo di quattro.È composto da quattro serie di numeri interi consecutivi di uguali dimensioni.

In aumento la prima e la terza manche.In diminuzione la seconda e la quarta manche.Le esecuzioni utilizzano intervalli di numeri tali $R_2 < R_3 < R_1 < R_4$.Ad esempio, con $4n=16$,

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

La sottosequenza crescente più lunga è la lunghezza $n+2$.Ad esempio, nell'esempio sopra dove $4n=16$, la sottosequenza crescente più lunga ha lunghezza $6$ ($1| 5, 6, 7, 8|16$).Nessuna sottosuccessione crescente è più lunga:

• Non è possibile scegliere un elemento da entrambe le serie crescenti, poiché qualsiasi elemento nella prima serie crescente li squalifica tutti dalla seconda serie crescente.
• Non è possibile scegliere più di un elemento da nessuna delle due sequenze decrescenti

Per le sottosuccessioni decrescenti si applica un ragionamento simmetrico.

Da $n+2 << 2n$, questo funziona come controesempio per qualsiasi sequenza multipla di quattro.Puoi facilmente completare con elementi di sequenza aggiuntivi per lunghezze non multiple di quattro.

Mi sono imbattuto in questa costruzione considerando una sequenza che fosse una "collina" (crescente, poi decrescente), che soddisfa perfettamente la tua condizione.Spezzare questi lunghi percorsi potrebbe essere fatto creando due colline (crescente, decrescente, crescente, decrescente), cosa che questa sequenza fa garantendo che la pendenza su/giù di una "collina" non sia continuata dall'altra.

Answer 3

Ci sono anche sequenze brevi che soddisfano la tua richiesta. Considera ad esempio i primi 16 termini della sequenza di corput binary van der $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In generale esiste una sequenza $ T $ di lunghezza $ n \ geq1 $ contenente una più lunga successiva successivalunghezza $ x \ geq 1 $ e una più lunga riduzione della sottospetto della lunghezza $ y \ geq 1 $ Se eSolo se i numeri $ x $ , $ y $ e $ N $ soddisfare le condizioni $ x \ cdot y \ geq n $ e $ x + y \ leqn + 1 $ , vedere qui .Si noti che il riferimento fornisce una prova costruttiva.

Answer 4

Tali sequenze esistono.È sufficiente generare una sequenza casuale abbastanza grande.Se controlli il libro di Dan Romik, la sorprendente matematica delle successive successive più lunghe , teorema 1.1 afferma che

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

dove $ \ ell_n $ è una lunghezza prevista per aumentare la successive successiva in un permutazione casuale di dimensioni $ N $ .Lo stesso per diminuire.Pertanto, per abbastanza $ N $ deve esistere una sequenza con sequenze di lunghezze crescenti e decrescenti nella maggior parte dei $ 5 \ SQRTn $ , altrimenti:

$$ 2 e [\ ell_n]= E [| Dec_n |+ | inc_n |] \ ge 5 \ sqrt n, $$

che contraddice il teorema.