Encontrar elementos principales en un subconjunto

Question

Consideremos el conjunto a $S= \{1,2,\cdots,2n\}$. Deje $\mathscr{B}$ ser un subconjunto de a $S$ que contiene estrictamente a más de $n$ elementos.

• Demostrar que podemos encontrar elementos $m,k$ $\mathscr{B}$ tal que $m+k$ es primo.

Answer 1

Nos probar por la fuerte inducción en $n$ que si un subconjunto $A$ $S$ es tal que no hay dos elementos distintos suma a un primo, a continuación,$|A| \leq n$.

Esto es claramente cierto al $n=1$, ya que el $A$ es un subconjunto de a $\{1, 2\}$, e $1+2=3$ es un número primo, así que $|A| \leq 1$.

Supongamos que es cierto para $1 \leq n \leq k, k\geq 1$, entonces considere el $n=k+1$. Por Bertrand postulado, ya que $2(k+1)>1$, existe un extraño prime $p$ estrictamente entre el$2(k+1)$$4(k+1)$. Escribir $p=2(k+1)+l$, donde $1 \leq l \leq 2k+1$, $l$ impar. Considerar los pares de números $(l, 2(k+1)), (l+1, 2k+1), \ldots , (k+1+\frac{l-1}{2}, k+1+\frac{l+1}{2})$. $A$ debe tener en la mayoría de 1 elemento de cada par, de lo contrario $A$ contendrá 2 números cuya suma $p$, una de las principales. Por lo tanto, $A$ tiene más de $\frac{2(k+1)-l+1}{2}$ elementos en $\{l, l+1, \ldots , 2(k+1)\}$.

Por la hipótesis de inducción, $A$ tiene más de $\frac{l-1}{2}$ elementos en $\{1, 2, \ldots , l-1\}$. Por lo tanto,$|A| \leq \frac{2(k+1)-l+1}{2}+\frac{l-1}{2}=k+1$, por lo que estamos hecho por la fuerte inducción.

Por lo tanto, si tenemos un subconjunto de a $\{1, 2, \ldots , 2n\}$ estrictamente con más de $n$ elementos, entonces podemos encontrar 2 distintos elementos de este subconjunto tal que su suma es un número primo.