Mathematics – Combinatorics
Scientific paper
2011-01-05
Mathematics
Combinatorics
9 pages; The main theorem was improved
Scientific paper
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 $\frac{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 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.
Ma Tengyu
Sun Xiaoming
Yu Huacheng
No associations
LandOfFree
A New Variation of Hat Guessing Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A New Variation of Hat Guessing Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Variation of Hat Guessing Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-266091