Cuántas estrategias existen para este juego en el que uno de n lógicos, debe llamar a su propio sombrero de color de entre los n?

Question

$n$ lógicos son los sombreros que pueden ser de $n$ diferentes colores. Cada lógico puede ver los colores de todos los sombreros excepto la suya propia. Los lógicos al mismo tiempo debe llamar a un color; ellos ganan si al menos uno llama el color de su propio sombrero.

Matemáticamente, una estrategia es un elemento de $(C^{n-1} \to C)^n$ donde $C$ es el conjunto de colores de sombrero ($\mathrm{card}(C) = n$); una estrategia de $(d_0,\ldots,d_{n-1})$ está dada por los procedimientos de toma de decisiones de cada lógico, donde lgica $k$ dice $d_k(h_0, \ldots, h_{k-1}, h_{k+1}, \ldots, h_{n-1})$ cuando el sombrero de colores se $(h_0, \ldots, h_{n-1})$.

Una estrategia ganadora para este clásico del rompecabezas es

tener contados los lógicos y los colores, cada lógico llama el color que es su propio número menos la suma de los colores de sombrero que él ve (todos modulo $n$). Entonces quien tiene el número correspondiente a la suma de los colores está llamando fuera de su propio sombrero.

Esta no es la única solución. (Sugerencia: el caso de $n=2$ es fácil. Ahora concentrarse en $n=4$ y tratar de reducir al caso anterior.)

Usted puede reformular la estrategia anterior de la siguiente forma: vamos a $h_0, \ldots, h_{n-1}$ ser el sombrero de colores de los lógicos $0, \ldots, n-1$; lgica $k$ llama el valor de $h_k$ que hace que la ecuación de $h_0 + \ldots + h_{n-1} = k$ cierto. Más en general, dotar el conjunto de colores $C = \{c_0, \ldots, c_{n-1}\}$ con cualquier estructura de grupo $(C, *)$, y asignar a cada uno lógico de un único color $\ell_k$; a continuación, una estrategia ganadora para cada lgica $k$ a resolver la ecuación de $h_0 * h_1 * \ldots * h_{n-1} = \ell_k$ $h_k$ y de llamar a la solución. Por ello, toda la estructura de grupo conduce a una estrategia ganadora.

Son las estrategias presentadas anteriormente son todos los que hay? Si no, hay una manera razonable para describir la colección de todas las estrategias ganadoras, como la relativa a otro conocido estructura matemática? Por ejemplo, ¿cuántos distintas estrategias que existen para que un determinado $n$?

Answer 1

He aquí una respuesta parcial: No, estas no son las únicas estrategias. Para$n=3$, $10752$ estrategias diferentes, sólo $24$ de los que se presentan en la manera que usted describe. (Vamos a llamarlos "estrategias de producto".)

En primer lugar, para el recuento de las estrategias de producto, podemos hacer uso del hecho de que sólo hay un grupo con tres elementos es abelian. Por lo tanto el orden en el que el producto es irrelevante, y las cosas sólo pueden elegir son las $l_k$ y los tres bijections entre los colores y los elementos de grupo para cada lógico. Que hace cuatro opciones con $3!$ posibilidades de cada uno, pero muchos de ellos conducen a las mismas estrategias. Para ver esto, observe que las permutaciones de los restos modulo $3$ todo puede ser escrito como $r\to\sigma r+t$$\sigma=\pm1$. El aditivo constantes $t$ de todas las cuatro opciones pueden ser montados en una sola, por lo que sólo tenemos una constante aditiva (tres valores posibles) y cuatro signos. Sin embargo, podemos multiplicar toda la ecuación por $-1$, lo que deja sólo tres signos independientes, con dos posibles valores de cada uno, para un total $3\cdot2^3=24$ de posibilidades. Esto es confirmado por un equipo de búsqueda.

A continuación doy una lista de un programa que busca todas las estrategias para $n=3$. Encuentra $10752=2^9\cdot3\cdot7$ de ellos. Aquí está uno que no es un producto de la estrategia:

$$ \begin{array}{c|ccccccccc} &00&01&02&10&11&12&20&21&22\\\hline d_0&0&0&1&0&1&2&1&2&2\\ d_1&2&1&2&0&2&1&0&1&0\\ d_2&2&2&1&1&0&2&1&0&0\\ \end{array} $$

You can check that it's a strategy by going through the $3^3$ cases, and you can see it's not a product strategy because a product strategy couldn't have $d_0(0,0)=d_0(0,1)=0$.

Some interesting facts that may point towards a solution: For $n=3$, there is no individual choice left in any of the strategies; that is, for any two individual strategies $d_0$ and $d_1$ there is never more than one strategy $d_2$ to complete them. Also, for $n=3$ in each strategy each player guesses each colour for the same number of combinations. And generally (not just for $n=3$) only one player guesses correctly for each combination; this follows because the expectation value of a correct guess is $1/n$, así que si no eran combinaciones con más de una respuesta correcta tendría que ser una que no acierto. Todo esto puede apuntar a un poco de magia-cuadrado-como la descripción de las soluciones.

