A345257 Tiefenbruck sequence for the game of countably infinitely many hats.

-1, 1, 0, 0, 2, 1, 2, -1, 4, 1, 0, 0, 2, 1, 2, 4, 3, 1, 0, 0, 2, 1, 2, 3, 3, 1, 0, 0, 2, 1, 2, 3, 5, 1, 0, 0, 2, 1, 2, 5, 4, 1, 0, 0, 2, 1, 2, 4, 5, 1, 0, 0, 2, 1, 2, 5, -1, 1, 0, 0, 2, 1, 2, -1, 7, 1, 0, 0, 2, 1, 2, 7, 4, 1, 0, 0, 2, 1, 2, 4, 3, 1, 0, 0, 2, 1

Offset: 0

Author

Frederic Ruget, Jun 12 2021

Keywords

• sign

Comments

The Tiefenbruck sequence represents a strategy for the game of countably infinitely many hats. This strategy is conjectured to be one of several optimal strategies.

The rules of the game are as follows: two players each have countably infinitely many hats put on their heads. Each hat is either black or white with equal probability; furthermore, the players are only able to see the hats on the other player's head; simultaneously both players guess and point to a hat on their own head; they win if both pick out a white hat.

One would think that the maximum probability of winning the game is 1/4 -- and indeed the probability of winning is 25% if both players (e.g.) always choose the first hat on their own head. However, better results can be achieved if the players agree on a common strategy.

For example, if both players choose the position of the first black hat on the other player's head, then the probability of success is 1/3. Loosely speaking, this "first black hat" strategy corresponds to A007814 -- in a sense that will be made clearer later on.

Interestingly, choosing the position of the first white hat on the other player's head also results in a probability of success of 1/3. Loosely speaking, this "first white hat" strategy corresponds to A007814, with an added leading -1.

Actually it is possible to achieve a probability of success of 7/20 (35%) using the Tiefenbruck strategy described here, the Carter and Reyes strategy described in A345255, or variations thereof. Also it is an open problem whether strategies can achieve results better than 7/20.

The Tiefenbruck strategy is defined using a cellular automaton specified in the link "Infinitely Many Hats" below. The cellular automaton is fed with the sequence of hats on the other player's head, identifying each black hat with digit 0 and each white hat with digit 1. When (if) it completes, the automaton outputs the position of the hat the player should point to on their own head. Assuming a Baire/Borel measure for the universe of possible hat configurations, then the automaton almost always completes and the probability of success is indeed 7/20.

Now a(n) is defined as the output of the Tiefenbruck cellular automaton when fed with index n -- n being interpreted as the infinite stream of zeros and ones of its binary representation, starting from the least significant bit -- or as -1 if the automaton does not complete with the given infinite stream.

The "Towers of hats" and "Infinitely Many Hats" links below provide a formal exposition of the game of hats and a calculation of the probability of success.

Examples

			With n = 06567700 (octal notation), we have a(n) = 3 + 3 + 3 + 3 + 2 = 14.
		

Links

• Joe Buhler, Hat Problems, Numberphile Video.
• Frederic Ruget, Towers of hats.
• Frederic Ruget, Hats Calculator.
• Frederic Ruget, Infinitely Many Hats.
• Stan Wagon, An Infinitely Puzzling Hat Problem.

Crossrefs

Cf. A007814.

Cf. A345255.

Programs

JavaScript

// Tiefenbruck sequence for the game of countably infinitely many hats
function a(n) {
    let offset = 0;
    while (true) {
        if (n == 0) return -1;
        switch(n & 7) {
            case 1: return offset + 1;
            case 2: return offset + 0;
            case 3: return offset + 0;
            case 4: return offset + 2;
            case 5: return offset + 1;
            case 6: return offset + 2;
        }
        n >>= 3;
        offset += 3;
    }
}

Formula

[a(n): 0 <= n < 7] = [-1, 1, 0, 0, 2, 1, 2]

For n > 7:

if (n mod 8) in {1, 2, 3, 4, 5, 6}, then a(n) = a(n mod 8);

otherwise if a(floor(n/8)) = -1, then a(n) = -1;

otherwise a(n) = a(floor(n/8)) + 3.