A+ CATEGORY SCIENTIFIC UNIT

Minimal predictors in hat problems

Volume 208 / 2010

Christopher S. Hardin, Alan D. Taylor Fundamenta Mathematicae 208 (2010), 273-285 MSC: Primary 03E05; Secondary 03E17. DOI: 10.4064/fm208-3-4

Abstract

We consider a combinatorial problem related to guessing the values of a function at various points based on its values at certain other points, often presented by way of a hat-problem metaphor: there are a number of players who will have colored hats placed on their heads, and they wish to guess the colors of their own hats. A {\it visibility relation} specifies who can see which hats. This paper focuses on the existence of minimal predictors: strategies guaranteeing at least one player guesses correctly, regardless of how the hats are colored. We first present some general results, in particular showing that transitive visibility relations admit a minimal predictor exactly when they contain an infinite chain, regardless of the number of colors. In the more interesting nontransitive case, we focus on a particular nontransitive relation on $\omega$ that is elementary, yet reveals unexpected phenomena not seen in the transitive case. For this relation, minimal predictors always exist for two colors but never for $\aleph_2$ colors. For $\aleph_0$ colors, the existence of minimal predictors is independent of ZFC plus a fixed value of the continuum, and turns out to be closely related to certain cardinal invariants involving meager sets of reals.

Authors

  • Christopher S. HardinDepartment of Mathematics
    Union College
    Schenectady, NY 12308, U.S.A.
    e-mail
  • Alan D. TaylorDepartment of Mathematics
    Union College
    Schenectady, NY 12308, U.S.A.
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image