Encuentra el conjunto más pequeño de números naturales cuyas sumas pairwise incluyen 0..n

Question

Dado un entero positivo $n$, ¿cómo encontrar el conjunto más pequeño de números enteros no negativos $S$ tal que para cada entero $m$ donde $0\leq m<n$, existen dos (no necesariamente distintos) los miembros de $S$, decir $x$ $y$ tal que $x+y=m$.

Por ejemplo, considere el caso de $n=50$. Supongamos que la longitud de $S$$L$. Para el límite inferior, si los elementos de a $S$ tienen pares de distintas sumas de dinero, entonces no se $\dbinom{L+1}{2}$ sumas (el plus 1 es porque los números pueden ser añadidos a sí mismos). Por lo tanto, $$\binom{L+1}{2}\geq50\implies L\geq10$$.

Que puede alcanzar $L=12$ con el conjunto {0, 1, 2, 3, 7, 10, 15, 18, 22, 23, 24, 25} (hecho con muy ineficiente programa que busca al azar entre todos los conjuntos). Para $L=10$, me siento como debería ser imposible; sólo tenemos que demostrar que más de 5 números que se pueden expresar como una suma de más de 1 vía, que debe ser capaz de realizarse a través de algunos casos. Sin embargo, es $L=11$ posible? Yo así lo creo.

Del mismo modo, para $n=100$, he a $L=17$ de mi programa: {0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50}. Pero el límite inferior sólo da $L\geq 14$, así que al menos $L=15$ o $L=16$ debería ser posible.

En general, ¿cómo hacerlo de manera eficiente para cualquier $n$?

Answer 1

Aquí están los resultados de $n$ $80$ donde $\min$ es el límite inferior de la que se derivan del coeficiente binomial, $\max$ es el límite superior que Fabio Lucchini derivados en su respuesta, $L=|S|$ es el tamaño de un mínimo de generación del sistema. Real subconjuntos $S$ sólo se muestran para la última entrada para cualquier $L$, ya que este subconjunto también funciona para todos los $n$.

\begin{array}{c|c|c|c|l} n&\min&\max&L&S\\\hline 2&2&2&2&\{0,1\}\\ 3&3&3&3\\ 4&3&3&3&\{0,1,2\}\\ 5&3&4&4\\ 6&4&4&4\\ 7&4&4&4\\ 8&4&4&4&\{0,1,3,4\}\\ 9&4&5&5\\ 10&5&5&5\\ 11&5&5&5\\ 12&5&5&5&\{0,1,3,5,6\}\\ 13&5&6&6\\ 14&5&6&6\\ 15&6&6&6\\ 16&6&6&6&\{0,1,3,5,7,8\}\\ 17&6&7&7\\ 18&6&7&7\\ 19&6&7&7\\ 20&6&7&7&\{0,1,2,5,8,9,10\}\\ 21&7&8&8\\ 22&7&8&8\\ 23&7&8&8\\ 24&7&8&8\\ 25&7&8&8\\ 26&7&8&8&\{0,1,2,5,8,11,12,13\}\\ 27&7&9&9\\ 28&8&9&9\\ 29&8&9&9\\ 30&8&9&9\\ 31&8&9&9\\ 32&8&9&9&\{0,1,2,5,8,11,14,15,16\}\\ 33&8&10&10\\ 34&8&10&10\\ 35&8&10&10\\ 36&9&10&10\\ 37&9&10&10\\ 38&9&10&10\\ 39&9&11&10\\ 40&9&11&10&\{0,1,3,4,9,11,16,17,19,20\}\\ 41&9&11&11\\ 42&9&11&11\\ 43&9&11&11\\ 44&9&11&11\\ 45&10&12&11\\ 46&10&12&11&\{0,1,2,3,7,11,15,19,21,22,24\}\\ 47&10&12&12\\ 48&10&12&12\\ 49&10&12&12\\ 50&10&12&12\\ 51&10&12&12\\ 52&10&12&12\\ 53&10&13&12\\ 54&10&13&12&\{0,1,2,3,7,11,15,19,23,25,26,28\}\\ 55&11&13&13\\ 56&11&13&13\\ 57&11&13&13\\ 58&11&13&13\\ 59&11&13&13\\ 60&11&13&13\\ 61&11&14&13\\ 62&11&14&13\\ 63&11&14&13\\ 64&11&14&13&\{0,1,3,4,9,11,16,21,23,28,29,31,32\}\\ 65&11&14&14&\\ 66&12&14&14&\\ 67&12&14&14&\\ 68&12&14&14&\\ 69&12&15&14&\\ 70&12&15&14&\\ 71&12&15&14&\\ 72&12&15&14&\{0,1,3,4,9,11,16,20,25,27,32,33,35,36\}\\ 73&12&15&15&\\ 74&12&15&15&\\ 75&12&15&15&\\ 76&12&15&15&\\ 77&12&16&15&\\ 78&13&16&15&\\ 79&13&16&15&\\ 80&13&16&15&\{0,1,3,4,5,8,14,20,26,32,35,36,37,39,40\}\\ \end{array}

