Cómo formalmente el modelo de la "vacilación" en el sombrero de adivinanzas de puzzle?

Question

Hua Luogeng (en Chino, 华罗庚) hizo un hat-adivinar rompecabezas como una ilustración en un folleto centrándose en la inducción matemática. La siguiente descripción es una traducción literal del Chino.

Hat-Adivinar Rompecabezas: Un profesor quiere identificar a la mayoría de los más inteligentes de uno de sus tres estudiantes por los métodos siguientes: 5 sombreros se muestra, en la que 3 de ellos son de color blanco y los otros dos son de color negro, a los tres estudiantes. Con los ojos cerrados, cada estudiante se pone en un white hat, mientras que los otros dos negros están ocultos. Una vez que los permisos de apertura de los ojos se conceden, los tres estudiantes que abran sus ojos a la vez y se pueden ver los sombreros de los demás sin ningún tipo de comunicación. Después de una vacilación, dicen que "el sombrero en mi propio sombrero es blanco" con una sola voz. La pregunta es ¿cómo lo hacen?

El rompecabezas puede ser fácilmente generalizado para la versión con $n$ personas $n-1$ sombreros negros, y $\ge n$ sombreros blancos y ser resueltos por inducción en $n$:

Demostrar por inducción sobre $n$:

• Al $n$ es 2, la situación es trivial debido a que sólo hay un sombrero negro. Si yo estoy usando el negro, la otra persona puede decir que el sombrero sobre su cabeza es de color blanco, sin ninguna duda. Sin embargo, él no dudó. Contradicción.
• Supongamos que hemos resuelto el rompecabezas de la con $n = k$.
• Al $n = k + 1$, la razón va de la siguiente manera: Si alguien está usando el sombrero negro, el resto de la gente va a saber que y el problema se reduce a una versión con $k$ persona $k-1$ sombreros negros y $\ge k+1$ sombreros blancos. De acuerdo a la hipótesis inductiva, el $k$ de personas debe decir que el sombrero sobre sus cabezas son todos en blanco, sin ninguna duda. Contradicción.

Mientras tanto el rompecabezas y la prueba de sonido muy simple, estoy muy confundido con el sector informal de la palabra clave "vacilación" en ellos. Yo aún no puede decir la vaguedad de vacilación claramente. Por ejemplo, es la vacilación en sí mismo un objeto adecuado que puede ser utilizado en la inducción matemática? Informalmente, mi problema puede enunciarse de la siguiente manera.

Mi Problema: Cómo formalmente el modelo de la vacilación en el sombrero de adivinanzas de puzzle?

Gracias por cualquier sugerencia.

Answer 1

El rompecabezas es anterior a su mathmaical formalizaciones y una versión cates remonta a los años cincuenta. La forma más común para modelo de tal situación es el uso de la partitional modelo introducido por Robert Aumann. Hay un conjunto finito (puede ser algo generalizado) $\Omega$ de los estados. Un estado que describe todo lo relevante que podría ser el caso. En el rompecabezas, un estado podría describir que lleva lo del sombrero, por lo que hay siete estados $$\Omega=\{www,wwb,wbw,bww,bbw,bwb,wbb\},$$ where for example $smlm$ stands for kid $1$ wearing a white hat, kid $2$ wearing a black hat, and kid $3$ wearing a white hat. Now we have to model what the kids know. We do this the following way: A person is able to different between certain states, but not others. We model this by that person having a partition of $\Omega$ and the person gets informed in which element in the partition the true state lies but not the precise state. In the puzzle, a kid is unable to differentiat states in which everyone else wears the same hat. For example, kid $2$ has the partition $$P_2=\big\{\{www,wbw\}, \{bww,bbw\},\{wwb,wbb\},\{bwb\}\big\}.$$

