Encuentre el número natural n más pequeño tal que si el conjunto $\{1,2,...,n\}$ se divide arbitrariamente en dos subconjuntos no intersectantes.

Question

Encuentra el número natural más pequeño $n$ tal que si el conjunto $\{1,2,\dots,n\}$ se divide arbitrariamente en dos subconjuntos no intersectantes entonces uno de los subconjuntos contiene tres números distintos tales que el producto de dos de ellos es igual al tercero.

Supongamos que tengo dos conjuntos:

$A$ y $B

Entonces $1,2,3$ tienen que estar en un conjunto, vamos a ponerlos en $A$. Esto hace que $6$ deba estar en $B$. Si ponemos $4$ en A, entonces $8,12$ deben estar en $B$. Si ponemos $5$ en A, entonces $10,15$ deben estar en $B$. Si ponemos $7$ en A, entonces $14,21$ deben estar en $B$.

Así que hasta ahora tengo:

$$ A=\{1,2,3,4,5,7\} $$ $$ B=\{6,8,12,10,14,15,21\} $$

No veo un patrón particular, así que supongo que hay un enfoque diferente para este problema porque esto podría continuar para siempre. ¿Alguna idea?

EDITAR: Malinterpreté la pregunta. Aquí están mis nuevos conjuntos $$ A=\{1,2,3,6,9,12,24,36,72,18\} $$ $$ B=\{4,5,7,8,32,10,40,56,28,35,20\} $$

Así es como va mi conjunto hasta ahora

Answer 1

La respuesta es $n=96$.
Para demostrar esto, tome cualquier $n\ge96$ y asuma que dividimos el conjunto $\{1,2,\cdots,n\}$ en la unión disjunta de $A$ y $B$. Que $P(A)$ denote el conjunto de productos de elementos distintos (y diferentes de $1$) de $A$, similarmente $P(B)$ denote el conjunto de productos de elementos distintos (y diferentes de $1$) de $B.

Asuma sin pérdida de generalidad que $48\in B$ y considere casos de la siguiente manera. Se forman cuatro casos basados en si $2$ está en $A$ o en $B$, y si $3$ está en $A$ o en $B. En cada caso asumimos que $A\cap P(A)=\emptyset$, $B\cap P(B)=\emptyset$ y derivamos una contradicción.

Caso cuando $\{2,3\}\subseteq A$. Entonces $6\in B$ (ya que $6=2\cdot3$ y $\{2,3\}\subseteq A$). Entonces $8\in A$ (ya que $8=48/6$ y $\{6,48\}\subseteq B$), así que $4=8/2\in B. Entonces $24=3\cdot8=4\cdot6\in P(A)\cap P(B)$, lo cual es suficiente para derivar una contradicción. (De hecho, $24$ debe estar en $A$ o en $B$. En el primer caso, la contradicción es que $24=3\cdot8\in A\cap P(A)$, en el segundo caso $24=4\cdot6\in B\cap P(B)$.)

Tal vez sea más fácil visualizar el argumento anterior de la siguiente tabla, donde los números más hacia la derecha se agregan a $A$ o $B como consecuencia de los números (a la izquierda) que se agregaron anteriormente.

$$ \begin{array}{l|c|c|c|c|r} \hline A & 2,\ {\color{red}3} & & {\color{red}8} & & {\color{red}{24}} &\\ \hline B & 48 & {\color{blue}6} & & {\color{blue}4} & {\color{blue}{24}} &\\ \hline \end{array} $$

Caso cuando $2\in A$, $3\in B$. Entonces $16=48/3\in A$, $8=16/2\in B$, $\{6=48/8,\ 24=3\cdot8\}\subset A$, $\{4=24/6,\ 12=24/2,\ 48\}\subset B$, y $4\cdot12=48. Este caso visualizado de la siguiente manera:
$$ \begin{array}{l|c|c|c|c|r} \hline A & 2 & 16 & & 6,\ 24 & &\\ \hline B & 3,\ {\color{blue}{48}} & & 8 & & {\color{blue}{4,\ 12}} &\\ \hline \end{array} $$

