El motociclista reto

Question

n caminantes ${A}_{i}$ ($i=1,2,...,n$) empezar de X a Y, simultáneamente, con velocidades constantes ${a}_{1}<{a}_{2}<...<{a}_{n}$. Al mismo tiempo, el motorista M con velocidad $m=1$ comienza desde Y para llevar a ellos, como se muestra a continuación:

El motociclista puede elegir para recoger un andador a la reunión. Él puede llevar a más de una persona, sino que es libre para dejar a la persona que la lleva en cualquier momento. Abandonados a sí mismos, los caminantes a pie hacia adelante (de X a Y) con las velocidades de $a_i$, mientras que el motociclista es libre para conducir, ya sea hacia delante o hacia atrás, con o sin carga.

El motorcylist del objetivo (reto!) es encontrar un plan en virtud del cual todos los caminantes llegan a Y simultáneamente, si ese plan existe. Llamamos un plan a, un plan factible, y llamar a la $({a}_{1},{a}_{2},...,{a}_{n})$ para que un posible plan de existe un factible de configuración. Para un n dado, definir el conjunto de todos los posibles configuraciones de conjunto factible ${B}_{n}$.

La pregunta: ¿Cuál es el conjunto factible ${B}_{n}$? O al menos, lo que es${B}_{4}$?

n=2 es trivial debido a que ${B}_{2}={\mathbb{R}}_{++}^{2}$. He trabajado fuera de la n=3 caso, para que ${B}^{3}=\{({a}_{1},{a}_{2},{a}_{3})| 2{a}_{2}\leq{a}_{1}+1,\ {a}_{3}<1 \}$. A pesar de la sencilla respuesta final, sin embargo, hay un montón de sutilezas, matices y debates en la necesidad de llenar en el proceso, lo que realmente me hace dudar de si realmente se puede caracterizar ${B}_{n}$ incluso moderadamente grande n.

---

Alternativamente, para un n dado, uno puede tratar de buscar una especie de dominante plan (o una regla,un conjunto de instrucciones para saber qué hacer, si así lo desea) para el motorista, en el sentido de que si este plan no funciona, no hay ningún otro plan. Si tenemos éxito en la búsqueda de uno, dado ningún tipo de configuración, podemos simplemente ingrese a un programa de ordenador que simula todo el proceso mediante el plan y ver el resultado. En resumen, podemos hacer la pregunta: "dada una configuración, decidir si es viable" una decidable uno. Para n=3, se puede demostrar que el siguiente es una estrategia dominante:

1) Después de la reunión ${A}_{3}$, unidad con él y abandonarlo en la posición x antes de la reunión de ${A}_{1}$, donde x es elegido tal que 2) se cumple:

2) Recoger ${A}_{1}$ y llevarlo hacia adelante para cumplir con ${A}_{2}$ en alguna posición y. x 1) es elegido tal que ${A}_{3}$ ahora acaba de llegar a la y, demasiado. Una configuración será factible iff y$\leq$el destino Y.

(Necesariamente, esto le da a la ${B}^{3}$ I se describió anteriormente, también)

---

De hecho, me ha publicado esto en MO cerca de la mitad de hace un año y nadie se ha dado una definición de respuesta: http://mathoverflow.net/questions/72449/the-motorcyclists-challenge. También me pregunto si algo puede decirse acerca de ${B}_{n}$ para la gran n? Las especulaciones son apreciados, también.

Answer 1

Considere la posibilidad de una versión más fácil del problema, en los que los caminantes están en una prisa rumbo Y, por lo que no permitirá M, para llevarlos hacia atrás. Claramente, si $({a}_{1},{a}_{2},...,{a}_{n})$ es factible, a continuación, $({b}_{1},{b}_{2},...,{b}_{n})\leq({a}_{1},{a}_{2},...,{a}_{n})$ también será factible. Por lo tanto, sólo es necesario considerar el "límites".

Definición: $({a}_{1},{a}_{2},...,{a}_{n})$ es un límite de configuración (BC) si la única viable $({b}_{1},{b}_{2},...,{b}_{n})\geq({a}_{1},{a}_{2},...,{a}_{n})$ $({a}_{1},{a}_{2},...,{a}_{n})$ sí.

La solución depende esencialmente de la siguiente afirmación:

Reclamo: En un posible plan para BC, M puede nunca conducir hacia adelante con un vacío asiento trasero.

Por qué? Posiblemente en este caso, la mejor M puede hacer es intentar sucesivamente de la unidad más lenta caminantes hacia adelante lo suficiente como para corregir posiciones. Cuando walker se cae, M inmediatamente vuelve a elegir otra, de modo que todos los demás caminantes llegar Y al mismo tiempo tan M llega con su último llevar.(Aunque yo creo que es probablemente cierto, esto no es prueba de la reclamación. Más evidencia a favor o en contra es de agradecer)

La observación crucial es que si la demanda es verdad, luego de exactamente la mitad del tiempo M es descargado y va hacia atrás, y se carga y se va a seguir para el resto de la mitad. (Porque él comienza a partir de y, y finalmente regresa a Y, con desplazamiento cero)

Tenga en cuenta que la distancia entre X y y es irrelevante para nuestro propósito. Para mayor comodidad, vamos a ser $1$. Deje $T$ el total de lapso de tiempo, ${t}_{i}$ ser la longitud de tiempo que walker $i$ es en la motocicleta. Por la observación hecha anteriormente, tenemos:

$\sum_{i}{t}_{i}=T/2$

${t}_{i}+a_i(T-{t}_{i})=1$ $i=1,2,...,n$

Lo que da:

$T=\sum_i1/(1-a_i)/(1/2+\sum_i\frac{a_i}{1-a_i})$

$t_i=(1-{a}_{i}T)/(1-a_i)$

Observe que, curiosamente, el total de lapso de tiempo es independiente de M la decisión acerca de la selección de la orden. Para garantizar que el $({a}_{1},{a}_{2},...,{a}_{n})$ es de hecho posible, necesitamos $t_i\geq 0$ todos los $i$, lo que significa que $a_i\leq 1/T$, lo que significa que $a_n=1/T$ (ya que estamos en el límite, y la $a_n$ es el más grande). Por lo tanto $a_n\leq 1/\sum_i1/(1-a_i)/(1/2+\sum_i\frac{a_i}{1-a_i})$, lo que caracteriza a la $B_n$ deseamos para $n\geq 2$.