Partición de $S = \{1,2,\dots, 3n\}$ en tres subconjuntos $A, B, C$ tal que $|A| = |B| = |C| = n$

Question

Deje $n$ ser un entero positivo y considerar el conjunto $S = \{1,2,\dots ,3n\}$. Demostrar que, para cada partición de $S$ en 3 subconjuntos $A, B, C$ tal forma que:

i) $|A| = |B| = |C| = n$ (aquí se $|X|$ denota el número de elementos de un conjunto $X$)

ii) $A \cap B = B \cap C = C \cap A = \varnothing$ $A \cup B \cup C = S$

existen 3 elementos $a \in A, b \in B, c \in C$ de tal manera que uno de $a, b, c$ es igual a la suma de los otros dos elementos.

Answer 1

Supongamos lo contrario.

Escribir $A = \{a_1, \dotsc, a_n\}$, $B = \{b_1, \dotsc, b_n\}$, y $C = \{c_1, \dotsc, c_n\}$, cada uno representado cada vez más, de tal manera que $a_1 < b_1 < c_1$. Por lo tanto $a_1 = 1$. Set $k = b_1 - 1$, por lo que el $\{1, \dotsc, k\} \subseteq A$.

Ahora, para cualquier $b \in B$, si alguno de $b+1, \dotsc, b+k$$C$, entonces tenemos una prohibido triple. Del mismo modo para cualquier $c \in C$, el éxito $k$ elementos no puede ser en $B$. Así que, entre todos los elementos de la $B$ e de $C$ debe ser de al menos $k$ elementos de $A$.

Considere la posibilidad de cualquier $c \in C$ cuyo antecesor es que no se en $C$, es decir, de modo que $c - 1 \notin C$. A continuación, antes de $c$ tenemos, al menos, $k$ elementos de $A$; en particular,$c - k \in A$. Si $(c - k) + b_1 = c + 1$$C$, entonces tenemos una prohibido triple. Del mismo modo, $(c - (k-1)) + b-1 = c + 2, \dotsc, (c-1)+b_1 = c+k$ no puede ser en $C$. De modo que podemos tener a lo sumo un elemento de $C$ ocurren de forma sucesiva, cuyas $k$ predecesores y $k$ sucesores están todos en $A$.

Por lo tanto, el más compacto que los elementos de la $C$ puede ocurrir en un patrón como este: $$ \underbrace{A\dotsm Un}_k C \underbrace{A\dotsm Un}_k C \dotsm\underbrace{A\dotsm Un}_k C, $$ donde la última entrada es $3n$ sí. Si alguno de los elementos de $B$ fueron intercalados, incluso más de los elementos de $A$ tendría que aparecer.

Para cada elemento de la $C$ tenemos, al menos, $k$ elementos de $A$, contradiciendo ese $|C| = |A|$, a menos que $k = 1$. Incluso entonces, la única manera de tener sólo $n$ elementos de $A$ aparecen con el patrón $$ AC AC \dotsm CA $$ donde $c_n = 3n$, lo que se contradice con que $1 \in A$.