Construir un conjunto de números para que las particiones de los 3 elementos tengan diferentes sumas de subconjuntos

Estoy interesado en construir un conjunto de S de 24 enteros positivos de modo que cualquier partición en 8 3 -subconjuntos de elementos, S 1 , … , S 8 tiene la propiedad de que las sumas

∑ s ∈ S i s
son diferentes para cada i = 1 , 2 , … , 8 . Me gustaría hacer esto usando el valor máximo más pequeño posible de cualquier elemento del conjunto, es decir, minimizar
máximo s ∈ S s .
Me imagino que esto se ha estudiado y simplemente no sé el nombre correcto para el problema.

Tenga en cuenta que lo que quiero es diferente del problema de la "suma de subconjuntos" que dice que TODOS los subconjuntos de nuestros 24 enteros tienen sumas diferentes, aunque supongo que esto responde a la pregunta con una construcción subóptima (muy probablemente).

En términos más generales, tengo curiosidad por lo que se sabe sobre tales conjuntos, por norte entero, ¿cómo construimos un conjunto de norte enteros positivos tales que cada partición en k subconjuntos de elementos tiene la propiedad de que el k todos los subconjuntos de elementos tienen una suma diferente.

¿Todos los subconjuntos deben tener 3 elementos? (Indicado en la pregunta, pero no en el problema inicial). La formulación al final es mucho más limpia.
Actualizado, gracias @CalvinLin!
Consulte OEIS , el número más pequeño tal que las sumas de uno, dos o tres de a(1), ..., a(n) son distintas (no se permiten repeticiones), debe ser una estimación aproximada.
¡Gracias! Creo que ese es solo el número de "suma de subconjuntos" donde nos limitamos a subconjuntos de '3 elementos o menos'. En cuyo caso, ¿tiene una idea de qué tan cerca será esta estimación (más aún para general norte , k , pero también para el caso 24,3)?
¿Ha intentado construirlo con avidez, simplemente agregando el número más pequeño que no creará un duplicado? 2 − suma o 3 -¿suma? Por ejemplo, comenzamos con 1 , 2 , 3 y luego no podemos sumar 4 , porque 1 + 4 = 3 + 2 , pero podríamos agregar 5 , etcétera. No digo que esto necesariamente dará el mínimo, pero dará un límite superior.
¡Gracias por la respuesta! Creo que la mala redacción de la forma "general" de mi pregunta ha dado lugar a un ligero malentendido. Estoy pidiendo conjuntos de números que no comparten una suma solo para el 8 sumas obtenidas por partición. Parece que @saulspatz ha respondido a la " 3 -sum" versión de la pregunta que no es exactamente lo que estoy buscando.
¿Quiso decir que podemos tener sumas de 2 duplicadas pero no sumas de 3 duplicadas? Porque creo esto. Mirando a { 1 , 2 , 3 , 5 , 8 , 10 } parece exhibir esta propiedad con { 1 , 10 } y { 3 , 8 } mientras que si mis matemáticas son correctas, ¡esto no tiene partición en dos conjuntos de 3 elementos con una suma duplicada!
Eliminé ese comentario justo antes de que publicaras el tuyo. Realmente, no podemos tener disjuntos 3 -conjuntos con la misma suma, ya que podríamos extenderlos a una partición. Podemos haber duplicado 2 -sumas, si. Por el momento, no veo una forma de modificar mi script para lidiar con esto, pero aquí es muy tarde. Lo pensaré mañana.

Respuestas (1)

Probé el enfoque codicioso que sugerí en un comentario, y produjo un máximo de 13796 , a diferencia del valor 17404 en la tabla OEIS mencionada en los comentarios.

Escribí este pequeño script de Python:

from itertools import combinations

xs = [1,2,3]
twos = {3,4,5}
threes = {6}
nextX = 4
while len(xs) < 24:
    if len(xs) != 23:
        newTwos = {nextX + x for x in xs}
        if newTwos & twos:
            nextX += 1
            continue
    newThrees = {nextX + t for t in twos}
    if newThrees & threes:
        nextX += 1
        continue
    twos |= newTwos
    threes |= newThrees
    xs.append(nextX)
    nextX += 1
print(xs)

# audit
test3 = {sum(t) for t in combinations(xs,3)}
if len(test3)== 24*23*22//6:
    print('Passed audit')
else:
    print('Failed audit')

empezamos con { 1 , 2 , 3 } e intente agregar repetidamente el entero más pequeño aún no probado al conjunto. Hacemos un seguimiento de todos los 2 -sumas y 3 -sumas Cuando probamos un nuevo elemento, lo aceptamos si su adición no crearía un duplicado. 2 -suma o 3 -suma. El 2 -La prueba de suma es necesaria porque si hubiera un duplicado 2 -sum, la adición de un elemento adicional crearía necesariamente un duplicado 3 -suma. Esta prueba es innecesaria cuando agregamos el 24 elementos al conjunto.

El script produjo la salida.

[1, 2, 3, 5, 8, 14, 25, 45, 82, 140, 235, 388, 559, 839, 1286, 1582, 2221, 3144, 4071, 5795, 6872, 9204, 11524, 13796]
Passed audit

Por supuesto, no hay garantía de que el algoritmo codicioso produzca la respuesta óptima. Se garantiza que el algoritmo codicioso funcionará solo cuando tengamos un matroide subyacente . Podríamos definir un conjunto como independiente si todos sus 3 -los subconjuntos tienen sumas distintas. Un subconjunto de un conjunto independiente es independiente, pero no tenemos la propiedad de que todos los subconjuntos independientes máximos tengan el mismo tamaño. { 1 , 2 , 3 , 4 } y { 1 , 2 , 3 , 5 , 8 } ambos son subconjuntos máximos independientes de { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } . Entonces, llamaremos independiente a un conjunto si todos sus 3 -los subconjuntos tienen sumas distintas, y todos sus 2 -los subconjuntos tienen sumas distintas. Ahora no parece tan fácil producir un contraejemplo, aunque si me viera obligado a adivinar, diría que todavía no es un matroide.

Incluso si resultara ser un matroide, solo habríamos encontrado el mínimo para un superconjunto de { 1 , 2 , 3 } , así que nos quedaría trabajo por hacer.

Construir un conjunto de números para que las particiones de los 3 elementos tengan diferentes sumas de subconjuntos
RespuestasAquíPolítica de privacidad1y, 0v