Este es el código que he utilizado para generar estos resultados. Se recorre $n$, haciendo uso de la solución para $n-1$ en cada paso. Primero comprueba si el conjunto de $n-1$ también funciona para $n$. Si no, intenta encontrar un nuevo conjunto también contiene $L$ números, en primer lugar, utilizando sólo los elementos de a $\lfloor\frac n2\rfloor + 2$. Sólo si esto no funciona, trata todas las combinaciones con $L$ elementos de todo el camino hasta el $n$. Si no que además no funciona, aumenta el $L$. De esta manera, se pasa casi todo su tiempo sólo en los valores de $n$ donde $L$ necesita ser incrementado; para todos los demás valores de $n$ se encuentra rápidamente una solución sin tener que buscar en todo el espacio.

Al menos $n$ para que Fabio Lucchini del límite superior no es firme, es $n=39$, por lo que el $10$-element set $\{0,1,3,4,9,11,16,17,19,20\}$ es suficiente, mientras que el límite superior es $11$.

La secuencia de $L(n)$ es OEIS A066063, y la única información de que la entrada es el límite inferior de la que ya se encuentra. Generalmente, OEIS es bastante bueno en la recopilación de información acerca de las secuencias, por lo que es probable que no se sabía nada más.

Answer 2

Deje $n+4=s^2+r$$r,s\in\Bbb N$$0\leq r\leq 2s$. A continuación, un límite superior está dado por $$L\leq \begin{cases} \lceil{\frac rs}\rceil+2s-3&2\mid s\\ \lceil{\frac{r+1}{s+1}}\rceil+2s-3&2\nmid s \end{casos}$$ que da $L\leq 12$$n=50$$L\leq 18$$n=100$. En general, para un gran $n$ esto da $L=O(\sqrt n)$.

Un conjunto $S$ correspondiente a este límite superior está dado por \begin{align} S &=\{i\in\Bbb N:0\leq i<q-1\}\\ &\cup\{(q-1)+jq:0\leq j\leq k-1\}\\ &\cup\{i\in\Bbb N:(q-1)+(k-1)q<i\leq 2(q-1)+(k-1)q\} \end{align} para valores adecuados de a$q$$k$. A continuación, $|S|=k+2(q-1)$ y, a continuación, la suma de cada par de sus elementos de obtener toda la número natural menor o igual a $2(2(q-1)+(k-1)q)=2\max S$. En consecuencia, podemos elegir $$k=\left\lceil\frac{n+4}{2q}\right\rceil-1$$ La función $$\frac{n+4}{2q}-1+2(q-1)$$ alcanza un mínimo en $q=\frac{\sqrt{n+4}}2$.

Si $n+4=s^2+r$$s=2t+b$$r\leq 2s$$0\leq b\leq 1$, luego $$t\leq\frac{\sqrt{n+4}}2<t+1$$

