Colocación de los enteros $\{1,2,\ldots,n\}$ en un círculo ( para $n>1$ ) en algún orden especial

Question

Para qué número entero $n>1$ podemos colocar los enteros $\{1,2,\ldots,n\}$ en un círculo (digamos el límite de $S^1$ ) en un orden tal que para cada $s \in \{1,2,\ldots,\dfrac {n(n+1)}{2}\}$ existe un subconjunto conexo del círculo en el que la suma de los enteros colocados es exactamente $s$ ?

Answer 1

Creo que tengo una respuesta : El arreglo es posible para cualquier $n\ge 1$ .

Prueba :

$\underline {case 1}$ , $n$ es incluso :

$n$ es par, así que empareja los números $1,2,...,n$ en $n/2$ pares con los dos números de cada par que suman $n+1$ es decir, el emparejamiento es como $\{1,n\} ; \{2,n-1\} ; ...;\{\dfrac n2 , \dfrac n2+1\}$ . Afirmamos que cualquier disposición circular de los números $1,2,...,n$ que mantiene los números de cada par adyacentes entre sí da todos los valores posibles de la suma de $1 $ a $\dfrac {n(n+1)}2$ . Para ver esto, considere cualquier $s$ como $1\le s \le \dfrac {n(n+1)}2$ por el algoritmo de la división, hay enteros $q,r$ tal que $s=q(n+1)+r$ , donde $0\le r\le n$ y $0 \le q \le n/2$ . Si $r=0$ entonces elegimos cualquier $q$ pares consecutivos , como los números de cada par son adyacentes , esto da un subconjunto conectado con suma ( ya que cada par tiene suma $n+1$ ) $q(n+1)=q(n+1)+r(=0)=s$ ; si $r>0$ ( y para que $q < n/2)$ elegimos el subconjunto conectado que comienza con $r$ y luego $q$ pares consecutivos en el sentido de las agujas del reloj o en sentido contrario, según el caso, obteniendo una suma igual a $r+q(n+1)=s$

[Nota: En $s=(n+1)q+r$ la desigualdad $0\le r \le n$ proviene del algoritmo de división, pero los límites $0\le q \le n/2$ no proviene directamente del algoritmo de división; se debe a lo siguiente : $q(n+1)=s-r\le s \le \dfrac {n(n+1)}2$ así que $q \le n/2$ y $q(n+1)=s-r\ge1-r\ge1-n=-(n-1)>-(n+1)$ para que $q>-1$ Entonces, como $q$ es un número entero, obtenemos $q \ge 0$ ]

$\underline {case 2}$ , $n$ es impar :

$n$ es impar ,entonces formamos $\dfrac {n+1}2$ pares cada uno con suma $n$ pensando en el singleton $n$ como un par degenerado ; es decir $\{1,n-1\};\{2,n-2\};...;\{\dfrac {n-1}2 , \dfrac {n+1}2\};\{n\}$ son los pares requeridos . Aquí también , cualquier disposición que mantenga los números de cada par adyacentes entre sí da todas las sumas posibles , siendo la justificación la misma que la anterior .

Answer 2

Tenga en cuenta que esto no pretende ser una respuesta a la pregunta del OP, pero el espacio en los campos de comentarios es demasiado limitado, así que pongo mi comentario aquí.

Utilizando la fuerza bruta (informática), conseguí encontrar soluciones para todos $n\leq 26$ y es muy probable que las soluciones para las grandes $n$ se puede encontrar. Sin embargo, todavía no puedo decidirme si creo o no que hay un número entero $N$ para el que el problema no tiene solución:

He modificado mi programa para contar el número de posibles soluciones de todas las permutaciones de los enteros $1,\ldots,n$ en el círculo (sin contar las rotaciones y las reflexiones) y observaron los cocientes de estos números:

2: 1 solution(s) found (out of 1 possible). Ratio is 1.0
3: 1 solution(s) found (out of 1 possible). Ratio is 1.0
4: 2 solution(s) found (out of 3 possible). Ratio is 0.6666666666666666
5: 10 solution(s) found (out of 12 possible). Ratio is 0.8333333333333334
6: 41 solution(s) found (out of 60 possible). Ratio is 0.6833333333333333
7: 126 solution(s) found (out of 360 possible). Ratio is 0.35
8: 537 solution(s) found (out of 2520 possible). Ratio is 0.2130952380952381
9: 3956 solution(s) found (out of 20160 possible). Ratio is 0.19623015873015873
10: 19776 solution(s) found (out of 181440 possible). Ratio is 0.10899470899470899
11: 76340 solution(s) found (out of 1814400 possible). Ratio is 0.04207451499118166
12: 388047 solution(s) found (out of 19958400 possible). Ratio is 0.019442791005291005
13: 2775155 solution(s) found (out of 239500800 possible). Ratio is 0.011587247307733419
14: 15013424 solution(s) found (out of 3113510400 possible). Ratio is 0.004822024683135794

El programa está actualmente ocupado en obtener las cifras de $n=15$ . Estoy seguro de que se puede optimizar un poco, pero no espero que se puedan calcular muchos valores adicionales en un tiempo aceptable, así que probablemente no habrá mucha más información de la que ya está disponible:

Es evidente que mientras el número absoluto de permutaciones admisibles crece con $n$ los ratios respecto al número total de permutaciones disminuyen, pero lo hacen de forma bastante irregular, nótese que los ratios para $n=8$ y $n=9$ están bastante cerca, mientras que en otros lugares hay un descenso de más del 50%, por lo que no es sólo el tamaño lo que importa, sino posiblemente algunas constelaciones de teoría de números.

Así pues, estas limitadas pruebas apoyan ambas posibles proposiciones: El número creciente de soluciones sugiere que hay una solución para cada número entero, y los cocientes decrecientes así como la irregularidad en el número de soluciones podrían ser una señal de que eventualmente podría haber un número $N$ para la que no existe solución.

¿Puede alguien aportar alguna idea adicional sobre el problema? Creo que es toda una joya, pero no tengo ni idea de cómo abordarlo.