Four really hard logic puzzles

[woodpijn]

These have in common that they can sound impossible at first description, even (or perhaps especially) to seasoned puzzlers and/or people with some mathematical knowledge. In all cases, if I were presented with them for the first time and asked "either do this or provide a proof that it's mathematically impossible", I'd be inclined to start working

Comments

[geekette8]

Is the "each wearing either a buttercup yellow hat or a hat or a cadmium yellow hat" deliberate? I don't see anyone remarking on it in the ACX thread either.

[woodpijn]

Wow, I'm embarrassed to say I didn't notice that! No, I think "or a hat" can be ignored.

[geekette8]

Also, in the first puzzle, are the boxes moveable, i.e. can they be shuffled around or arranged in a particular order?

[woodpijn]

No, they can't be moved or rearranged, but we can assume there's an obvious natural way that they're ordered (rather than just being in a haphazard heap).

[khoth]

I've seen 1 and 3 before.

2: I can't completely get it but this almost works: Ahzore gur fdhnerf 1 gb 64, nqq gur inyhrf bs gur fdhnerf jvgu urnqf ba, nqwhfg n pbva fb gung gur gbgny zbq 64 vf gur gnetrg fdhner. Ohg V'z abg fher lbh pna nyjnlf qb guvf orpnhfr lbh zvtug jnag gb nqq 23 ohg 23 vf nyernql n urnqf. Srryf yvxr gur evtug genpx gubhtu

--------------

5, if you want it: An infinite number of mathematicians will each be given a hat. They'll be able to see everyone's hats except for their own. They each have to simultaneously guess their own hat colour. Is there a strategy such that only finitely many of them will be wrong?

[woodpijn]

2: Yes, that's ridiculously close.

5: Cool, that's definitely in the same category of puzzles that initially look completely impossible!
Are there any constraints on the hat colours? Or can they be any colour from the (extremely large, but presumably finite for quantum-ish reasons) number of distinct wavelengths in the visible light spectrum?

[khoth]

No real constraint on hat colours, except that they have to form a set.

(Also, the solution requires the axiom of choice and isn't remotely something an infinite number of real people could actually do)

[khoth]

In case anyone comes across this later, the solution:

Pbafvqre nyy cbffvoyr nffvtazragf bs ungf gb crbcyr. Qrsvar nffvtazragf nf rdhvinyrag vs gurl qvssre sbe ng zbfg svavgryl znal crbcyr. (Guvf vf n erny rdhvinyrapr eryngvba, vs nffvtazragf N naq O ner rdhvinyrag, naq O naq P ner, gura N naq P nyfb zhfg or). Fb lbh pna cnegvgvba gur frg bs cbffvoyr nffvtazragf vagb rdhvinyrapr pynffrf. Va gur cer-tnzr fgengrtl zrrgvat, rirelbar nterrf ba n ercerfragngvir nffvtazrag sbe rnpu rdhvinyrapr pynff (guvf arrqf gur nkvbz bs pubvpr naq lbh pbhyqa'g npghnyyl qb guvf va erny yvsr...).

Gura, bapr rirelbar frrf gur ungf, gurl pna gryy juvpu rdhvinyrapr pynff gurl'er va (orpnhfr gurl pna frr nyy ohg n svavgr ahzore (bar) bs gur ungf). Gura rirelbar thrffrf nppbeqvat gb gur nffvtazrag gurl pubfr.

Fb (vasvavgryl ynetr) fgengrtl ybbxf yvxr "Vs gur ung nffvtazrag lbh frr vf bayl qvssrerag sebz 'nyy oynpx' sbe n svavgr ahzore bs crbcyr, thrff oynpx. Vs vg'f bayl svavgryl qvssrerag sebz 'nygreangvat benatr naq checyr', thrff onfrq ba gung. rgp rgp

[simont]

Thank you for this. I have a fairly large collection of hat puzzles of the #3/#4 kind, but nonetheless, #3 and #4 themselves are new to me!

I'll be curious to hear what the intended answer for #4 is. I've got an answer, but I don't think it can be the one the puzzle designer intended, because: vg bayl arrqf sbhe bs gur svir cynlref. Vg fhssvprf gb unir gjb ebjf bs gjb cynlref rnpu snpvat rnpu bgure. Fb gur guveq cynlre va bar bs gur ebjf pna or pbzcyrgryl vtaberq, va gur frafr gung abar bs gur bgure sbhe cynlref' qrpvfvbaf vf nssrpgrq ol gur rkgen cynlre'f ung pbybhe, naq bar bs gur bgure sbhe jvyy eryvnoyl thrff evtug, fb vg jbhyqa'g rira znggre vs cynlre svir unf fhcerzryl onq yhpx naq nyjnlf thrffrf jebat

[woodpijn]

#4: Ooh, you might be right. I confess #4 is the only one I don't actually know the solution for. I feel like I've got quite close (and will expand on that in the follow-up post). Alex knows the solution, so I thought that was good enough to justify including it in my post. I don't know where Alex got the puzzle from; it might be that there's a better solution than the person posting it realised.

#1': Oh, cool. Yes, I think they can: vs gurer'f n plpyr ybatre guna svsgl, fjnc gjb qvnzrgevpnyyl bccbfvgr obkrf jvguva vg, yvxr gur "zvqqyr" bar naq gur "ynfg" bar, gb fcyvg vg vagb gjb plpyrf unys gur fvmr.

[simont]

Cerpvfryl!

[simont]

On #3: the question calls for a solution giving the best chance of escape. But it leaves unspecified the question of how the hat colours are chosen, i.e. from what probability distribution. I guess we're meant to evaluate candidate solutions based on the most obvious distribution in which all the 2n possible arrangements are equiprobable?

On that assumption, I think I've got an answer that does significantly better than the totally obvious 50-50 guesswork strategy - but I'm absolutely nowhere near thinking of a way to prove it's the best possible!

[woodpijn]

Yes, I think the OP clarified that about the probability distribution later in the thread; sorry, I probably should have included that.

[simont]

Not to worry - it was the single most obvious assumption :-)

But my solution definitely depends on the choice being random rather than directed. In an adversarial situation where someone was listening to our strategy session and then choosing the hats to defeat it, they would have no trouble doing so, and then we'd all be on uncertain-goat-guard duty for sure.

[woodpijn]

In an adversarial situation where someone was listening to our strategy session and then choosing the hats to defeat it, they would have no trouble doing so

I think that's true in any of these puzzles where you're looking to maximise your chance of success rather than guarantee it (e.g. the 100 prisoners one without your addition of a sympathetic prison guard).