La división de un sandwich y no se siente engañado

Question

Este es un problema que me ha perseguido durante más de una década. No todo el tiempo - pero de vez en cuando, y siempre en el tiempo ventoso o los días de lluvia, de repente vuelve a aparecer en mi mente, me mira fijamente durante media hora a una hora y, a continuación, sólo sonríe a mí, y susurra todo el día: "Usted no va a resolver mí..."

Por favor, sálvame de esta torturador.

Aquí está:

Digamos que hay dos personas y un sándwich. Ellos quieren compartir el bocadillo, pero no confiar el uno en el otro. Sin embargo, encontraron la manera en la que ambos de ellos tendrá un almuerzo sin sentirse engañado: Uno de ellos va a cortar el sándwich en dos mitades, y el otro va a elegir a los cuales la mitad será de él. Justo, derecho?

El problema es:

Existe el mecanismo para tres personas y un sándwich?

---

EDIT: Esto fue en la montaña rusa para mí. Ahora, resulta que hay al menos dos libros dedicados exclusivamente sobre este problema y sus variaciones:

Feria De La División De

Corte De La Torta De Algoritmos

---

Ayer estuve en una tienda de café, en una pequeña empresa. Pedimos café y algunas pastas de chocolate. Como yo estaba cortando mi pastel para mi primer bocado, me sentía el sudor en mi frente. Algunos de mis amigos solo me interrumpe y dice: ¡basta! Usted no es el corte de la torta de una manera justa! Mis manos empezó a temblar de miedo de que. Pero no, no pasó nada. Afortunadamente.

Answer 1

Durante más de dos, el movimiento de un cuchillo es una buena solución. Alguien toma un cuchillo y se mueve lentamente a través del sándwich. Cualquier jugador puede decir "corte". En ese momento, el bocadillo es de corte y la pieza dada para el que dijo que "cortar". Como él ha dicho que es un aceptable pieza, él cree que él tiene por lo menos $\frac 1n$ del sándwich. El resto han afirmado (por no decir "corte") que es en la mayoría de los $\frac 1n$ del sándwich, por lo que el promedio disponible ahora, al menos de su parte. Recurse.

Answer 2

Sólo para que conste, aquí está el Selfridge–Conway discretos procedimiento mencionado en los comentarios. El artículo de la Wikipedia también contiene algunos comentarios sobre su origen y por qué funciona.

Este procedimiento fue el primer envidia libre discretos procedimiento ideado para tres jugadores. El número máximo de las cortes en el procedimiento es de cinco. Las piezas no siempre son contiguos. Soluciones para n jugadores también fueron encontrados más tarde.

Supongamos que tenemos tres jugadores P1, P2 y P3. Donde el procedimiento da un criterio para tomar una decisión significa que el criterio da un elección óptima para el jugador.

Paso 1. P1 divide la torta en tres piezas que él considera de igual tamaño.

Paso 2. Vamos a llamar a Una de las más grandes de la pieza de acuerdo a P2.

Paso 3. P2 corta un poco de Una a hacer el mismo tamaño como el segundo más grande. Ahora se divide en:

• recorte la pieza A1
• los adornos A2.

Dejar los adornos A2 a un lado. Si P2 piensa que el más grande de dos partes son iguales, entonces cada jugador elige una parte en este orden: P3, P2 y finalmente P1.

Paso 4. P3 elige una pieza entre A1 y las otras dos piezas.

Paso 5. P2 elige una pieza con la limitación de que si P3 no elegir A1, P2 debe elegir.

Paso 6. P1 elige la última pieza, dejando los recortes de A2 a ser dividido.

Ahora, el pastel de menos los adornos A2 ha sido dividido en una envidia manera libre. Recorte la pieza A1 ha sido elegido por P2 o P3. Vamos a llamar el jugador que eligió la PA y el otro Jugador PB.

Paso 7. PB cortes A2 en tres pedazos iguales.

Paso 8. PA escoge un trozo de A2 - tenemos que nombrar A2₁.

Paso 9. P1 escoge un trozo de A2 - tenemos que nombrar A2₂.

Paso 10. PB elige la última pieza restante de la A2 - tenemos que nombrar A2₃.

La Wikipedia sobre los orígenes de este procedimiento:

Este procedimiento es llamado después de que Juan Selfridge y John Horton Conway. Selfridge descubrió en 1960, y le dijo a Richard, quien dijo para muchas personas, pero Selfridge no publicarlo. John Conway lo descubrió de forma independiente en 1993, y además nunca se publicó, pero el resultado es que se les atribuyen en una serie de libros.

Answer 3

Para dividir un pastel a $n$ a la gente, no es un algoritmo que garantiza que:

• Cada uno de los $n$ la gente se lleva una pieza que él considera, al menos, tan buena como la de cada una de las otras piezas (es decir, la división es la envidia libre);
• Todas las piezas están conectadas (en realidad, todas las piezas son rectángulos).

Este algoritmo fue inventado por el Bosque Simmons y publicado por Francisco de la Ub en 1999.

