Arco sumas de dinero para un círculo de $k$ enteros positivos cuya suma es $n$

Question

Este problema me hizo pensar en el siguiente escenario más general:

Supongamos que usted ha $k$ enteros positivos con la suma total $n$, y organizarlos en un círculo.

Dado un arreglo, usted puede buscar en diferentes sumas de forma consecutiva colocan enteros positivos a lo largo de "los arcos" de este círculo. Además, usted podría pedir que los números deben siempre aparecer en un arco para un determinado$k$$n$, es decir, independientemente de que $k$ enteros positivos sumar a $n$ son elegidos y cómo se organizan alrededor del círculo.

Deje $A_{k, n}$ ser el conjunto de números que tienen que aparecer necesariamente en algunos de arco para cada arreglo circular de $k$ enteros positivos cuya suma es $n$. (Por supuesto, este conjunto es no vacío iff $k \leq n$.)

Trivialmente, $n \in A_{k, n}$. (Prueba: tome el arco que corresponde a todo el círculo.)

Los enlaces problema anterior demuestra que $200 \in A_{101, 300}$ usando el principio del palomar.

Otro hecho obvio: dado un entero positivo $m < n$$m \in A_{k, n}$,$n-m \in A_{k,n}$.

Esté vinculada al problema anterior, esto significa que $300 - 200 = 100 \in A_{101, 300}$.

Por supuesto, este último hecho es demostrado por tomar complementar los arcos.

Preguntas:

$1.$ Tiene este escenario ya se ha estudiado bajo algún otro nombre?

$2.$ Hay una manera fácil de determinar los elementos de $A_{k,n}$ en general?

$3.$ Si las respuestas a $1$ $2$ son tanto de no, ¿qué se puede mostrar para algunos casos especiales?

Como final, un ejemplo muy simple: $A_{n,n} = \{1, \ldots, n\}$.

(Idealmente, si usted va a responder a $3$, sería con un menos trivial de la proposición!)

Answer 1

He aquí un caso especial: Si $k \leq n < 2k$$A_{k,n} = \{1, 2, \ldots, n\}$.

---

El OP ya ha demostrado que $A_{n,n} = \{1, 2, \ldots, n\}$, así que supongamos $k < n < 2k$.

Inicio en el mayor entero positivo en el círculo. Desde $n > k$, este debe ser de al menos $2$. Vamos $s_j$, $1 \leq j \leq kn$, la suma de los $j$ valores consecutivos movimiento de las agujas del reloj desde este punto de partida. Tenga en cuenta que $s_{kn}$ suma de los números que se envuelven alrededor de la circunferencia $n$ veces.

Deje $S = \{s_j \, |\, 1 \leq j \leq kn\}$. Los valores de $S$ son todos distintos. Por otra parte, el más pequeño, al menos, $2$ y el más grande es exactamente $n^2$.

Para cualquier entero positivo $i$, vamos a $T = \{s_j + i \, | \, 1 \leq j \leq kn\}$. Los valores de $T$ son todos distintos. Por otra parte, el más pequeño, al menos, $2+i$ y el más grande es exactamente $n^2+i$.

Juntos, $S$ $T$ contienen $2kn$ elementos, todo lo cual debe estar entre los $n^2+i-1$ valores. El principio del palomar dice que si $2kn > n^2 + i - 1$, al menos un elemento de a $S$ y un elemento de $T$ deben tener el mismo valor. Reorganizar, esta desigualdad es equivalente a $i < (2k-n)n + 1$. Desde $2k - n \geq 1$, la desigualdad se cumple para cualquier $i \leq n$.

Por lo tanto, si $1 \leq i \leq n$, existen índices de $j$ ( $S$ ) y $m$ ( $T$ ) tal que $s_j = s_m + i$. Pero $s_j - s_m = i$ significa que la secuencia de números enteros a partir de la posición $m+1$ y finalizando en la posición $j$ sumas de dinero a $i$. Por otra parte, ya que una vez alrededor del círculo de los rendimientos de una suma de $n$, e $i \leq n$, esta secuencia no ir todo el camino alrededor del círculo. Por lo tanto si $1 \leq i \leq n$, existe un arco suma igual a $i$.

Por lo tanto, $A_{k,n} = \{1, 2, \ldots, n\}$$k \leq n < 2k$.

Answer 2

Seguimiento, un poco demasiado largo para un comentario: hice algunos pequeños experimentos, y aparece (empíricamente) que $A_{k,2k}$ consiste de exactamente los números enteros tener al menos el $2$-ádico de valoración de $2k$ (por ejemplo,$A_{6,12} = \{4,8,12\}$). El patrón se mantiene hasta el $k\le 17$, después de que mi programa se toma más de un par de minutos para que se ejecute.

Parece que las cosas no ponerse interesante cuando se $n - 2k$ es pequeña y no negativo. Parece que $A_{k,n} = \{n\}$ la mayoría del tiempo, especialmente cuando se $n$ es mucho más grande de lo $k$ (una forma precisa de esta declaración, probablemente, no es difícil de probar, tal vez por $n \ge 3k$).

He aquí otro patrón interesante:

• $A_{4,n} = \{n\}$ todos los $8 \le n \le 30$, con la excepción de $A_{4,9} = \{3,6,9\}$.
• $A_{5,n} = \{n\}$ todos los $11 \le n \le 30$, con la excepción de $A_{5,12} = \{4,8,12\}$.
• $A_{6,n} = \{n\}$ todos los $13 \le n \le 30$, con la excepción de $A_{6,15} = \{5,10,15\}$.
• $A_{7,n} = \{n\}$ todos los $16 \le n \le 30$, con la excepción de $A_{7,18} = \{6,12,18\}$.

Uno naturalmente, podría estar tentado a pensar que, o bien $A_{k,n} = \{1,\ldots,n\}$ o $A_{k,n} = \{n\}$, a menos que $n = 2k$ o $n = 3(k-1)$. Pero la verdad no es muy conveniente, porque también tenemos

• $A_{7,15} = \{3,5,6,9,10,12,15\}$.

Este parece ser el primer ejemplo de que no se trata de una progresión aritmética mod $n$ (sin embargo, tenga en cuenta que es precisamente el conjunto de no-unidades de mod $15$).

Answer 3

Problema equivalente: $k$ distintos elementos son seleccionados a partir de los enteros $\mod n$; que $\mod n$ diferencias entre pares se ven obligados? La equivalencia es de asignar a un conjunto de $k$ enteros positivos escrito alrededor de un círculo, su conjunto de las agujas del reloj arco sumas $\mod n$, incluyendo a $0$ para el vacío de la suma.

Pares en una diferencia de $d$ puede ser representada como un grafo no dirigido por unirse a cualquier par por un borde. La estructura de la gráfica depende sólo de $g = \gcd(d,n)$, es una unión de $g$ ciclos disjuntos toda la longitud de la $\frac{n}{g}$. Un ciclo de longitud $L$ puede acomodar hasta a $\lfloor \frac{L}{2} \rfloor$ vértices no conectados por una arista.

Por lo tanto $d$, y la distancia con el mismo valor de $g$, es obligado si y sólo si $k > g \lfloor \frac{n}{2g} \rfloor$. La condición para $k$ a fuerza de $g$ luego $k > n/2$ al $2g|n$, e $k > \frac{n-g}{2}$ al $n$ $g$ son divisibles por el mismo poder de $2$. Esta es la condición necesaria y suficiente para los valores de $d$ $(d,n)=g$ a de estar en el conjunto de obligado arco sumas $A_{k,n}$.