Too Many Hats

2018/10/18 by Rob Pratt, Pratt, Rob, Stan Wagon +5 · 1 citation
Computer Science · Mathematics · #05B30 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1810.08263

openalex publication_date 2018/10/18 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

A puzzle about prisoners trying to identify the color of a hat on their head leads to a version where there are k more hats than prisoners. This generalized puzzle is related to the independence number of the arrangement graph A(m, n) and to Steiner systems and other designs. A natural conjecture is that perfect hat-guessing strategies exist in all cases, where "perfect" means that the success probability is 1/(k+1). This is true when k = 1, but we show that it is false when k = 2. Further, we present a strategy with success rate at least 1/O(k log k), independent of the number of prisoners.

Cited by

• A probabilistic look at the infinite hat-guessing game

Related

• The hat guessing number of graphs
• The Hats game. The power of constructors
• A General Theorem for Non-Simultaneous Hat Guessing Puzzles
• The success probability in Lionel Levine's hat problem is strictly decreasing with the number of players, and this is related to interesting questions regarding Hamming powers of Kneser graphs and independent sets in random subgraphs
• A note on the problem of prisoners and hats