Fijado con una propiedad

Question

Este fue un problema de simulacro de olimpiada matemática que me envió un amigo.

Dejemos que $P$ sea un conjunto de números primos. Entonces, crea un conjunto $S$ de enteros positivos que satisface la siguiente propiedad:

1. Para cada elemento $p \in P$ , $p$ es un factor de al menos tres elementos en $S$ .

Demostrar que para todos los conjuntos $P$ y $S$ es posible dividir $S$ en 4 subconjuntos no vacíos tales que cada $p$ es un factor de al menos tres enteros.

Traté de considerar el elemento $a \in P$ que era un factor del menor número de elementos en $S$ y ver qué podía descubrir, pero no conseguí nada. También pensé que tal vez algún tipo de algoritmo funcionaría también, pero no hice ningún progreso. En general, no estoy muy seguro de cómo empezar.

Answer 1

Considere una partición $\{S_1,S_2,\ldots,S_k\}$ tal que

( $\ast$ ) cada uno $p \in P$ tiene múltiplos en al menos dos conjuntos diferentes $S_i$

para lo cual $k$ es lo más pequeño posible. (Obsérvese que existen particiones para las que ( $\ast$ ) es verdadera, como la partición con sólo monotones, debido a (1). Pretendemos demostrar que $k \le 3$ .

En efecto, supongamos que $k \ge 4$ . Por la minimidad de $k$ existe un $p \in P$ que sólo divide números en $S_1$ y $S_2$ ; de lo contrario, podríamos fusionar $S_1$ y $S_2$ y ( $\ast$ ) se mantendría. Del mismo modo, existe un $q \in P$ que sólo divide números en $S_3$ y $S_4$ . Pero ahora $S$ no contiene un múltiplo de $pq$ , lo que contradice (2).

Answer 2

No es del todo una respuesta, pero es demasiado larga para ser un comentario: ten en cuenta que los primos y la factorización aquí son un poco una pista falsa. Es posible reescribir esta pregunta de manera que no entren en juego. Para ver esto, dejemos que el conjunto de primos sea etiquetado como $\{p_1, p_2, \ldots, p_N\}$ (donde posiblemente no haya una última $N$ , en cuyo caso diremos que $N=\omega$ sólo por comodidad). A continuación, etiquete cada número $i\in S$ por el conjunto $s_i$ de los números $j$ tal que $p_j$ es un factor de $S$ . Por ejemplo, si $P$ es el conjunto $\{2, 3, 11\}$ y $S$ es el conjunto $\{12, 22, 99\}$ entonces tendríamos $p_1=2, p_2=3, p_3=11$ y $s_{12}=\{1,2\}$ desde $p_1$ y $p_2$ son los factores de $12$ ; de la misma manera $s_{22}=\{1,3\}$ y $s_{99}=\{2,3\}$ . Pero ahora podemos escribir la condición ' $p_j$ divide $i$ ' como ' $j$ es miembro de $s_i$ ' y sólo escribir $S$ en términos de $s_i$ (por ejemplo, aquí $S$ sería $\left\{\{1,2\}, \{1,3\}, \{2,3\}\right\}$ ) y sus propiedades iniciales se convierten en:

• por cada $n \leq N$ hay al menos dos conjuntos $s\in S$ tal que $n\in s$
• por cada $i, j\leq N$ hay al menos un conjunto $s\in S$ tal que $i\in s$ y $j\in s$ (o, de forma equivalente, $\{i,j\}\subseteq s$ )

Y su resultado se convierte en que es posible dividir $S$ en tres conjuntos $S_1, S_2, S_3$ tal que para cada $n\leq N$ al menos dos $S_i$ contienen un conjunto que tiene $n$ como elemento.