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 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 ω 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 ℵ₂ colors. For ℵ₀ 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-fm208-3-4,
author = {Christopher S. Hardin and Alan D. Taylor},
title = {Minimal predictors in hat problems},
journal = {Fundamenta Mathematicae},
volume = {209},
year = {2010},
pages = {273-285},
zbl = {1196.03056},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm208-3-4}
}
Christopher S. Hardin; Alan D. Taylor. Minimal predictors in hat problems. Fundamenta Mathematicae, Tome 209 (2010) pp. 273-285. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm208-3-4/