Media y mediana en un clásico río cruzando el problema

Question

Considere el siguiente problema clásico:

Cuatro personas en el lado oeste del río que se desea utilizar su barco para llegar a la east side de un río. Cada viaje en barco puede contener un máximo de dos personas, y el tiempo que se tarda en llegar será el momento preferido por el más lento de los ocupantes. El tiempo preferencias son: $1, 2, 5$ $10$ minutos. ¿Cuál es la mínima cantidad de tiempo en el que usted puede conseguir cuatro personas de todo el río, donde una hacia el este de viaje debe tener dos ocupantes y un viaje hacia el oeste debe tener uno de los ocupantes?

Respuesta: $17$ minutos. (A pesar de que muchos creen erróneamente que es es $19$ minutos).

Pregunta 1: Si usted mira todas las maneras posibles de llevar a estas cuatro personas de todo el río, sujeta a las restricciones anteriores, ¿cuál sería el promedio (media y mediana) veces?

Pregunta 2: ¿Qué pasa si usted reemplace el tiempo preferencias de los con $x_1, x_2, x_3$ $x_4$ minutos?

Pregunta 3: ¿Qué hacer si tiene tiempo preferencias de $x_1, \ldots, x_n$ minutos $n$ de personas, respectivamente?

Probablemente la forma más fácil de abordar la Pregunta 1 sería escribir un rápido programa para el cálculo de la respuesta, y tal vez haciendo esto por varias de tiempo diferentes preferencias daría una idea de la media y la mediana en el general de cuatro caso de persona. No estoy muy seguro de cómo iba a empezar a pensar en la general $n$ caso de persona; tal vez por la solución de $n = 1, 2, 3, 4$.

Respuestas (incluso parcial) a cualquiera o a todas mis preguntas sería muy apreciada!

Answer 1

Hay $N!(N-1)!^2/2^{N-1}$ diferentes horarios. El promedio para el tipo de problema ya ha sido calculado en carlop la respuesta. Sospecho que el cálculo de la mediana para el tipo de problema en la forma cerrada es intratable. Aquí está el código que comprueba que el promedio de $30$ y determina la mediana. El tiempo que toma para que el horario justo por debajo de la media es $27$, el tiempo que toma para que el horario justo por encima de la media es $30$. De acuerdo a la definición habitual de la mediana de un número par de números como la media de los dos centrales, la mediana es, por tanto,$28\frac12$.

Answer 2

El uso de @EuYu idea de que la fijación de un solo viaje (por ejemplo. el tercer viaje) cada subconjunto de la derecha de la cardinalidad tienen la misma probabilidad, se puede escribir el promedio de atravesar el tiempo como: $$E[time] = E[one person trip] * N[one person trip] + E[two person trip] * N[one person trip]$$ y sabes que: $$N[one person trip]=N-2$$ $$E[one person trip]=\frac{\sum_i x_i}{N}$$ $$N[two person trip]=N-1$$ $$E[two person trip]=\frac{\sum_{i,j} min(x_i,x_j)}{N*(N-1)/2}=\frac{\sum_i(x_i*(i-1))}{N*(N-1)/2}$$

Por ejemplo, para el caso de $N=4$$x_i=1,2,5,10$, usted tiene 2 una persona que viaje con un tiempo medio de $(1+2+5+10)/4=18/4=4.5$, 3 de dos persona que viaje con una media de $(1*0+2*1+5*2+10*3)/(4*3/2)=42/6=7$ para un total de tiempo de espera de $2*4.5+3*7=30$.

Este método funciona para la media, para otros la estadística (como la mediana), yo creo que un enfoque computacional debe ser utilizado.