A345257 -id:A345257 - cp's OEIS frontend

A345255 Carter and Reyes sequence for the game of countably infinitely many hats.

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

Offset: 0

Frederic Ruget, Jun 12 2021

sign

The Carter and Reyes 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 Carter and Reyes strategy described here, the Tiefenbruck strategy described in A345257, or variations thereof. Also it is an open problem whether strategies can achieve results better than 7/20.
The Carter and Reyes strategy is defined using the 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 Carter and Reyes 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.

Numberphile, Hat Problems - Numberphile.
Frederic Ruget, Towers of hats.
Frederic Ruget, Hats Calculator.
Frederic Ruget, Infinitely Many Hats.
Stan Wagon, An Infinitely Puzzling Hat Problem.

Cf. A007814.

Cf. A345257.

function a(n) {
    if (n == 0) return -1;
    let offset = 0;
    while (true) {
        switch (n & 7) {
            case 1: return offset + 1;
            case 2: return 0;
            case 3: return 0;
            case 4: return offset + 2;
            case 5: return offset + 1;
            case 6: return offset + 2;
        }
        n = ((n >> 2) & (~1)) | (n & 1);
        offset += 2
    }
}

[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 n mod 8 = 0, then a(n) = a(2*floor(n/8)) + 2*[a(2*floor(n/8)) != 0],
otherwise a(n) = a(2*floor(n/8) + 1) + 2 * [a(2*floor(n/8) + 1) != 0].

cp's OEIS Frontend

A345255 Carter and Reyes sequence for the game of countably infinitely many hats.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

JavaScript

Formula