A new variation of hat guessing games

Tengyu Ma, Xiaoming Sun, Huacheng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 17th Annual International Conference, COCOON 2011, Proceedings
Pages616-626
Number of pages11
DOIs
StatePublished - 2011
Externally publishedYes
Event17th Annual International Computing and Combinatorics Conference, COCOON 2011 - Dallas, TX, United States
Duration: Aug 14 2011Aug 16 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6842 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Annual International Computing and Combinatorics Conference, COCOON 2011
Country/TerritoryUnited States
CityDallas, TX
Period8/14/118/16/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Hat guessing game
  • hypercube
  • k-dominating set
  • perfect code
  • perfect strategy

Fingerprint

Dive into the research topics of 'A new variation of hat guessing games'. Together they form a unique fingerprint.

Cite this