Aquí está el código:

import java.util.Set;
import java.util.HashSet;

public class Hats {
    final static int n = 3;
    final static int UNKNOWN = -1;
    static int [] [] [] strategy = new int [n] [n] [n]; // [player] [first hat seen] [second hat seen]

    static int [] [] permutations = {
        {0,1,2},
        {0,2,1},
        {1,2,0},
        {1,0,2},
        {2,0,1},
        {2,1,0}
    };

    static int [] [] inversePermutations = new int [6] [3];

    static {
        for (int i = 0;i < 6;i++)
            for (int j = 0;j < 3;j++)
                inversePermutations [i] [permutations [i] [j]] = j;
    }

    static Set<Integer> productStrategies = new HashSet<Integer> ();

    public static void main (String [] args) {
        // generate all product strategies
        int [] p = new int [3];
        for (p [0] = 0;p [0] < 6;p [0]++)
            for (p [1] = 0;p [1] < 6;p [1]++)
                for (p [2] = 0;p [2] < 6;p [2]++)
                    for (int g = 0;g < 6;g++) {
                        for (int player = 0;player < 2;player++)
                            for (int first = 0;first < 3;first++)
                                for (int second = 0;second < 3;second++)
                                    strategy [player] [first] [second] =
                                        inversePermutations [p [player]]
                                        [(permutations [g] [player] -
                                          permutations [p [(player + 1) % 3]] [first] -
                                          permutations [p [(player + 2) % 3]] [second] + 9) % 3];

                        productStrategies.add (getCode ());
                        if (!isCorrect ())
                            throw new Error ();
                    }

        System.out.println ("Found " + productStrategies.size () + " different product strategies");

        // generate all strategies
        recurse (0);

        System.out.println ("Found " + count + " different strategies in all");
    }

    final static int [] colours = new int [n];
    static int count;
    static int total;

    // returns a unique integer code for the strategies of the first two players
    static int getCode () {
        int result = 0;
        for (int player = 0;player < 2;player++)
            for (int first = 0;first < 3;first++)
                for (int second = 0;second < 3;second++)
                    result = 3 * result + strategy [player] [first] [second];
        return result;
    }

    // checks whether the strategies of the first two players allow for a strategy of the third player
    // returns true if there is one strategy, false for none, throws an error if there is more than one
    static boolean isCorrect () {
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                strategy [2] [i] [j] = UNKNOWN;

        // for each combination of hat colours, check whether one of the first two players guesses correctly;
        // if not, this fixes a value in the third player's strategy
        for (colours [0] = 0;colours [0] < n;colours [0]++)
            for (colours [1] = 0;colours [1] < n;colours [1]++)
                for (colours [2] = 0;colours [2] < n;colours [2]++) {
                    if (strategy [0] [colours [1]] [colours [2]] != colours [0] &&
                        strategy [1] [colours [2]] [colours [0]] != colours [1]) {
                        // neither of the first two players guesses this combination correctly
                        int s = strategy [2] [colours [0]] [colours [1]];
                        int s0 = colours [2];
                        if (s == UNKNOWN)
                            // fix the third player's strategy in this case
                            strategy [2] [colours [0]] [colours [1]] = s0;
                        else if (s != s0)
                            // or conclude that there is no strategy if it was already otherwise determined
                            return false;
                    }
                }

        // check that there's only one strategy left for the third player
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                if (strategy [2] [i] [j] == UNKNOWN)
                    throw new Error ();

        return true;
    }

    static boolean first = true;

    // generate all 3^18 combinations of strategies for the first two players
    static void recurse (int depth) {
        if (depth == (n - 1) * n * n) {
            if (isCorrect ()) {
                // this combination allows for a successful strategy of the third player -- count it...
                count++;
                if (first && !productStrategies.contains (getCode ())) {
                    // and if it's the first non-product strategy, print it as a TeX array
                    System.out.println ("non-product strategy:");
                    for (int player = 0;player < 3;player++) {
                        for (int first = 0;first < 3;first++)
                            for (int second = 0;second < 3;second++)
                                // internally first and second are cyclic; for output the order is reversed for the second player
                                System.out.print ("&" + strategy [player] [player == 1 ? second : first] [player == 1 ? first : second]);
                        System.out.println ("\\\\");
                    }
                    first = false;
                }
            }
        }
        else {
            int player = depth / (n * n);
            int first = (depth / n) % n;
            int second = depth % n;
            for (int guess = 0;guess < n;guess++) {
                strategy [player] [first] [second] = guess;
                recurse (depth + 1);
            }
        }
    }
}