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 -