Para $q=t$ tenemos \begin{align} |S_t| &=\left\lceil\frac{n+4}{2t}\right\rceil+2t-3\\ &=\left\lceil\frac{s^2+r}{s-b}\right\rceil+s-b-3\\ &=\left\lceil\frac{r+b}{s-b}\right\rceil+2s-3 \end{align} mientras que para $q=t+1$ \begin{align} |S_{t+1}| &=\left\lceil\frac{n+4}{2t+2}\right\rceil+2t+2-3\\ &=\left\lceil\frac{s^2+r}{s-b+2}\right\rceil+s-b-3\\ &=\left\lceil\frac{r+4-3b}{s+2-b}\right\rceil+2s-3 \end{align} Desde $|S_t|\leq|S_{t+1}|$ si y sólo si $b(2s+1)\leq 2s-r$, la fórmula en la parte superior está probado.

Answer 3

Aquí está el trabajo de casos para demostrar que para $n=50$, $L$ de hecho, tiene que ser mayor que $10$, suponiendo joriki sugerencia:

todas las soluciones contienen un mínimo de $0$,$1$,$\lceil\frac n2\rceil-1$ y $\lceil\frac n2\rceil$

Desde ${11 \choose 2} =55$, sólo tenemos que demostrar que podemos obtener al menos $6$ 'partidos' para cualquier conjunto de números.

OK, así que por joriki sugerencia, necesitamos $0,1,24,25$. Por lo tanto, tenemos un partido: $24+1=25+0$

Ahora, para los casos de:

I) Si añadimos $2$, tenemos dos más: $1+1=2+0$ $24+2=25+1$

Para hacer 47, necesitamos agregar a $23$ o $22$:

I. A) Agregar $23$. Luego podemos agregar $23+1=24+0$, $24+2=25+1$, y $23+25=24+24$, por lo que tenemos a nuestro $6$ partidos

I. B) Agregar $22$. Podemos agregar $22+2=24+0$ (4 partidos de ahora)

Para hacer $5$, tenemos que añadir $3$, $4$, o $5$:

I. B. i) Agregar $3$: $2+1=3+0$ y $24+3=25+2$ nuestra $6$

I. B. ii) Agregar $4$: $2+2=4+0$ y $22+4=24+2$. También se $6$

I. B. iii) Agregar $5$: $22+5=25+2$. OK, necesito uno más ... bueno, a crear $45$ necesitamos para agregar cualquiera de las $20$ (lo que le da $20+2=22+0$) o $21$ ($21+1=22+0$), así que hacer aquí así

OK, así que la adición de $2$ definitivamente conduce a $6$ partidos. Así que, no vamos a agregar $2$ ... pero ahora necesitamos $3$ crear $3$:

II) Agregar $3$

De nuevo, para crear $47$, tenemos que agregar cualquiera de las $23$ o $22$:

II.A) Agregar $23$. Podemos agregar $24+24=23+25$, $23+1=24+0$, y $23+3=25+1$, para un total de 4 partidos ahora.

Para crear $5$, tenemos que agregar cualquiera de las $4$ o $5$:

II.Una.i) Agregar $4$. Luego tenemos a $3+1=4+0$$23+4=25+3$. Hecho

II.Una.ii) Agregar $5$. Tenemos $5+1=3+3$ $23+5=25+3$ Hecho

II.B) Agregar $22$. Podemos agregar $22+3=25+0$ $22+3=24+1$ (3 partidos ahora)

Para hacer $5$, necesitamos tpo agregar $4$ o $5$:

II.B.i) Agregar $4$. Esto le da $1+3=4+0$, $24+4=25+3$, y $22+4=25+1$ Hecho

II.B.ii) Agregar $5$. Esto le da $1+5=3+3$, $22+5=24+3$, tan sólo necesitamos una más. Pero para crear $45$ tenemos que añadir $21$ ($21+1=22+0$), o $20$ ($20+3=22+1$), así que hacer aquí así

.. y concluye que todos los casos. Así que, sí, como se sospecha, por $n=25$ tenemos $L>10$

Y, francamente, viendo cómo rápidamente a estos posibles coincidencias aumento, mi conjetura es que para $n=50$, $L=12$