A New Variation of Hat Guessing Games

DOI10.1007/978-3-642-22685-4_53zbMATH Open1353.91005arXiv1101.0869OpenAlexW1877628645MaRDI QIDQ3087987FDOQ3087987

Authors: Tengyu Ma, Xiaoming Sun, Huacheng Yu 

Publication date: 17 August 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Several variations of hat guessing games have been popularly discussed in recreational mathematics. In a typical hat guessing game, after initially coordinating a strategy, each of $n$ players is assigned a hat from a given color set. Simultaneously, each player tries to guess the color of his/her own hat by looking at colors of hats worn by other players. In this paper, we consider a new variation of this game, in which we require at least $k$ correct guesses and no wrong guess for the players to win the game, but they can choose to "pass". A strategy is called {em perfect} if it can achieve the simple upper bound $fracnn+k$ of the winning probability. We present sufficient and necessary condition on the parameters $n$ and $k$ for the existence of perfect strategy in the hat guessing games. In fact for any fixed parameter $k$, the existence of perfect strategy can be determined for every sufficiently large $n$. In our construction we introduce a new notion: $(d_1,d_2)$-regular partition of the boolean hypercube, which is worth to study in its own right. For example, it is related to the $k$-dominating set of the hypercube. It also might be interesting in coding theory. The existence of $(d_1,d_2)$-regular partition is explored in the paper and the existence of perfect $k$-dominating set follows as a corollary.

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

Recommendations

• Hat Guessing Games
• Hat Guessing Games
• Yet another hat game
• Guessing Games
• A variant of the guessing secrets game
• Take-and-guess games
• The Hats game. On maximum degree and diameter
• A modified hat problem
• Hat guessing on books and windmills
• The hat guessing number of graphs

zbMATH Keywords

hypercubeperfect code\(k\)-dominating sethat guessing gameperfect strategy

Mathematics Subject Classification ID

Cooperative games (91A12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial games (91A46)

Cited In (8)

• Hat problem: a new strategy based on quantum stabilizer codes
• A note on marking lines in \([k]^n\)
• The Hats game. On maximum degree and diameter
• On 1-factorizations of bipartite Kneser graphs
• On a conjecture of Butler and Graham
• The three colour hat guessing game on cycle graphs
• Hat Guessing Games
• THE COMPLETE VERSION OF THE GORRITI HAT GAME

This page was built for publication: A New Variation of Hat Guessing Games

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