Question

Sea $m \ge 3$ un entero y sea $S = \{3, 4, 5, \ldots, m\}.$ Halle el menor valor de $m$ tal que para toda partición de $S$ en dos subconjuntos, al menos uno de los subconjuntos contiene enteros $a,$ $b,$ y $c$ (no necesariamente distintos) tales que $ab = c.$

Nota: una partición de $S$ es un par de conjuntos $A,$ $B$ tales que $A \cap B = \emptyset$ y $A \cup B = S.$

Let $m \ge 3$ be an integer and let $S = \{3, 4, 5, \ldots, m\}.$ Find the smallest value of $m$ such that for every partition of $S$ into two subsets, at least one of the subsets contains integers $a,$ $b,$ and $c$ (not necessarily distinct) such that $ab = c.$

Note: a partition of $S$ is a pair of sets $A,$ $B$ such that $A \cap B = \emptyset$ and $A \cup B = S.$

Respuesta

Respuesta: 243

Conceptos:deducción lógica argumento extremal

Nivel de dificultad: 3060

Pista pequeña:

Pruebe particiones en dos subconjuntos que mantengan separados los números pequeños y sus productos por pares, como separar $\{3, \ldots, 8\}$ de $\{9, \ldots, 80\}$

Try two-subset partitions that keep small numbers and their pairwise products apart, such as separating $\{3, \ldots, 8\}$ from $\{9, \ldots, 80\}$

Pista grande:

Para la cota superior, siga las potencias de $3:$ una vez que $3$ y $9$ quedan forzados en subconjuntos distintos, coloque $27$ y $81,$ y una potencia más crea una contradicción

For the upper bound, follow the powers of $3:$ once $3$ and $9$ are forced into different subsets, place $27$ and $81,$ and one more power creates a contradiction

Solución:

Primero, $m = 243$ funciona. Suponga que $S = \{3, 4, \ldots, 243\}$ se particiona en $T$ y $U$ sin que ninguno contenga un producto, y digamos que $3 \in T.$ Entonces $9 = 3 \cdot 3$ debe estar en $U,$ así que $81 = 9 \cdot 9$ debe estar en $T,$ y luego $243 = 3 \cdot 81$ debe estar en $U.$ Ahora considere $27:$ si $27 \in T,$ entonces $3 \cdot 27 = 81$ pone un producto en $T;$ si $27 \in U,$ entonces $9 \cdot 27 = 243$ pone uno en $U.$ En cualquier caso llegamos a una contradicción.

Para $m = 242,$ la partición $T = \{3, \ldots, 8\} \cup \{81, \ldots, 242\}$ y $U = \{9, \ldots, 80\}$ evita productos: dos elementos de $\{3, \ldots, 8\}$ se multiplican dando algo en $[9, 64] \subseteq U,$ cualquier producto que involucre un elemento de $\{81, \ldots, 242\}$ es al menos $3 \cdot 81 = 243 \gt 242,$ y dos elementos de $U$ se multiplican dando al menos $81 \gt 80.$

Por lo tanto, el menor $m$ con esta propiedad es $243.$

First, $m = 243$ works. Suppose $S = \{3, 4, \ldots, 243\}$ were partitioned into $T$ and $U$ with neither containing a product, and say $3 \in T.$ Then $9 = 3 \cdot 3$ must lie in $U,$ so $81 = 9 \cdot 9$ must lie in $T,$ and then $243 = 3 \cdot 81$ must lie in $U.$ Now consider $27:$ if $27 \in T,$ then $3 \cdot 27 = 81$ puts a product in $T;$ if $27 \in U,$ then $9 \cdot 27 = 243$ puts one in $U.$ Either way we reach a contradiction.

For $m = 242,$ the partition $T = \{3, \ldots, 8\} \cup \{81, \ldots, 242\}$ and $U = \{9, \ldots, 80\}$ avoids products: two elements of $\{3, \ldots, 8\}$ multiply to something in $[9, 64] \subseteq U,$ any product involving an element of $\{81, \ldots, 242\}$ is at least $3 \cdot 81 = 243 \gt 242,$ and two elements of $U$ multiply to at least $81 \gt 80.$

Hence the smallest such $m$ is $243.$

2010 AIME I Problema 12

Respuesta: 243

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años