Permutación anti-aritmética larga

Question

Una permutación es una secuencia $(a_1, \ldots, a_n)$ , en la que cada número $1, \ldots, n$ aparece exactamente una vez. Llamamos a una secuencia anti-aritmética si no hay no-trivial aritmética de las subsecuencias en ella; es decir, si no hay $i < j < k$ tal que $(a_i, a_j, a_k)$ es una progresión aritmética.

Un ejemplo de un anti-progresión aritmética de longitud 6 es $$ (3, 5, 4, 6, 1, 2). $$

Intuitively it seems "hard" to me for a long sequence to be anti-arithmetic. For example, suppose that you have built about half the sequence so far; then adding any element $$ near $n/2$ requires that the elements of $1, \ldots, n$ you have used so far mirror (almost) exactly around $$, y hay un montón de maneras para que esto vaya mal.

En particular, no sé cómo crear anti-progresiones aritméticas de longitud arbitraria.

Hay anti-progresiones aritméticas arbitrariamente de alta duración? ¿Cómo puedo construir?

---

Estoy haciendo esta pregunta porque de Kattis problema Antiarithmetic?; buscando en google la palabra "antiarithmetic" me pone solo las referencias a esta recreación de un problema de programación. Yo soy no está buscando una solución para el problema, sólo para algunos más intuición acerca de antiarithmetic secuencias.

---

Edit: algo de programación sugiere fuertemente que tales anti-progresiones aritméticas continúan apareciendo por mayor $n$. El siguiente (unoptimized, pero un poco más rápido que el de la fuerza bruta) de secuencia de comandos de muestra de anti-progresiones aritméticas de longitud de hasta 40 muy rápidamente, y que hay acerca de 74904 tales secuencias de longitud 15.

def extend_aas(length, partial_sequence=[]):
    results = []
    for i in range(length):
        if i in partial_sequence:
            continue
        for j in partial_sequence:
            if 0 <= i + i - j < length and (i + i - j not in partial_sequence):
                break
        else:
            yield partial_sequence + [i]

def get_aases(length, partial=[]):
    for extended in extend_aas(length, partial):
        if len(extended) == length:
            yield extended
        else:
            for result in get_aases(length, extended):
                yield result

for n in range(1, 41):
    print(n, next(get_aases(n)))

for n in range(1, 16):
    print(n, len(list(get_aases(n))))

Sin embargo, esto todavía no me da la intuición de por qué esto podría ser el caso.

Answer 1

Sí, hay anti-progresiones aritméticas (AASs) de cualquier longitud.

Si $(a_1, \ldots, a_n)$ e $(b_1, \ldots, b_n)$ son AASs de longitud $n$, luego pretendemos que $$ (2a_1, \ldots, 2a_n, 2b_1 - 1, \ldots, 2b_n-1) $$ es un AAS de longitud $2n$. De hecho, es evidente que cada entero $1, \ldots, 2n$ aparece exactamente una vez, incluso en la primera mitad y los impares en la segunda mitad. Además, supongamos que hacia una contradicción que contiene no trivial de la progresión aritmética. Si la secuencia es de la forma $(2a_i, 2a_j, x)$ , entonces debemos tener ese $x$ es aún, por lo tanto, $x = 2a_k$. Pero, a continuación, $(a_i, a_j, a_k)$ sería una progresión aritmética en $(a_1, \ldots, a_n)$. Por una razón similar,no podemos tener una progresión aritmética $(2b_i - 1, 2b_j - 1, x)$. Por último, una secuencia $(2a_i, 2b_j - 1, x)$ no puede ser aritmética, porque las $x$ tendría que ser, pero no hay número par se produce después de un extraño.

Ya hay al menos un anti-progresión aritmética, hay arbitrariy largo anti-progresiones aritméticas. De más AAS siempre podemos hacer una corta simplemente tomando sólo la parte inferior de los números de la secuencia, de manera que hay AASs de cualquier longitud.

Nota además de que puede invertir el orden de los pares y los impares partes, y el mismo argumento pasa a través de. Esto significa que si hay $k$ AASs de longitud $n$, entonces esta construcción da $2k^2$ diferentes AASs de longitud $2k$. Desde allí es trivialmente 1 AAS de longitud 1, esto nos dice que hay al menos $2^{2^n - 1}$ AASs de longitud $2^n$. Dado que el número de AASs de longitud $n$ está delimitado por la mayor potencia de 2 por debajo de $k$ y el de menor potencia de 2 mayor que $k$, este en particular se muestra que hay exponencialmente en muchos de la longitud de $k$ AASs.