Too many hats

DOI10.1007/S00283-019-09896-6MaRDI QIDQ2325862zbMATH OpenOpenAlexFDO

Authors Rob Pratt, Stan Wagon, Michael J. Wiener, Piotr Zieliński

Publication date 30 September 2019

Published in The Mathematical Intelligencer (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.08263

zbMATH Keywords

puzzle

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05)

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.

Cites work

• scientific article; zbMATH DE number 4075081 (Why is no real title available?)
• scientific article; zbMATH DE number 124524 (Why is no real title available?)
• Nonbinary codes, correcting single deletion or insertion (Corresp.)
• Some Results in the Theory of Quasigroups
• The mathematics of coordinated inference. A study of generalized hat problems

Cited in

(1)

• Prisoners in a line transmitting (binary+ ) bits of information

This page was built for publication: Too many hats

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325862)