Para lo cual $n\in\Bbb N$ podemos dividir $\{1,2,3,...,3n\}$ en $n$ subconjuntos cada uno con $3$ elementos tales que en cada subconjunto $\{x,y,z\}$ tenemos $x+y=3z$ ?

Question

Para lo cual $n\in \mathbb{N}$ podemos dividir el conjunto $\{1,2,3,\ldots,3n\}$ en $n$ subconjuntos cada uno con $3$ elementos tales que en cada subconjunto $\{x,y,z\}$ tenemos $x+y=3z$ ?

Desde $x_i+y_i=3z_i$ para cada subconjunto $A_i=\{x_i,y_i,z_i\}$ tenemos $$4\sum _{i=1}^n z_i=\sum _{i=1}^{3n}i = {3n(3n+1)\over 2} \implies 8\mid n(3n+1) $$ así que $n=8k$ o $n=8k-3$ . Ahora no es difícil ver que si $k=1$ tenemos tal partición.

• Para $n=5$ que tenemos: $$A_1= \{9,12,15\}, A_2= \{4,6,14\}, A_3= \{2,5,13\}, \\A_4= \{10,7,11\}, A_5= \{1,3,8\}$$
• Para $n=8$ que tenemos: $$A_1= \{24,21,15\}, A_2= \{23,19,14\}, A_3= \{22,2,8\}, A_4= \{20,1,7\}, \\A_5= \{17,16,11\}, A_6= \{18,12,10\}, A_7= \{13,5,6\}, A_8= \{9,3,4\}$$

¿Y para $k\geq 2$ ? ¿Algún paso inteligente de inducción? ¿O alguna configuración "bien" conocida?

Fuente: Serbia 1983, ronda municipal, 3. grado

Answer 1

Si existe una solución para $N$ existe una solución para $7N+5$ .
La solución para $N$ utiliza números de $1$ a $3N$ . Entonces $$(3N+k, 15N+9+2k, 6N+3+k), k=1..3N+3\\ (12N+8+k,15N+10+2k,9N+6+k), k=1..3N+2$$ sienta los números de $3N+1$ a $21N+15$ encima de ellos.

Un método similar da una solución para $25N+8Q$ para todos $-13\le Q\le11$ siempre que exista una solución para $N\ge 13$ . Junto con la solución de @RobPratt, que cubre todas las $N=8M$ y todos $N=8M-3$ .

He iniciado una nueva pregunta para una versión diferente en Dividir $\{1,2,...,3n\}$ en triples con $x+y=4z$ y también Dividir $\{1,...,3n\}$ en triples con $x+y=5z$ - ¿no hay soluciones?

Answer 2

Este es el método de programación lineal entera que utilicé para encontrar particiones para todos estos casos $n\le 496$ con $n \equiv 0,5 \pmod 8$ . Enumera primero todas las triplas $\{x,y,z\}$ con $x+y=3z$ y $x,y,z$ elementos distintos de $[3n]:=\{1,\dots,3n\}$ . Para cada uno de estos triples $T$ y la variable de decisión binaria $u_T$ indicar si $T$ aparece en la partición. Las restricciones $$\sum_{T:\ i\in T} u_T = 1 \quad \text{for $ i\in[3n] $} \tag1$$ garantizar que cada elemento aparezca exactamente una vez en la partición.

Un enfoque alternativo consiste en introducir variables de holgura no negativas $s_i$ sustituye las restricciones de partición del conjunto $(1)$ con restricciones (de cobertura de conjuntos y cardinalidad) \begin{align} \sum_{T:\ i\in T} u_T + s_i &\ge 1 &&\text{for $i\in[3n]$} \tag2 \\ \sum_T u_T &= n \tag3 \end{align} y minimizar $\sum_{i=1}^{3n} s_i$ . Una partición de $[3n]$ en $n$ triples con $x+y=3z$ existe si y sólo si el valor objetivo óptimo es $0$ .