Deje $p$ ser un entero positivo. Para cada entero no negativo $k$, escribir $[k]$ para el conjunto de $\{0,1,2,\ldots,k\}$. También, se definen $[-1]:=\emptyset$. Decimos que un número entero $k\geq -1$ $p$-splittable si hay una partición de $[k]$ a $p$ subconjuntos $A_1$, $A_2$, $\ldots$, $A_p$ tal que $\sum_{x\in A_1}\,x=\sum_{x\in A_2}\,x=\ldots=\sum_{x\in A_p}\,x$ (es decir, de estos conjuntos tienen la misma suma). Dicha partición $\left\{A_1,A_2,\ldots,A_p\right\}$ se llama un $p$-división de $[k]$.
¿Cuáles son todas las $p$-splittable enteros para un determinado $p$? Cuántas $p$-escisiones de $[k]$ hay para cada una de estas disponible $k$'s? Si el número exacto de $p$-escisiones de $[k]$ no es fácilmente computable, entonces ¿cuál es el asintótica respuesta?
Claramente, $k=-1$ $k=0$ $p$- splittable. También podemos ignorar el caso trivial $p=1$. Sabemos que, si $p=2$, entonces todos los $p$-splittable números de los formularios $4t-1$ $4t$ donde $t$ es un entero no negativo. Si $p$ es un extraño primo, entonces todos los $p$-splittable números son enteros de las formas $tp-1$ $tp$ donde $t\in\{0,2,3,4,\ldots\}$.
Para $p=2$, se puede demostrar que el número de $2$-escisiones de una $2$-splittable entero $k$ está dado por el coeficiente de $x^{\frac{k(k+1)}{4}}$ en la expansión de $\prod_{r=1}^k\,\left(1+x^r\right)$. Por ejemplo, si $k=3$, hay dos $2$-escisiones de $[3]$, es decir, $\big\{\{0,1,2\},\{3\}\big\}$$\big\{\{1,2\},\{0,3\}\big\}$, mientras que $$\prod_{r=1}^3\,\left(1+x^r\right)=1+x+x^2+2x^3+x^4+x^5+x^6$$ whose coefficient of $x^{\frac{k(k+1)}{4}}=x^3$ is also $2$. Similarly, there are $2$, $8$, and $14$ $2$-spittings of $[k]$ for $k=4$, $k=7$, and $k=8$, respectively. I do not know if there is any closed form for this coefficient for an arbitrary $2$-splittable $k$.
Suponemos los siguientes:
(1) Si $p$ es extraño, entonces, para cualquier $j\in\{-1,0,1,2,\ldots,p-2\}$ tal que $p\mid j(j+1)$, todos los enteros de la forma $tp+j$ donde $t\in\{2,3,4,\ldots\}$ $p$- splittable, y nada más (con la excepción de$-1$$0$) $p$- splittable.
(2) Si $p$ es par, entonces, para cualquier $j\in\{-1,0,1,2,\ldots,2p-2\}$ tal que $2p\mid j(j+1)$, todos los enteros de la forma $2tp+j$ donde $t$ es un entero positivo, es $p$-splittable, y nada más (con la excepción de$-1$$0$) $p$- splittable.
Esta conjetura es verdadera, por lo menos, si $p$ es una potencia principal (donde $j=-1$ $j=0$ son las únicas opciones posibles de $j$). Si usted puede demostrar que (1) tiene por $t=2$$t=3$, y que (2) tiene por $t=1$, entonces usted está listo. Vale la pena señalar que, si $k$ $p$- splittable, a continuación, $k+2p$ $p$- splittable.
Inspiración: Particionamiento $\{1,\cdots,k\}$ a $p$ subconjuntos con sumas iguales
P. S. tengo que incluir $k=0$ $k=-1$ en aras de la exhaustividad. No hay nada sutil sobre estos números.
Respuesta
¿Demasiados anuncios?
probablemente la última edición, el formato para mayor claridad:
Podemos decir $n$ $p$- splittable si hay una partición $A_1,...,A_p$ $\{1,...,n\}$ $\sum A_i := \sum_{a \in A_i} a = \sum A_j$ todos los $i,j\leq p$
Llamamos a $n$ uniformemente $p$-splittable si hay una partición con $|A_i|=|A_j|$ todos los $i,j \leq p$
Llamamos una partición de un $p$-división de $n$
Vamos $s_p(n)$ $(\bar{s}_p(n))$ indicar el número de (uniforme) $p$-splits de a $n$
Algunas verdades:
$\bar{s}_p \leq s_p$
Si $n$ $p$- splittable, a continuación, $p| \frac{(n+1)n}{2}$
Si tenemos igualdad de $s_p(n)=1$ (no es exactamente una $p$-división de $n$)
$2p$ $2p-1$ $p$- splittable, $2p$ uniformemente.
Si $n$ $p$- splittabe y $p'|p$ $n$ $p'$- splittable y obtenemos una cota inferior de a $s_{p'}(n)\geq \frac {p!}{(\frac{p}{p'}!)^{p'}}$ (el número de maneras de hacer un $p$ -, dividido en $p'$-split mediante la fusión de los grupos de $\frac{p}{p'}$ juntos)
(puede ser posible obtener un obligado en términos de $s_p(n)$ si uno puede argumentar lejos doble conteo)
Si $n$ es uniformemente $p$-splittable, a continuación, $mn$ es uniformemente $p$-splittable para todos los m$\in \mathbb{N}$
Si $n$ $p$- splittable y $k$ es uniformemente $p$-splittable, a continuación, $m+k$ $p$- splittable
Si $m,n$ son uniformemente $p$-splittable, a continuación, $m+n$ es uniformemente $p$-splittable
El $p$-splittable números son entonces una unión finita de (afín) copias de la uniformidad de la $p$-splittables y son generados por un número finito de primitivos $p$-splittable números, un trivial límite superior en el número de primitivas es el más pequeño distinto de cero uniformably $p$-splittable número $2p$. Una mejor obligado se logra por $\# \{j \in \{-1,0,...,2p-2\} \; with \; 2p|j(j+1)\}$
Se cree que esta enlazado es exacta y la primitiva $p$-splittables son de la forma $2p+j$ $j$ en este conjunto. (Este es numéricamente probado para $p\leq 184$)
Si $n$ es uniformemente $p$-splittable, a continuación, $n$ debe ser un múltiplo de $p$. Voy a dar un total de categorización:
Deje $p \in \mathbb{N}$, a continuación, la uniformidad de la $p$-splittables se $p \mathbb{N} \backslash p$ si $p$ es impar y $2p \mathbb{N}$ si p es incluso (o $\mathbb{N}$$p=1$)
prueba: es evidente que $2p$ es uniformemente $p$-splittable y $p$ no lo es. Esto es suficiente para mostrar que por extraños $p$ $3p$ es uniformemente $p$-splittable y para $p$ no extraño múltiples.
Deje $p$ ser incluso y $k$ impar. A continuación, $\frac{kp(kp+1)}{2}$ no es múltiplo de $p$ (es un extraño múltiples de $\frac p 2$)
Deje $p$ raro:
deje $[i]$ denotar $ i \; mod \; p$
A continuación, un uniforme de $p$-división de $3p$ está dado por $A_i = \{ 1+[i], (p+1)+[\frac{p-1}{2}+i], 2p+1+[p-1-2i]\}$ $i=0,...,p-1$ Obviamente, cada una de las $A_i$ tiene 3 elementos y cada número $\leq 3p$ está representado. Debemos mostrarles a $[i]+[\frac{p-1}{2}+i]+[p-1-2i]$ es independiente de $i$.
Esto es cierto porque para $i \leq (p-1)/2$ todos los argumentos en $(0,...,p-1)$ $(p+1)/2 \leq i \leq p-1$ hemos $[\frac{p-1}{2}+i]=\frac{p-1}{2}+i-p$, $[p-1-2i]=p-1-2i+p$ en cada caso la suma es igual a $\frac{3(p-1)}{2}\square$
$\bar{s}_p(p^2) \geq (p-1)!$ (por la construcción de $(p-1)!$ uniformes $p²$-splits)
Cosas para buscar en:
-
El original de la conjetura. Esto puede ser logrado por
simplemente construyendo $p$-se divide por $2p+j$ de la $j$ (nota: $j=-1,0$ son triviales) o
La construcción de un algoritmo. Los problemas aquí yacen en probar el algoritmo termina, esto nos lleva a estudiar de encontrar la manera de dividir un conjunto en montones de (diferentes) dado tamaños (divide sería el caso especial donde todas las pilas tienen el mismo tamaño)
Tenga en cuenta que el requisito de la $j$ es equivalente a $j \equiv -1$ o $ 0 \mod p_i$ para todo el primer potencias $p_i|p$ (nota: esto demuestra la conjetura para el prime $p$ después de dar un partido para $3p-1$ ($p$ impar) como aquí)
Dicho estudio de "ajuste" de un conjunto en una tupla de enteros $(d_1,...,d_n)$ (es decir, encontrar una partición con $\sum A_i = d_i$) Aquí los conjuntos de la forma $\{1,...,n\}$ son de especial importancia para la demostración de las cosas acerca de splittability
Estudio de splittability para conjuntos de $A\subset \mathbb{N} \neq \{1,...,n\}$
Estudio de $s_p$ y/o $\bar{s}_p$, no me fijé en el número de divisiones, excepto cuando un obligado cayó de una prueba.
