cp's OEIS Frontend

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

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