cp's OEIS Frontend

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

%I A345255 #38 Mar 08 2024 23:11:33
%S A345255 -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,
%T A345255 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,
%U A345255 2,1,2,3,0,1,0,0,2,1,2,0,4,1,0,0,2,1,2
%N A345255 Carter and Reyes sequence for the game of countably infinitely many hats.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%C A345255 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.
%H A345255 Numberphile, <a href="https://www.youtube.com/watch?v=laAtv310pyk">Hat Problems - Numberphile</a>.
%H A345255 Frederic Ruget, <a href="https://blog.atlant.is/?p=1183">Towers of hats</a>.
%H A345255 Frederic Ruget, <a href="https://blog.atlant.is/?p=1893">Hats Calculator</a>.
%H A345255 Frederic Ruget, <a href="https://blog.atlant.is/?p=2817">Infinitely Many Hats</a>.
%H A345255 Stan Wagon, <a href="http://stanwagon.com/potw/fall13/p1179.html">An Infinitely Puzzling Hat Problem</a>.
%F A345255 [a(n): 0 <= n < 7] = [-1, 1, 0, 0, 2, 1, 2]
%F A345255 For n >= 7:
%F A345255 if (n mod 8) in {1, 2, 3, 4, 5, 6}, then a(n) = a(n mod 8);
%F A345255 otherwise if n mod 8 = 0, then a(n) = a(2*floor(n/8)) + 2*[a(2*floor(n/8)) != 0],
%F A345255 otherwise a(n) = a(2*floor(n/8) + 1) + 2 * [a(2*floor(n/8) + 1) != 0].
%o A345255 (JavaScript)
%o A345255 function a(n) {
%o A345255     if (n == 0) return -1;
%o A345255     let offset = 0;
%o A345255     while (true) {
%o A345255         switch (n & 7) {
%o A345255             case 1: return offset + 1;
%o A345255             case 2: return 0;
%o A345255             case 3: return 0;
%o A345255             case 4: return offset + 2;
%o A345255             case 5: return offset + 1;
%o A345255             case 6: return offset + 2;
%o A345255         }
%o A345255         n = ((n >> 2) & (~1)) | (n & 1);
%o A345255         offset += 2
%o A345255     }
%o A345255 }
%Y A345255 Cf. A007814.
%Y A345255 Cf. A345257.
%K A345255 sign
%O A345255 0,5
%A A345255 _Frederic Ruget_, Jun 12 2021