¿Que tiene que comprar la cerveza?

Question

Hay $115$ de los miembros en un equipo en el que todo el mundo tiene un teléfono inteligente. Ningún miembro del equipo desea comprar cerveza para todos los demás miembros del equipo. Pero un viernes, después de las horas de trabajo, todo el mundo expresa el deseo de tener la cerveza. El líder del equipo propone un juego, que todo el mundo acepta a jugar.

El juego consiste en que un miembro del equipo sería enviar un mensaje de "Cerveza" a uno de los otros miembros del equipo, que tiene que remitir a una persona distinta de la persona de quien él/ella recibió el mensaje. Al final de el juego de quien es la última persona con el mensaje de que tiene que comprar cerveza para todos los demás.

Alguien arbitrariamente establece un límite de tiempo para el juego. El líder del equipo inicia el juego, enviando el mensaje a alguien de su equipo. Suponiendo que cualquiera en el equipo podría enviar mensaje a cualquier persona sin ninguna dificultad, ¿cuál es la probabilidad de que al final del juego, cuando $2009$ de los mensajes se han pasado, es el jefe del equipo que se encuentra para ser el uno con el último mensaje, y de ahí, el uno para comprar cerveza para todos los demás?

Por lo tanto, hay $115$ vértices y hay un borde de uno a todos los demás vértices. La gráfica es, por lo tanto, $114-$regular y simple. Así, el problema es este: ¿Puede haber un camino a partir de un vértice $u$, y después de haber atravesado $2009$ bordes, de tal manera que uno no puede salir de un vértice por el mismo borde de un vino, que culminó de nuevo a $u$? Desde entonces, el camino de $u-u$ debe contener un ciclo, que puede ser de longitud $3$$115$, la pregunta es ¿existe un no-negativos solución de:

$2x_1+3x_2+...+115x_{114}=2009$

tal que tal $u-u$ path existe? Por ejemplo, $x_1=1000$ $x_2=3$ no puede ser una solución, ya que implicaría que uno llevó al borde de $v-v$, $v\in V(G)$, consecutivamente, lo cual no está permitido.

¿Cómo podemos resolver esto?

Answer 1

No entiendo el método que se está intentando, pero aquí es una solución para el problema. Considerar todas las secuencias $$x_0,x_1,\ldots,x_n$$ con $n$ pasos, del tipo que estamos considerando: que es $$x_k\in\{1,\ldots,115\},\ x_0=1,\ x_k\ne x_{k-1},\ x_k\ne x_{k-2}.$$ Queremos encontrar a $P(x_n=1)$ en el caso de $n=2009$.

Voy a suponer que la gente no "objetivo" que el líder, como se sugiere en otros comentarios, pero que se elija al azar de todas las posibilidades disponibles.

Deje $p_n$ la probabilidad de obtención de $x_n\ne1$ $x_{n-1}\ne1$ en dicha secuencia. La respuesta a tu problema es $$\frac{p_{2008}}{113}\ .$$ Ahora para $n\ge4$ hemos $$\eqalign{p_n &=P(x_n\ne1,\,x_{n-1}\ne1,\,x_{n-2}\ne1) +P(x_n\ne1,\,x_{n-1}\ne1,\,x_{n-2}=1)\cr &=\frac{112}{113}p_{n-1}+P(x_{n-1}\ne1,\,x_{n-2}=1)\cr &=\frac{112}{113}p_{n-1}+P(x_{n-2}=1,\,x_{n-3}\ne1,\,x_{n-4}\ne1)\cr &=\frac{112}{113}p_{n-1}+\frac{1}{113}p_{n-3}\ .\cr}$$ Esta relación de recurrencia, con adecuadas condiciones iniciales, puede ser resuelto en la forma habitual. La ecuación característica es cúbica: afortunadamente, $1$ es una raíz; por desgracia, los otros dos son sucios complejo surds. Si mi álgebra es correcta la respuesta es $$p_n=\frac1{(1-\alpha)(1-\beta)(\alpha-\beta)}\bigl[(\alpha-\beta)-(1-\beta)\alpha^n+(1-\alpha)\beta^n\bigr]$$ donde $$\alpha=\frac{-1+i\sqrt{451}}{226}\ ,\quad \beta=\frac{-1-i\sqrt{451}}{226}\ .$$ La evaluación por parte de Maple da la respuesta $$\frac{p_{2008}}{113}=0.008695652174$$ que está muy cerca de a $\frac1{115}$. Esto es de esperar ya que, como se ha señalado en otros comentarios, la inicial de los efectos de la reducción (o aumento) de la posibilidad de que el líder de la compra de las cervezas deben casi han desaparecido por la $2009$th paso.

Answer 2

Intuitivamente, después de sólo un par de mensajes que les olvida de donde empezamos. En ese caso, cada persona tiene la misma oportunidad de recibir el $n$th mensaje, por lo que la posibilidad de que el líder de la compra de la cerveza es $1/115$. Para demostrar explícitamente un camino que puede recorrer un ciclo de todos los $115$ personas $17$ a veces, ir a través de $53$ puntos del ciclo siguiente y atrás de la cabeza.

Por otro lado, es razonable suponer que todo el mundo en el equipo quiere que el plomo a comprar la cerveza. Cuando el conductor envía un texto, la siguiente persona puede volver así que envía a alguien. Esa persona puede etiquetar el plomo, por lo que el plomo recibe cada otro mensaje. Como $2008$ es, incluso, el plomo se obtiene el $2008$th uno y elige a la víctima con el $2009$th.