$n$ personas que han de ser ordenados en una línea, una después de la otra. Decimos que:
- Una persona X se ve a una persona Y, si X está detrás de Y.
- Una persona X que escucha una persona Y, si X representa a la mayoría de las $k$ posiciones en el frente de Y.
Cada persona tiene dos amigos (amistad, relación no es simétrica).
Una orden es buena si cada persona ve o se oye tanto en sus/sus amigos
¿Cuál es el mayor valor de $n$ (como una función de la $k$) para que un buen orden siempre existe?
Aquí están algunos ejemplos.
Al $n\leq k+1$, un buen fin de que siempre existe, ya que cada persona puede ver o escuchar a todas las demás personas.
Al$k=1$$n\geq k+2$, un buen fin de que nunca existe, ya que la parte delantera de la persona se ve a nadie y se escucha en la mayoría de un solo amigo.
Al$k=2$$n=4$. un buen fin de que siempre existe y se puede encontrar de la siguiente manera. Poner una arbitraria persona (por ejemplo, Alice) en la parte delantera. Puso sus dos amigos justo detrás de ella, para que ella pueda escuchar a ambos. Poner la cuarta persona en la parte de atrás.
Al$k=2$$n=5$, las cosas se están poniendo interesantes. Supongamos que ponemos Alicia en el frente, y sus amigos son Bob y Carl. De modo que el orden tiene que empezar como Alicia-Bob-Carl o Alice-Carl-Bob. Pero, si Bob son los amigos de David y Eva y Carl son los amigos también David y Eva, entonces uno de ellos (el justo detrás de Alice) no escuchar tanto a sus amigos.
Podemos tratar de poner a Bob en la parte delantera, a continuación, David y Eva. Pero, si tanto David amigos y Eva son los amigos de Alice y Carl, uno de ellos (el justo detrás de Bob) no escuchar tanto a sus amigos.
En ese caso, podemos ordenar a los agentes como: Carl-David-Eva-Alice-Bob; este orden satisface todos los requerimientos.
Al parecer, la búsqueda de un buen orden se vuelve más difícil cuando se $n$ es mayor. De ahí la pregunta.
ACTUALIZACIÓN 1: al $n\leq 2k$, un buen fin de que siempre existe. Poner una hoja de agente (por ejemplo, Alice) en la parte delantera. Poner a uno de sus amigos (por ejemplo, Bob) justo detrás de ella. Poner uno de Bob amigos (es decir, Carl) justo detrás de él. Continuar de esta manera hasta que $k$ colocar a las personas. A continuación, en la posición $k+1$, poner Alice segundo amigo (si no está ya colocado). En la posición $k+2$, poner de Bob segundo amigo (si no está ya colocado), y así sucesivamente. Así que la gente en posiciones de $1,\dots,k$ puede escuchar todos sus amigos. Desde $n\leq 2k$, las personas en posiciones de $k+1,\dots,2k$ puede escuchar todo el mundo detrás de ellos. Por lo tanto el orden es bueno.
Esto parece no muy apretado, ya que sólo nos recogió el frente de la persona arbitrariamente. Seguro que podemos hacerlo mejor mediante la selección de la parte delantera de la persona con más cuidado, ¿verdad?
ACTUALIZACIÓN 2: Basado en Kevin probabilístico argumento, he probado el siguiente recuento de argumento. La relación de amistad puede ser representada por un vector de tamaño $2n$. Para cada una de las 2 posiciones en el vector, no se $(n-1)(n-2)$ opciones, por lo que el número total de vectores es $\approx n^{2n}$. Por otro lado, el número total de órdenes de es $n!$. Por lo tanto, si pudiéramos probar que cada pedido es buena por menos de $n^{2n} / n!$ vectores, entonces esto significaría que algunos de los vectores no tienen buena órdenes.
Por desgracia, la segunda afirmación es probablemente no es cierto. Revisión de una orden, y volver a numerar los agentes que el orden es $1,\dots,n$. Para la construcción de un vector para que este orden es bueno, tenemos $k(k-1)$ opciones para los amigos de la persona 1, $(k+1)k$ opciones para los amigos de la persona 2, ..., $(n-2)(n-1)$ opciones para los amigos de la persona $n-k$, e $(n-2)(n-1)$ opciones para los amigos de el resto de personas $n-k,\dots,n$. La multiplicación de todos los números que da mucho más de $n^{2n} / n!$. Por lo que esta contando el argumento no funciona.
ACTUALIZACIÓN 3: Esta pregunta está relacionada con: cuántos nodos se necesita? Si nuestra amistad gráfico si $k$-denso (como se define en la pregunta), luego de un buen orden no existe. Prueba: independientemente de que hemos puesto en la primera $k$ lugares, estos $k$ de las personas tienen juntos $k+1$ amigos además de a sí mismos. Así, uno de estos la gente no va a escuchar a uno de sus amigos. Así, un límite inferior de $n$ en la pregunta implica una cota superior de a $n-1$ en la pregunta actual. En particular, para $k=2$, existe un 2-denso gráfico con 7 nodos; de ahí que el mayor número de personas para las que un buen orden que existe es en la mayoría de los 6 (Pedro mostró una mejor cota superior: 5).