Tenga en cuenta que kid $2$ conoce el color de su sombrero, sólo si el verdadero estado es $bwb$. Kid $1$ sabe si el verdadero estado es $wbb$ y el cabrito $3$ sabe que si se es $bbw$. En general, vamos a $P_i$ de la información de la partición de una persona $i$. Si el verdadero estado es $\omega$, dejamos $P_i(\omega)$ a ser el elemento de la partición que contiene a $\omega$ y lo interpretamos como el conjunto de los estados $i$ considera posible. Un evento es simplemente un conjunto de estados. Decimos que $i$ conoce el caso de $E$ estado $\omega$ si $P_i(\omega)\subseteq E$. Dejamos $K_i(E)$ el conjunto de los estados en que $i$ conoce $E$. Tenga en cuenta que $K_i(E)$ es un evento en sí mismo. Así, uno puede escribir cosas como $K_1(K_2(K_1(E)))$, que puede ser interpretado como $1$ saber que $2$ sabe que $1$ conoce $E$.

Ahora en el rompecabezas, el verdadero estado es $www$. Pero un niño al ver a dos sombreros blancos no contarle nada sobre el color de su propio sombrero. Nadie sabe el color de su sombrero, de lo contrario, ella diría. En el caso de que nadie sabe el color de su sombrero es $$E=\{www,wwb,wbw,bww\},$$ which is exactly the set of states at which no two kids wear a black hat. Everyone knows this and gets therefore a new partition in which this knowlege is incorporated. For example, $$P_2'=\big\{\{www,wbw\}, \{bww\},\{bbw\},\{wwb\},\{wbb\},\{bwb\}\big\}.$$ Formally, this is the coarsest partition that is at least as fine as the two partitions $P_2$ and $\{E,E^C\}$ and this is how e model learning. Even with this partition, no kid knows the color of her hat. Everyone knows this, and this allows her to deduce that the state is not on in which the other two kids have white heads and she has black hats, for the other kids could then deduce that they have white hats and they did not. From this, every kid can deduce that the true state is $www$, or more formally $P"_i(www)=\{www\}$ for $i=1,2,3$, por lo que este se convierte en una declaración formal.

Una encuesta de este tipo de modelado ha sido escrito por John Geanakoplos para el Manual de la Teoría de juegos y Económico Applcations. La encuesta se puede encontrar aquí. También se explica esencialmente el mismo rompecabezas. El artículo es un poco técnico, y un poco simplificada de la versión se puede encontrar aquí.

Answer 2

Las variaciones de esta pregunta que he visto se dividen en dos tipos:

• El tiempo es muy atentamente cuantificada (por ejemplo, cada día al mediodía se reúnen para decir algo, si es posible), por lo que es posible hacer inferencias del tipo "Nadie dijo nada durante la última unidad de tiempo".
• El conocimiento de que la otra gente no podía decir nada, con el conocimiento que de inmediato se da es todo lo que uno necesita, por lo que uno puede esperar pacientemente el tiempo suficiente para que cualquier persona razonable habría dado una respuesta si se podría obtener esa información.

La pregunta que has estado, yo creo, es un mal (al menos según la traducción). Duda es, como usted ha dicho, demasiado vaga; sin el conocimiento de la rapidez con la que otras personas pueden hacer deducciones (y el conocimiento de la rapidez con la que ellos piensan que usted puede hacer deducciones, etcétera), se hace difícil o imposible de hacer con fiabilidad el número de personas crece.

Answer 3

Este tipo de preguntas se analizarán en la teoría de los juegos/microeconomía y normalmente se basan en la probabilidad filtraciones (discreta o continua en el tiempo la información de la actualización) o algebraicas métodos topológicos. La duda, como sugiere el comentario anterior, se actualiza la información a lo largo del tiempo; y es el resultado de la inacción de una información que habría llevado a la acción. Esto es sorprendentemente difícil, pero el análisis de un problema similar hizo alguien de mi escuela, su año en el mercado de trabajo de la superestrella (Sherlock Holmes - el Dr. Moriarity rompecabezas, el uso de jerarquías de creencias)

Esto no es verdaderamente útil para ayudarle a ver cómo el modelo de su problema en particular. Pero usted parece estar realmente interesado en comprender esto mejor, y buscando en google alguna de las anteriores palabras clave (también Repetidos Juegos; Racionalidad vinculada) debería ayudar.

P. S.: El embarrado niños problema, dicen, podría probablemente ser modelado mediante jerarquías de las creencias, que son secuencias de razonamiento "x", "yo sé que usted sabe x", "Usted sabe que yo sé que usted sabe x"...., que luego (a menudo) se examinaron para fijar puntos.

