Problema de tipo Ramsey (variante de personas en una fiesta)

Question

No es $n$ de la gente en una fiesta. Demostrar que hay dos personas que, de los restantes $n-2$ de la gente, hay, al menos, $\lfloor n/2\rfloor-1$ de ellos, cada uno de los cuales cualquiera sabe tanto o más conoce ninguno de los dos. Se supone que "saber" es una relación simétrica, y que $\lfloor n/2\rfloor$ denota el mayor entero menor o igual a $n/2$.

Fuente: Principios y Técnicas en la Combinatoria por Koh y Chen.

Esta es mi idea:

Ya sea una persona conoce a alguien o no. Si hay al menos $2$ de la gente que no sabe uno ni que sepan $0$ persona entonces puedo llevar a estas dos personas y estoy seguro de que estos dos son desconocidas para el resto de $n-2$ de la gente.

Así que supongamos que el número de personas que no conocen a nadie es $1$ o cero.

Vamos a empezar si no hay gente que no conoce a nadie (todo el mundo conoce a alguien). Así que el único número posible de amigos que una persona puede tener es de $1, 2, 3, . . , n-1$. O $n-1$ opciones. Puesto que hay n personas por el Principio del Palomar habrá por lo menos dos que tengan el mismo número de amigos. Deja que estos dos se $P1$$P2$. Deje $k=$ el número de amigos de $P1=$ el número de amigos de $P2$.

Vamos

$A=$ el conjunto contaning $P1$ e su $k$ amigos. $|A|=k+1$

$B=$ el conjunto contaning $P2$ e su $k$ amigos. $|B|=k+1$

Si $A$ $B$ son disjuntas, a continuación, $|A|+|B|=2k+2\leq n$ o $k\leq\frac{n}{2}-1$.

Aquí viene mi problema. Ya que si $k=\frac{n}{2}-1$ $|A|=|B|=\frac{n}{2}$ $A$ $B$ son distintos, yo no puedo mostrar lo que el problema está pidiendo.

Alguna idea chicos? Tal vez algunos consejos. :) Gracias.

ACTUALIZACIÓN

Me acabo de enterar de que este problema es similar al siguiente:

Un gráfico de ha $n>2$ puntos. Demostrar que podemos encontrar dos puntos de $A$ $B$ tal que al menos el $\lfloor n/2\rfloor-1$ restante de los puntos se unen a ambos o ninguno de $A$$B$.

Que es un problema en 1985 USAMO.

No entiendo muy bien la solución, aunque.

Answer 1

Esta no es una solución, sino que está orientado a por qué el enfoque de igualdad de número de amigos que no puede trabajar. Supongamos $n=4$, y el pueblo se $a,b,c,d$ y están dispuestas en una línea de $abcd$ donde $x$ conoce $y$ si y sólo si $x,y$ son adyacentes en la línea. A continuación, los extremos $a,d$ han $1$ amigo, y los empaques de $b,c$ han $2$ amigos, sin embargo, ni el par de obras.

Desde aquí $n/2-1=1$ un par de obras iff tienen un amigo en común o común, no el amigo. Si miramos $b,c$ cada uno con 2 amigos, a continuación, $b$ datos $a$ pero no $d$, mientras que $c$ conoce $d$ pero no $a$. De modo que el par $b,c$ no funciona, aunque cada uno ha $2$ amigos. Del mismo modo se puede demostrar que el par $a,d$ no funciona.

Por otro lado, cualquier otra pareja hace el trabajo, es decir, si usted toma dos con diferentes números de amigos en este ejemplo, ese par de obras. Aquí esto significa tomar uno en un extremo y el otro en uno de los interiores de las posiciones. Por ejemplo, el par $a,b$ no sabe $d$, por lo que el par $a,b$ obras, mientras que el par $a,c$ cada uno sabe $b$, por lo que el par $a,c$ obras. (Las otras dos posibilidades son simétricas a estos).

Parece que a partir de este ejemplo, que uno tiene que mirar más que algunos de los bienes de una persona, tales como el número de amigos, para comprobar esta afirmación.