Solutions and discussion of yesterday's logic puzzles

[woodpijn]

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.

Comments

[simont]

#3: very clever! I had the "exclude one of the residues mod 3" decent-but-not-optimal solution. I certainly wouldn't have got to the Hamming approach even given more time to think: even if I'd had the thought of error-correcting codes at all, which I didn't, my coding theory is not good enough that I'd have known what the best possible one in 31 bits might be

[simont]

But now I properly understand the way that Hamming code is constructed, I feel as if I could have got it, since it's essentially equivalent to the thing you're doing with the chessboard in puzzle #2 (minus the square labelled 0), which I did already know the answer to!

I suppose that if the number of players is 1 less than any other power of two, the same construction must work, scaled up or down. And if you have some other number of players, then a lower bound on the best answer is given by having the first 2n−1 of them do this strategy between them, and everyone else just keep quiet.

[woodpijn]

Yes, I was struck by how similar the yellow-hats and chessboard solutions turned out to be, despite such different-looking setups.

[alextfish]

Nice! I can't see any problems with that off the top of my head.

It looks... similar to the solution I saw (for the 5-player version). Not exactly the same.

...Ahh. I've just dug out the original solution, and it's actually fairly unsatisfying. This genetic algorithm to find a solution talks through it in more detail, but is still opaque. Your solution seems a lot nicer than either of those pages, and neither of those pages seem to claim (or demonstrate) that the puzzle really needs all 5 citizens!

[simont]

This makes me want to look into other applications of index-XOR

Then perhaps you'd be interested to know that it's related to a standard construction of category theory. That per se doesn't mean it has practical applications, of course :-) but it might be relevant regardless.

A standard construction of category theory is called a "free functor", which turns a thing of type A into a thing of type B in the "most general" kind of way. This is a bit of a vague definition, and depending on A,B the details can go all sorts of strange ways (e.g. free groups), but the relevant example is the free functor that turns an arbitrary set S into a vector space V (over some pre-specified field 𝔽) whose basis corresponds to the original set: you say that an element of V is just any old way of assigning a nonzero coefficient in 𝔽 to some finite set of elements of S. (Put another way, V is the space of functions S→𝔽 with finite support

[woodpijn]

Cool! I know almost nothing about category theory except that Alex did his Part III on it and says it's very cool and like set theory but "more so". That, and your comment here, make me both intrigued and slightly intimidated.

[atreic]

Nothing much to say on hard logic puzzles (other than I only came across the cycles one this year, and it took me So Long to get my head round it, it’s ridiculously cool once you see it!) but I am amused that I thought I recognised the yellow-loving, so messaged Jacob S, and it was indeed his comment. The world is small 😊

[ilanin]

He actually posted the same puzzle on Facebook a few months back; the answering thread was somewhat interesting, if you can actually find it.

[woodpijn]

Oh, cool! I don't think I know him (don't recognise that name), but I have previously had the experience of thinking something posted on SSC/ACX was cool and then subsequently realising the poster is someone I knew :)
I'm glad I kept the original yellow details from the original rather than paraphrasing it, then, so that you could enjoy that experience :)

[atreic]

He's another mathmo, but I think he was a few years after us, I mostly know him from folk dance :-) He was at my wedding ceilidh (he's the one that whenever my family see the photos, they go 'why is that man wearing bright yellow?' :-D <3 )

[simont]

The actual optimal solution (according to the OP; IDK how to prove it's optimal)

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

[simont]

Yes, here we go, I think I believe this

[woodpijn]

Nice insight with the overlapping.