Este es un seguimiento de esta pregunta sobre math.stackexchange.
Digamos que un conjunto no vacío S ⊆ ℤ es autosuficiente si para cada a ∈ S, existen elementos distintos b, c ∈ S de modo que a = b + c. Para enteros positivos n , ejemplos simples incluyen el ideal S = n ℤ, o (para n > 3) el intervalo entero [- n , n ].
Diremos que S es fuertemente autosuficiente si S es disjunto de −S: es decir, si a ∈ S, entonces - a ∉ S. Ninguno de los ejemplos anteriores es fuertemente autosuficiente, porque de hecho están cerrados bajo negación Existen conjuntos finitos que son fuertemente autosuficientes: por ejemplo, los conjuntos {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} y {−10, −8, −6, −2, 1, 3, 4, 5}.
Pregunta 1. Para un entero positivo N > 0, ¿existe un algoritmo poly ( N ) -time [o polylog ( N ) -time] para (i) producir un conjunto fuertemente autosuficiente cuyo valor absoluto máximo es N o (ii ) determinan que no existe tal conjunto? [ Editar : como se señaló en la respuesta más antigua + mi comentario al respecto, siempre existe un conjunto para N ≥ 10.]
Pregunta 2. Para N > 0, ¿puede construir el conjunto fuertemente autosuficiente con el valor absoluto máximo N , y que tiene la menor cantidad de elementos posibles?
fuente
Respuestas:
Supongo que un algoritmo de tiempo lineal debería ser posible para la Pregunta # 1) (y si está dispuesto a tratar con una representación diferente, un algoritmo de tiempo O (1))
Dado cualquier N> = 23, construimos un conjunto fuertemente autosuficiente que contiene 1 y N.
Podemos hacerlo fácilmente si construimos lo mismo para N-1 y luego agregamos N al conjunto resultante.
Para el caso base de 23, podemos comenzar con su conjunto de ejemplos.
Para reducir el tamaño, deberíamos poder utilizar un enfoque similar:
Construir conjuntos que contienen
1, N and N-1.Utilizamos estos conjuntos restringidos y hacemos esta construcción de forma recursiva para reducir el tamaño a O (logN) de la siguiente manera:
Si N es par, para construir un conjunto que contenga 1, N y N-1, construya recursivamente un conjunto que contenga 1, N / 2 y N / 2-1 (es decir, conjunto correspondiente a N / 2) y agregue N y N-1 al conjunto resultante. Como N-1 = N / 2 + N / 2-1 y N = 1 + N-1, este es un conjunto válido.
Si N es impar, construya un conjunto para N-1 y N para el conjunto resultante.
Para los casos base, podemos comenzar con {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} para N = 24. Para 24 <N <= 47, podemos usar el algoritmo de tiempo lineal anterior y construir sobre el conjunto para N = 24. Para N> = 48 pasamos a reducir a la mitad.
De hecho, para el compuesto N, podemos reducir el tamaño al tamaño requerido para uno de los primos pequeños que divide N: Encuentre un conjunto para el primo pequeño, y simplemente multiplique todos los números por un factor adecuado.
Puede ser interesante probar algunos límites inferiores en el caso de que N sea primo.
fuente
Para N ≥ 10, se puede construir un conjunto de tamaño fuertemente autoportante como máximo once, de la siguiente manera:
El ejemplo más corto presentado en la pregunta original corresponde al caso N = 10. Esto está cerca de ser óptimo, ya que cualquier conjunto fuertemente autosuficiente debe tener cardinalidad de al menos ocho .
Por lo tanto, el problema se puede resolver en el tiempo O (log (N)) [tomado en operaciones aritméticas mundanas en N], produciendo un conjunto de cardinalidad entre ocho y once.
La construcción de esta respuesta se presentó por primera vez para la pregunta math.stackoverflow , que también da la intuición para la construcción. ¿Podemos obtener construcciones más pequeñas aún, por ejemplo , igualando el límite inferior de ocho por cada N> 9? ¿Qué pasa con los casos de N ∈ {8,9}?
fuente