A New Variation of Hat Guessing Games

DOI10.1007/978-3-642-22685-4_53MaRDI QIDQ3087987zbMATH OpenOpenAlexFDO

Authors Tengyu Ma, Xiaoming Sun, Huacheng Yu

Publication date 17 August 2011

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

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

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)

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.

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

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 a conjecture of Butler and Graham
• On 1-factorizations of bipartite Kneser graphs
• The three colour hat guessing game on cycle graphs
• THE COMPLETE VERSION OF THE GORRITI HAT GAME
• Hat Guessing Games

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)