Pigeonhole Principio Problema combo desigualdad

Question

Demuestre que para cualquier subconjunto de elementos$\{1,2,3,...,300\}$ con$102$, existen elementos$M$ y$x$ en ese subconjunto tal que$100<M-x<200$.

Creo que este es un problema de casillero, quiero construir$101$ pigeonholes pero en vano, puede alguien dar una ayuda aquí.

Answer 1

Deje $N=100$, y deje $A$ ser un subconjunto de a $\lbrace 1,2,3,4, \ldots, 3N\rbrace$ contiene, al menos, $N+2$ los distintos elementos. Tenemos que encontrar a $x,y\in A$ con $N \lt y-x \lt 2N$.

Deje $B=A \cap \lbrace 1,2,3,4, \ldots, N+1\rbrace$ ; denotar por $t$ el número de elementos en $B$, y por $b_1 \lt b_2 \lt \ldots \lt b_t$ los elementos en $B$. Supongamos primero que $t\neq 0$.

Si uno de los $N-1$ elementos $b_1+(N+1),b_1+(N+2), \ldots , b_1+(2N-1)$ en $A$, teniendo en $x=b_1$ hemos terminado.

Si uno de los $t-1$ elementos $b_2+(2N-1), \ldots, b_t+(2N-1)$$A$, luego podemos tomar la $y$ a ese elemento y hemos terminado.

De lo contrario, sólo hemos excluido $N-1+t-1$ elementos de $A$, por lo que

$$|A\cap \lbrace N+2,N+3 \ldots,3N \rbrace| \leq |\lbrace N+2,N+3 \ldots,3N \rbrace|-(N+t-2)=(2N-1)-(N+t-2)=N-t+1.$$

El número total de elementos en $A$ es que en la mayoría de $t+N-t+1=N+1$, contradicción.

Así que debemos tener $A \cap \lbrace 1,2,3,4, \ldots, N+1\rbrace=\emptyset$, y por simetría $A \cap \lbrace 2N-1,2N, \ldots, 3N\rbrace=\emptyset$. Pero, a continuación, $A \subseteq \lbrace N+2,N+3, \ldots, 2N-2\rbrace$ $A$ tiene más de $N-3$ elementos de contradicción.

Answer 2

Sugerencia: Poner todos los 300 puntos en un círculo. Queremos mostrar que algunos de los $a$ en el set elegido tiene un punto que está en el 99 puntos opuestos en el círculo.

---

Solución: Si no, a continuación, elija cualquiera de los $a$ en el conjunto; el resto de los 101 puntos se encuentran en los 200 puntos alrededor de $a$. Par de estos para que los más lejanos en el sentido contrario se combina con la más cercana de las agujas del reloj, con la distancia dentro de un par exactamente 101 o 199. Hay un centenar de pares y 101 puntos a cabo, por lo que algunos par contiene dos puntos, una contradicción.

No sé si hay una manera más prolija.

Answer 3

Supongamos que existe un subconjunto $S$ con 102 elementos que no satisface la propiedad deseada. A continuación, para cada par de elementos de a $(M,x)$ en el subconjunto, $M - x \le 100$ o $M - x \ge 200$.

Desde $|S| = 102$,$\max S - \min S \ge 101$, lo $\max S - \min S \ge 200$. Por lo tanto $\min S \le \max S - 200 \le 300-200 = 100$.

Deje $S_1 = \{x \mid \max S - x \ge 200\}$, que contiene $\min S$ y por lo tanto es no vacío. Deje $S_2 = \{x \mid \max S - x \le 100\}$, que contiene $\max S$, por lo que también es no vacío. Ahora vamos a $M = \min S_2$$x = \max S_1$. Si $M - x \ge 200$$\max S - x = (\max S - M) + (M - x) \ge \max S + 100$, una contradicción, por lo $M - x \le 100$. A continuación,$\max S - x = (\max S - M) + (M - x) \le 200$. Por lo tanto $\max S = x + 200$, lo $M = x + 100$$\max S = M + 100$. A continuación,$S_2 = \{M,\max S\}$$S = \{1,2,\dots,100,200,300\}$. Sin embargo, este conjunto no satisface el requisito del puesto $200 - 2 = 198$.

Esta contradicción muestra que a cada subconjunto con 102 elementos debe satisfacer la propiedad.