Solutions and discussion of yesterday's logic puzzles
This post is for discussion and solutions to the hard logic puzzles in my previous post. I recommend reading that one first, especially if you want to think about the puzzles without spoilers.
( Spoily puzzle solutions )
( Spoily puzzle solutions )
Here's a handwavy argument, somewhat short of a rigorous proof, but perhaps it's possible to make every step of it rigorous.
Looking at the SSC thread you linked from the previous post, one comment gives a hint to a baffled poster that says something relevant. Paraphrasing the hint:
The reason one feels this problem is impossible at first sight is that, without any knowledge of your own hat, you think that surely you can't guess it with more accuracy than probability 1/2. And this intuition is not entirely unjustified, because the scenarios where I guess right will unavoidably biject with the ones where I guess wrong, so (conditional on me making a guess at all) I indeed can't do better than 1/2. (Which is not to say that there isn't any fallacy in the intuition - but the error is in conflating "prob of me guessing right" with "prob of overall team victory", not in judgement of the former.)
So, for every hat arrangement where we have a player guess right, there will unavoidably be a hat arrangement where the same player guesses wrong. With that constraint, how can we minimise the total number of arrangements where at least one player guesses wrong?
Firstly: by arranging that the wrong-guess arrangements overlap as much as possible, so that my wrong guesses, your wrong guesses and the other 29 players' wrong guesses are all concentrated into the same small subset of the space, instead of spreading out over separate parts of it and increasing the total number of failures.
Both of the suggested solutions here (the mod 3 one and the Hamming-code one) have that property to the maximum extent possible: in the case where somebody guesses wrong, it turns out that everybody guesses wrong, all at once. But one of those strategies does a lot better than the other, so what else is it doing right to achieve that?
Secondly: you also want the players to guess as little as possible, because guessing is intrinsically dangerous - for every situation in which a player guesses at all, there's a situation where they guess wrong. The mod-3 solution has each player guessing in about 2/3 of the cases, so each player causes 1/3 of the problem space to be full of failures, and the best you can do is to make all those 1/3-sized failure spaces coincide. Whereas the Hamming solution makes each player guess only 1/16 of the time (hence, being wrong 1/32 of the time), and now if you totally overlap all their failure-spaces, you've got a 1/32 probability of failure overall.
Is that the best possible? Surely it must be, because if you reduce the probability any further of each player making a guess at all, you end up with the shared failure zone and the separated success zones unable to cover the whole space between them - i.e. you'll start to have areas of the space in which the players lose due to everybody staying silent.
Reply
In a given deterministic strategy, we can count up the total number of hat arrangements in which each player makes a guess at all. Call these numbers n_1,...,n_31. WLOG, let them be in descending order (if they differ at all): n_1 ≥ n_2 ≥ ... ≥ n_31. Each of these counts must be even (because the strategy can't call for me to do a different thing in any two arrangements differing only in my own hat), and each player's guesses must be exactly half right and half wrong, so each player has n_i/2 correct guesses and n_i/2 wrong ones.
An upper bound on the number of successes is (Σn_i) / 2: that's the total number of correct guesses made by all the players together, of which there must be at least one in every hat arrangement that the players win.
A lower bound on the number of failures is n_1 / 2: that's the total number of wrong guesses by player 1, and each of those wrong guesses must be in a different hat arrangement. (Of course, any other n_i / 2 is also a lower bound for the same reason, but the largest of them is the interesting one.)
We want to make Σn_i as large as possible. But the two quantities are related by the inequality Σn_i ≤ 31n_1 (since each individual n_i is at most n_1). In other words, the ratio (max successes / min failures) is at most 31, and that in turn is an upper bound on the ratio (successes / failures).
So an upper bound on the number of successes is 31/32 of the whole space, because with any more successes, the necessary number of failures to go with it wouldn't fit.
And that bound is attained by the Hamming-code solution, so it is indeed the best possible!
(We might also consider probabilistic strategies, in which each player can respond to some or all of the visible hat arrangements by choosing among their possible actions randomly with some distribution. But this is equivalent to saying that the players as a whole have some probability distribution from which they choose between a number of deterministic strategies. And if each deterministic strategy has at most a 31/32 success rate, so does the mean / expected value of any probability distribution of them. So probabilistic strategies can't do better.)
Reply
Reply
Leave a comment