El único problema con este algoritmo es que su tiempo de ejecución no es acotada, es decir, se podría tomar para siempre (Como lo demuestran Stromquist en 2008, no delimitada algoritmo puede encontrar una envidia libre de la división cuando queremos que las piezas a unir).

Pero, usted puede parar en cualquier momento y obtener una división que es aproximadamente la envidia libre.

Answer 4

Aquí está una variación en la aceptación de la respuesta.

A cuts the sandwich into 3 parts
If B thinks the top 2 pieces are equal
  C chooses a piece
  B chooses a piece
  A gets the remaining piece
Else
  B re-balances the 2 biggest pieces.
  C chooses a piece
  If only one of B's re-balanced pieces remain
    B gets that piece
    A gets the remaining piece
  else
    A chooses a piece
    B gets the remaining piece

Resumen:

• Un obtendrá uno de sus "iguales" piezas o más, y es por lo tanto feliz.
• B que es una de las piezas que se ajustan, y así son felices.
• C va a conseguir la primera opción, y es por lo tanto feliz.
• Aunque cada persona debe obtener al menos un tercio en su mente, esto no califica como una envidia solución libre. Por ejemplo, si B re-equilibra dos piezas y C elige la pieza B se ha incrementado, a continuación, Una sería la envidia de C porque tiene a más de 1/3 de la mente. Sin embargo, todavía hace 1/3 en su mente.

Creo que se puede generalizar este patrón de $N$ de la gente. Simplificado, renunciar a su lugar en el picking pedido, en caso de equilibrar, pero la desventaja es que usted está garantizado para conseguir una pieza de reajuste o uno más grande. He aquí una primera toma a las reglas de prioridad para la cosecha procedimiento, aunque no estoy seguro de que maneja todos los casos:

1. Si N personas tienen cada uno de N piezas que reequilibrado restantes, la primera persona que reequilibrado de la que el grupo obtiene para elegir sus reajuste de las piezas. Por ejemplo, si hay una pieza a la izquierda de las piezas que se re-equilibrado, se puede conseguir que la pieza.
2. Si no se re-equilibrio, el número más alto elige primero
3. Si usted hizo reequilibrar, el más bajo cortador elige primero

También, he aquí un ejemplo de cómo funcionaría para 4 personas:

A cuts the sandwich into 4 equal pieces
If B thinks the top 3 pieces are equal:
  If C thinks the top 2 pieces are equal:
    D chooses a piece
    C chooses a piece
    B chooses a piece
    A gets the last piece
  Else:
    C rebalances the top 2 pieces
    D chooses a piece
    If only one of C's rebalanced pieces remain:
      C gets the other rebalanced piece
      B chooses a piece
      A gets the last piece
    Else:
      B chooses a piece
      If only one of C's rebalanced pieces remain
        C gets the other rebalanced piece
        A gets the remaining piece
      Else
        A chooses
        C gets the remaining piece
Else:
  B rebalances the top 3 pieces
  If C thinks the top 2 pieces are equal:
    D chooses a piece
    C chooses a piece
    If only one of B's rebalanced pieces remain:
      B takes that piece
      A gets the final piece
    Else:
      A chooses a piece
      B gets the final piece
  Else:
    C rebalances the top 2 pieces
    D chooses a piece
    If only one of C's rebalanced pieces remain:
      C gets that piece
      If only one of B's rebalanced pieces remain:
        B gets that piece
        A gets the last piece
      Else:
        A chooses a piece
        B gets the other piece
    Else if only 2 pieces rebalanced by both C & B are left:
      B chooses one of the rebalanced pieces
      C gets the other one
      A gets the last piece
    Else:
      A chooses a piece
      If only one of C's rebalanced pieces remain:
        C gets that piece
        B gets the final piece
      Else:
        B gets to choose
        C gets the final piece

Answer 5

Bien, esto es solo un pequeño comentario acerca de la "ciencia" detrás de todos estos. Se puede entender un sándwich como una medida de espacio con $n$ determinadas medidas. Además, estas medidas no son atómicas, de lo contrario no se puede solucionar el problema incluso para dos personas. Estas medidas generan un vector de medida en el `sandwich". Ahora se puede aplicar el teorema de Lyapunov y decir, que el rango de esta medida es cerrado y convexo. Pero los puntos $(1,1,...,1)$ y $(0,0,...,0)$ se encuentran en el intervalo, por lo tanto el punto $(1/n,..., 1/n)$. Esto significa, que no hay un pedazo de sándwich de tal manera que cada persona piensa que es exactamente $1/$ n de todo el sándwich. Ahora usted puede dar a cualquier persona y repita el procedimiento. Lo bueno es que se dividen el sandwich de tal manera que cada persona va a pensar, que el sándwich se divide en partes iguales. Así que uno puede resolver el problema en el siguiente formulario "Hay una manera de dividir un sándwich de tal manera que cada persona piensa que nadie tiene más de sándwich de él". No tengo idea de cómo hacer un algoritmo explícito para que uno.