11 votos

Santa secreto problema

Decidimos hacer secret Santa en nuestra oficina. Y esto trajo un montón de problemas que nadie podía pensar en soluciones para el oso conmigo aquí.. esto es un problema importante.

Tenemos 4 personas en nuestra oficina - cada uno con una pareja que estará en nuestra comida de Navidad.

Steve, Christine, Marca, María, Ken, Ann, Pablo(me), Vicki

Resultado deseado

Nadie puede saber lo que está comprando un regalo para alguien más. Pero cada uno de nosotros quiero saber que estamos comprando nuestro presente para antes de ir a la Fiesta de navidad. Y no queremos ser la compra de regalos para nuestros socios. Los socios no están en la oficina.

La solución obvia es poner todos los nombres en el sombrero - ir alrededor de la oficina y roba dos cartas.

Y, sí, efectivamente me llamó a mí y a Mark sacó su pareja. (cambiamos)

Con esa información, yo podría trabajar que Steve tenía un 1/3 de probabilidad de tener Vicki(él no tenía a sí mismo o a Christine -, ni las dos cartas que había adquirido Ann o María) y yo sabía que la Marca fue la compra de mi presente. Inaceptable resultado.

Ken hizo la pregunta: "¿cuáles son las posibilidades de que vamos a recoger a nosotros mismos o a nuestra pareja?"

Así que tenía una puñalada en el trabajo que fuera.

Primera carta robada -> 2/8 Segunda carta -> 12/56

Añadiendo hace 28/56 es decir, 1/2.

es decir, Este método no siempre funciona... la mitad de posibilidades de dibujo de alguien que usted conoce significa que vamos a estar dibujando todo el año antes de obtener una solución que funciona.

Mi primer pensamiento fue que atribuimos dos cartas a nuestras espaldas... poner vendas en los ojos y tropezar en la oscuridad de acaparamiento de las primeras cartas que nos cruzamos... sin Embargo esto es un poco impráctico y estoy bastante seguro de que nos podemos acabar sabiendo que agarró lo que de todos modos.

¿Alguien tiene una solución para la distribución de las tarjetas que los resultados en nuestro resultado deseado?


Yo preferiría una solución sin un tercero..

5voto

lowglider Puntos 562

Si cada uno de ustedes simplemente dibuja un nombre al azar de el sombrero, la probabilidad de que nadie consigue su propio o de la pareja nombre es

$$\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%.$$

Por lo tanto, el número esperado de veces que tendrás que repetir el proceso antes de llegar a "una solución que funciona" es $280/33 \approx 8.5$. Este podría ser un poco tedioso, pero apenas tomar "todo el año", por lo menos hasta que los dos están muy lento y muy mala suerte con el sorteo.


Ps. Fui y calcula las probabilidades de los otros números de parejas:

  • $2$ parejas: $\frac{4}{24} = \frac{1}{6} \approx 16.7\%$ de probabilidad de nadie para su propio o de su pareja de nombre
  • $3$ parejas: $\frac{80}{720} = \frac{1}{9} \approx 11.1\%$
  • $4$ parejas: $\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%$
  • $5$ parejas: $\frac{440192}{3628800} = \frac{3439}{28350} \approx 12.1\%$
  • $6$ parejas: $\frac{59245120}{479001600} = \frac{16831}{136080} \approx 12.4\%$

Si no me equivoco, como el número de parejas que participan tiende a infinito, la probabilidad de nadie para su o su nombre del socio debe tender hacia el límite de $e^{-2} \approx 13.5\%$, y por lo tanto, la previsión del número de reintentos que se necesite debe tender a $e^2 \approx 7.4$.

3voto

Simon Puntos 3025

1) Usted podría tener una tercera parte de la manija de la distribución de las cartas en el sombrero, de modo que cada sorteo será válido.

Y después de cada sorteo de la tercera parte va a quitar no válido tarjetas y poner válido para el siguiente sorteo. Que debe suceder sin que ninguno de los participantes en el conocimiento de cuánto tarjetas que se colocan y quitan.

La desventaja es que usted tendrá que esa persona sabe (o al menos tener la información suficiente para deducir de él) sobre la que se basa la oms.

2) Otra solución sería si usted toma 8 tarjetas con cada nombre de las personas por un lado y, a continuación, cada pareja hace una única marca en el otro lado y se les pone en los sobres.

A continuación, se mezcla la envuelve, poner las cartas sobre la mesa única de la marca y todo el mundo se basa en la secuencia. De esta manera, se podría distinguir la opción inválida sin saber quién es quién.

3) Una modificación de la idea. El uso de tarjetas con los nombres, a continuación, cada pareja pone en la única caja marcada (o sobres) y, a continuación, en una caja más grande idéntica a las demás.

Entonces alguien coloca las cajas en una de las oficinas, abre las cajas grandes y elige una carta de una de las cajas pequeñas. Luego todo el mundo va en uno por uno.

Si nadie mira su propio cuadro de nadie sabe si él/ella fue atraída o no.

ACTUALIZACIÓN Hay una posibilidad de que este esquema se producirá un error si la última pareja tiene menos de 2 opciones válidas.

ACTUALIZACIÓN Si usted tiene a la gente entrar en la habitación de forma aleatoria y sin conocer el orden de la entrada que va a resolver el problema. Que se podría hacer (sin terceros) si usted tiene uno de los participantes elegir a las personas al azar para ir allí y, a continuación, tomar la última.

Este espero que funciona igual de necesarios. :)

En una Nota lateral : me iría a por el guión - es más fácil, pero la organización de todo lo anterior podría ser un montón de diversión para todos.

ACTUALIZAR Bien la miró fijamente la mirada de alguien que busca la forma en que va a ser la sugerencia de ningún algoritmo puede tratar.

1voto

albemuth Puntos 194

Ver este algoritmo aquí: http://weaving-stories.blogspot.co.uk/2013/08/how-to-do-secret-santa-so-that-no-one.html. Es un poco demasiado largo para incluir en un Intercambio de la Pila respuesta.

Esencialmente, se corrige la topología de ser un simple ciclo y, a continuación, una vez que tenemos un orden aleatorio de los participantes también podemos determinar que para conseguir un regalo para el.

0voto

PhirePhly Puntos 1343

Usted toma su propio nombre y sus socios nombre del sombrero. Usted, a continuación, dibuje una tarjeta con la que mantener. Mano el sombrero a su pareja. Que luego dibuja una tarjeta, que se mantienen. Ahora puedes poner tu tarjeta y sus socios de la tarjeta de nuevo el sombrero. Mano el sombrero a alguien más. Enjuague y repteat.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X