{"id":981,"date":"2014-08-29T18:19:13","date_gmt":"2014-08-29T22:19:13","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=981"},"modified":"2014-08-29T18:19:13","modified_gmt":"2014-08-29T22:19:13","slug":"the-infinite-hat-problem","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2014\/08\/29\/the-infinite-hat-problem\/","title":{"rendered":"The infinite hat problem"},"content":{"rendered":"

The infinite hat problem<\/a>\u00a0is a great puzzle. If you have a strong math background, you should try solving it before reading my solution below!<\/p>\n

Here’s my strategy for the wizards: first, they agree on an ordering of themselves. Each wizard can be indexed by a natural number, since there are countably many of them. They then consider the set of all possible hat configurations $S$ with respect to that ordering. By the\u00a0well-ordering theorem<\/a>\u00a0(which is equivalent to the axiom of choice<\/a>) a well-ordering of $S$\u00a0exists; the wizards also agree on a specific well-ordering.<\/p>\n

Note that this step is\u00a0non-constructive<\/em> because it relies on the axiom of choice. That is, such a well-ordering exists but there may not be a way to explicitly construct it. The point of the note about assuming the axiom of choice was a tip-off that the wizards need to make their decision based off of a set whose existence is only ensured by the axiom of choice.<\/p>\n

Once the well-ordering has been chosen the wizards are ready to receive their hats. Once they are able to see everyone else’s hat, they each construct a\u00a0subset $T$ of $S$ which contains the hat configurations which differ from the configuration they can see in only finitely many hats. The lack of knowledge about a wizard’s own hat is irrelevant to this construction, since\u00a0that lack of knowledge only\u00a0changes the configuration they see in finitely many hats. In particular, for every wizard their subset\u00a0$T$\u00a0will consist of the true configuration along with all configurations which differ from the true configuration in finitely many hats, and therefore be the same for all wizards.<\/p>\n

Now that all the wizards have constructed the same $T\\subset S$, they use the well-ordering of $S$ to find the least\u00a0element of $T$, and everyone guesses the hat colour which they have in the least element. Since every element of $T$ differs from the true configuration in finitely many hats, the configuration that the wizards guess will also differ in finitely many hats. Thus\u00a0almost all<\/em>\u00a0wizards will choose correctly.<\/p>\n

I\u00a0heard about the problem on a list of good logic puzzles<\/a> compiled by Philip Thomas. I purposely haven’t read his solution yet,\u00a0since I didn’t want that to influence me while writing down\u00a0my solution.<\/p>\n","protected":false},"excerpt":{"rendered":"

The infinite hat problem\u00a0is a great puzzle. If you have a strong math background, you should try solving it before reading my solution below! Here’s my strategy for the wizards: first, they agree on an ordering of themselves. Each wizard … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,7],"tags":[],"_links":{"self":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/981"}],"collection":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=981"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/981\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=981"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=981"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=981"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}