$A\subseteq \{1,2,3,\ldots2000\}$, y para cualquier$a,b\in A,$$|a-b|$ no es igual a 4 o 7. Entonces, como mucho, ¿cuántos elementos contiene$A$?
Para la condición general,$|a-b|$ no es igual a$i$ o$j, (i,j \in A)$, ¿cómo resolver la pregunta?
Respuestas
¿Demasiados anuncios?
justartem
Puntos
13
La respuesta es $182\times 5=910$. Una solución óptima es $\lbrace x\in[1,2000] | x\equiv 1,3,4,6 \ \text{ or } 9 \ \textsf{mod} \ 11\rbrace$. (con un poco más de trabajo, uno puede demostrar que no son exactamente $183$ soluciones óptimas y los describen).
Llame a un conjunto de $A$ de los enteros distinguido $|a-b|$ no es igual a $4$ o $7$ cualquier $a,b\in A$.
Lema 1. Si $A \subseteq [1,10]$ se distingue, entonces $A$ contiene en la mayoría de los cinco elementos.
La prueba del lema 1. Cada uno de los conjuntos de $\lbrace 1,5\rbrace$, $\lbrace 2,9\rbrace$, $\lbrace 3,7\rbrace$, $\lbrace 4,8\rbrace$, $\lbrace 6,10\rbrace$ tiene al menos un elemento en común con $A$.
Lema 2 Si $A\subseteq [1,11]$ se distingue, entonces $A$ contiene en la mayoría de los cinco elementos.
La prueba del lema 2. Por el lema 1, podemos suponer que $11\in A$ (y por lo tanto $4\not\in A,7\not\in A$). El uso de la simetría $x\mapsto 12-x$, podemos también asumen $1\in A$ (y, por tanto,$5\not\in A,8\not\in A$). Si $6\in A$, a continuación, $A$ no contiene $2$ o $10$, lo $A\subseteq \lbrace 1,3,6,9,11 \rbrace$ y hemos terminado. Por consiguiente, se puede suponer que $6\not\in A$. Entonces $A$ puede ser escrito $A=\lbrace 1,11 \rbrace\cup B$ donde $B$ es un subconjunto de $\lbrace 2,3,9,10 \rbrace$ tiene al menos un elemento en común con cada uno de los de $\lbrace 2,9\rbrace$$\lbrace 3,10\rbrace$. Esto concluye la prueba.
Lema 3 Si $A\subseteq [1,2000]$ se distingue, entonces $A$ contiene en la mayoría de los 910 elementos.
La prueba del lema 3. Aplicar el lema 2 en la de nueve element set $A\cap [1,9]$, y en cada una de las $181$ once elemento de los conjuntos de $A\cap [11k-1,11k+9]$.
