Minimal predictors in hat problems

Christopher S. Hardin¹ ; Alan D. Taylor¹

¹Department of Mathematics Union College Schenectady, NY 12308, U.S.A.

Fundamenta Mathematicae, Tome 208 (2010) no. 3, pp. 273-285

Résumé

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.

Détail

DOI : 10.4064/fm208-3-4

Keywords: consider combinatorial problem related guessing values function various points based its values certain other points often presented hat problem metaphor there number players who have colored hats placed their heads wish guess colors their own hats visibility relation specifies who see which hats paper focuses existence minimal predictors strategies guaranteeing least player guesses correctly regardless hats colored first present general results particular showing transitive visibility relations admit minimal predictor exactly contain infinite chain regardless number colors interesting nontransitive focus particular nontransitive relation omega elementary yet reveals unexpected phenomena seen transitive relation minimal predictors always exist colors never aleph colors aleph colors existence minimal predictors independent zfc plus fixed value continuum turns out closely related certain cardinal invariants involving meager sets reals