TY - GEN
T1 - A new variation of hat guessing games
AU - Ma, Tengyu
AU - Sun, Xiaoming
AU - Yu, Huacheng
N1 - Funding Information:
This work was supported in part by the National Natural Science Foundation of China Grant 60603005, 61061130540, the National Basic Research Program of China Grant 2007CB807900, 2007CB807901, and Tsinghua University Initiative Scientific Research Program 2009THZ02120.
PY - 2011
Y1 - 2011
N2 - 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 perfect if it can achieve the simple upper bound n/n+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 a perfect strategy for (n,k) is open for only a few values of n. In our construction we introduce a new notion: (d1,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 (d1,d2)-regular partition is explored in the paper and the existence of perfect k-dominating set follows as a corollary.
AB - 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 perfect if it can achieve the simple upper bound n/n+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 a perfect strategy for (n,k) is open for only a few values of n. In our construction we introduce a new notion: (d1,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 (d1,d2)-regular partition is explored in the paper and the existence of perfect k-dominating set follows as a corollary.
KW - Hat guessing game
KW - hypercube
KW - k-dominating set
KW - perfect code
KW - perfect strategy
UR - http://www.scopus.com/inward/record.url?scp=80051994529&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051994529&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22685-4_53
DO - 10.1007/978-3-642-22685-4_53
M3 - Conference contribution
AN - SCOPUS:80051994529
SN - 9783642226847
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 616
EP - 626
BT - Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
T2 - 17th Annual International Computing and Combinatorics Conference, COCOON 2011
Y2 - 14 August 2011 through 16 August 2011
ER -