Probar

Question

Pregunta:

$A \subset \{1,2,3,...,40\}$ tal que \begin{align} &\forall a,b\in A\\ &|a-b|\ne4,\quad|a-b|\ne9 \end {align} Demuestre que$n(A)<20$.

Encontré un caso de$n(A)=19$ que es$A=\{13m+n|m=0,1,2,\space n=1,3,4,6,9,11\}\cup\{40\}$, pero no pude probar que$19$ es el máximo. Gracias.

Answer 1

Lema : Dado $13$ números consecutivos $a+1,...,a+13$ $7$ elemento subconjunto $A$ de este conjunto, existen dos elementos en $A$ que difieren por cualquiera de las $4$ o $9$.

Prueba: Supongamos $A$ ser un subconjunto tal que no hay dos elementos en $A$ difieren por cualquiera de las cuatro o nueve. Si $a+m \in A$, entonces queremos ver cómo muchos de los elementos de la membresía de este reglamento en $A$. Si $m=1, ..., 4$, esto descarta $2$ elementos, a saber,$a+m+4,a+m+9$. Si $m = 10,...,13$, esto descarta dos elementos, a saber,$a+m-4,a+m-9$. Si $m = 5,...,9$, esto descarta dos números : $a+m-4,a+m+4$. Por lo tanto, el número de miembros de $a+m$ siempre las normas de otros dos números de la lista.

Vamos a llamar $B = \{a+1,a+2,a+3,a+4\}$, $C = \{a+5,a+6,a+7,a+8,a+9\}$ y $D = \{a+10,a+11,a+12,a+13\}$.

Tenga en cuenta que $A$ de las acciones, al menos, tres de sus elementos con uno de estos subconjuntos. Si comparte tres elementos con $B$, entonces estas de eliminar exactamente tres elementos cada uno de$C$$D$, lo que deja sólo dos en $C$ y una en $D$, por lo que el $A$ puede tener sólo seis elementos.

Del mismo modo, si se comparte tres elementos con $D$, entonces estas de eliminar exactamente tres elementos en $B$$C$, lo que deja sólo dos en $C$ y una en $B$, por lo que el $A$ puede tener sólo seis elementos.

Si comparte tres elementos con $C$, entonces tenemos tres casos:

1 : Si no $a+5$ ni $a+9$ es un miembro de $A$, entonces esto elimina a los tres miembros de $B$$D$. Que deja a los cuatro elementos en total, pero tenga en cuenta que tanto $a+5,a+9$ no puede ser ambas en $A$ como su diferencia es $4$. Por lo tanto, $A$ puede tener sólo seis elementos.

2: Si $a+5$ es un miembro de $A$, entonces esto elimina tres opciones de las $B$, y dos opciones de $D$. Por lo tanto, tenemos dos opciones a la izquierda en $D$ y una en $B$, lo $A$ puede tener en la mayoría de los seis elementos.

3 : Una cosa similar a la anterior, para $a+9$ ser miembro de $A$.

Finalmente, el lema queda demostrado. Con esto, vamos a $A$ ser un subconjunto de a $\{1,...,40\}$ que ha $20$ elementos. A continuación, $A$ acciones $19$ elementos con $\{1,...,39\}$, por lo que uno de los subconjuntos $\{1,...,13\},\{14,...,26\},\{27,...,39\}$ de las acciones de al menos siete elementos con $A$. A partir de aquí, utilice el lema para obtener una contradicción.

Por lo tanto, $A$ debe tener menos de diecinueve elementos. Usted ha proporcionado una $19$ elemento del subconjunto, felicitaciones. Además, tenga en cuenta que cualquier diecinueve elemento del subconjunto de la satisfacción de la anterior propiedad debe contener $40$.

EDIT: no he comprobado lo que sucede si $B,C,D$ termina compartiendo cuatro elementos con los $A$, pero se puede comprobar incluso que esto no funciona. Pero yo prefiero la prueba a continuación, por Muralidharan.

Se puede generalizar este resultado?

Lema : Vamos a $k$ ser impar, y $c,d$ dos números tales que $c + d=k$. Entonces, cualquier subconjunto de a $\{a+1,...,a+k\}$ de tamaño, al menos, $\frac {k+1}2$ contiene dos elementos que, bien se diferencian por $c$ o $d$.

Answer 2

Otra prueba de la Lema en la solución anterior:

Poner trece puntos $1,2,\ldots, 13$ en un círculo y conectar dos de aquellos con los bordes si se diferencian por 4 o 9. Podemos obtener un gráfico de grado 2 (que es cada vértice tiene dos incidentes bordes). Ahora si es posible elegir 7 vértices tal que no hay dos están conectados por una arista, luego de la eliminación de estos vértices y las aristas incidentes en ellos se retire 14 bordes de la gráfica original, pero que la gráfica tiene sólo 13 de los bordes.