Caso cuando $3\in A$, $2\in B. Then $24=48/2\in A$, $8=24/3\in B. $\{4=8/2,\ 6=48/8\}\subset A, entonces $4\cdot6=24$ with $\{4,6,24\}\subset A.

Este caso visualizado como sigue:
$$ \begin{array}{l|c|c|c|c|r} \hline A & 3 & {\color{red}{24}} & & {\color{red}{4,\ 6}} &\\ \hline B & 2,\ 48 & & 8 & & \\ \hline \end{array} $$

Finalmente, caso $\{2,3\}\subseteq B. Entonces $\{6=2\cdot3,\ 96=2\cdot48,\ 16=48/3\}\subset A, una contradicción como $6\cdot16=96.

Este último caso visualizado como sigue:
$$ \begin{array}{l|c|c|c|c|r} \hline A & & {\color{red}{6,\ 96,\ 16}} & \\ \hline B & 2,\ 3,\ 48 & & \\ \hline \end{array} $$

Queda por demostrar que se podría dividir el conjunto $\{1,2,\cdots,95\}$ en la unión disjunta $A\cup B$ de manera que ningún par de números distintos (y diferentes de $1$) en $A$ tengan un producto en $A, y ningún par de números distintos (y diferentes de $1$) en $B$ tengan un producto en $B.
Es decir, $A\cap P(A)=\emptyset$ y $B\cap P(B)=\emptyset.

Usando consideraciones como las anteriores, comenzamos con $\{6,8,12,16,24,36,18\}\subset A$ y $\{2,3,4,48,72\}\subset B y agregamos los números restantes hasta $95$ uno tras otro en $A$ o en $B intentando evitar un conflicto. Esto se hizo a mano (y después se verificó con una computadora).

La siguiente partición funciona:

$A=\{6,8,10,12,14,15,16,18,20,21,22,24,26,27,28,30,32,33,34,35,36,38,39,40,42,44,45,46,50,51,52,55,57,58,62,63,65,68,69,74,75,76,77,78,82,85,86,87,91,92,93,94,95\}$

y

$B=\{1,2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,48,49,53,54,56,59,60,61,64,66,67,70,71,72,73,79,80,81,83,84,88,89,90\}.

Para facilitar la verificación, también enumeramos $P(A)\cap\{1,2,\cdots,96\}$ y $P(B)\cap\{1,2,\cdots,96\}.

$P(A)\cap\{1,2,\cdots,96\}=\{48,60,72,80,84,90,96\}.

$P(B)\cap\{1,2,\cdots,96\}=\{6,8,10,12,14,15,18,20,21,22,26,27,28,33,34,35,36,38,39,44,45,46,50,51,52,55,57,58,62,63,65,68,69,74,75,76,77,82,85,86,87,91,92,93,94,95,96\}.

Algo arbitrariamente $1$ y todos los números primos terminaron en $B. Esta partición no es única ya que $1, 11 y todos los primos $p\ge17$ (o cualquier subconjunto de estos) podrían moverse de $B$ a $A sin problema. (Pero $13 no podría moverse de $B$ a $A ya que esto crearía un conflicto $6\cdot13=78). Muchas otras variaciones también son posibles.

Una última edición para colocar $P(A), A, B, P(B) todos juntos para una inspección visual más fácil.

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & & & & & & & \\ \hline A & & & & & &6 & & 8& &10 & &12 & &14 &15 & 16& \\ \hline B &1 &2 &3 &4 &5 & &7 & &9 & &11 & &13 & & & & \\ \hline P(B) & & & & & &6 & &8 & &10 & &12 & &14 &15 & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & & & & & & \\ \hline A & &18 & &20 &21 &22 & &24 & &26 &27 &28 & &30 & &32 & \\ \hline B &17 & &19 & & & &23 & &25 & & & &29 & &31 & & \\ \hline P(B) & &18 & &20 &21 &22 & & & &26 &27 &28 & & & & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|r} \hline P(A) & & & & & & & & & & & &60 & & & & & \\ \hline A & &50 &51 &52 & &