Answer 4

Sugerencia en relación con la $\textbf{hesitation}$: El motivo manifiesto de la vacilación es que cada uno está esperando a ver si uno de los otros sabe el color. Así que me gustaría interpretar el rompecabezas como diciendo que si cualquiera de los dos no sabe el color de sus propios sombreros, luego el tercero, el sombrero es de color blanco. Esta versión del puzzle, con el cuantificador "si cualquiera de los dos no" cambia a", existen dos que no", que aparece en la web

http://mathforum.org/library/drmath/view/55638.html

Un no-frills versión de la misma es como sigue.

Tres personas a, B y C están sentados de manera que cada uno sólo puede ver a los otros dos. Ellos saben que un negro sombrero o una gorra blanca serán colocados en cada uno de la cabeza, mientras que todos cierran sus ojos, y que los tres sombreros no todo es de color negro. Después de los sombreros se colocan sobre sus cabezas, ellos están autorizados a abrir sus ojos y a cada uno se le pedirá el color de su propio sombrero (mirando sólo a los otros dos), pero C, B, siguiente y último. Cuando C abre sus ojos, él admite que él no sabe. Entonces B abre sus ojos y también dice que no sabe. A continuación, Un anuncia el color de su sombrero correctamente sin siquiera abrir los ojos.

Pregunta por el enigma: ¿Cuál es el color de Un sombrero?

Este rompecabezas se puede resolver para obtener la respuesta "blanco", permitiendo a los cuatro posibilidades para B y C. El cuantificador "dos" hace que la situación simétrica y de ello se desprende que los tres sombreros tienen que ser de color blanco. Me imagino que el puzzle en el folleto de Hua Luogeng por lo tanto es un corolario de la versión citada por encima de la mathforum sitio web.

$\textbf{MY QUESTION:}$ Es la siguiente una correcta interpretación matemática de la situación en el rompecabezas que se describe aquí? Hay uno mejor?

Terminología: Para una clase dada ℱ de funciones de un conjunto $X$ a un conjunto $Y$, diremos que una función de la clase se determina dentro de ℱ por (un subconjunto) $S \subseteq$ $X$ si es la única función de la clase de ℱ que está de acuerdo con que en el subconjunto $S$.

Reclamo: Considerar la clase de ℱ de funciones de un conjunto de tres elementos $X$ = $\{A,B,C\}$ a un conjunto de dos elementos $\{b,w\}$ tales que el rango no es de $\{b\}$. En esta clase (que contiene 7 funciones), no es una subclase $\mathscr G$ de las funciones (solo queda 1) que están determinados dentro de ℱ por el subconjunto $S$ = $\{A,B\}$ de $X$. En el complemento de la clase ℋ de funciones no $\mathscr G$ (hay 6 de ellos), no es una subclase de funciones (2 de ellos) que están determinados dentro de ℋ por $\{A,C\}$. En la subclase de las funciones del resto de las funciones (4 de ellos), cada uno se toma el valor de $w$ en el punto de $A$.

La PRUEBA de la Demanda: Para las siete funciones en ℱ, los respectivos valores en $A,B,C$ puede ser tabulados a continuación.

$$ \{b,w,b\}, \{b,b,w\}, \{b,w,w\}, \{w,w,b\}, \{w,b,w\}, \{w,b,b\}, \{w,w,w\}. $$

La segunda función de las formas de la subclase $\mathscr G$, cada uno de los cuales se determina dentro de ℱ por $\{A,B\}$. La primera y la tercera forma de una subclase ℐ en el complemento de la clase ℋ = ℱ∖$\mathscr G$, de 6 de funciones, cada una de las cuales se determina dentro de ℋ por $\{A,C\}$. En el complemento de la clase ℋ∖ℐ, que consta de los cuatro restantes funciones y están catalogados como cuarta a séptima, cada uno se toma el valor de$w$$A$.

Answer 5

Fragmentar el tiempo que elimina la necesidad de modelo de vacilación, como otros han dicho.

Acaba de dar a cada persona tres opciones: negro / blanco / no lo sé, y tengo dos rondas de respuestas. Abiertamente declarados < no sé > respuestas en la primera ronda de dar la información para las respuestas correctas en la segunda ronda.