You're reading: cp's mathem-o-blog, Features

#thatlogicproblem round-up

C: $K_A m; \\ K_B d.$

A: $\neg K_A d; \\ m \vDash \neg K_B m.$

B: $d \not\vDash K_B m; \\ (K_A(\neg K_B m)) \vDash K_B (m,d).$

A: $m \wedge K_B(m,d) \vDash K_A (m,d).$

Albert, Bernard and Cheryl have had a busy week. They’re the stars of #thatlogicproblem, a question from a Singapore maths test that was posted to Facebook by a TV presenter and quickly sent the internet deduction-crazy.

First of all: no, it’s not meant to be answered by an average Singaporean student. It’s a hard question from a schools Olympiad test.

You’ve doubtless seen multifarious debates about the correct answer on your Facebook/Twitter/Friendface feeds. The various newspapers of the world saw an opportunity for some easy page views and each wrote basically the same story: When iCheryl’s birthday? Only maths weirdos can possibly work it out.

By far the best treatment, in my opinion, is by top pop maths chap Alex Bellos in the Guardian. He’s written a few pieces: first asking “can you solve” (with an encouraging number of fallacious arguments for each answer in the comments) and then explaining “how to solve” with his model solution. Later on, Alex was invited onto BBC TV to present his solution.

Over on Radio 4, the Today programme got carried away with logic puzzles and presenter Sarah Montague managed to read out the wrong answer to a hats puzzle.

STOP PRESS: while this post was working its way through our editing process, Numberphile posted its own explanation of the problem.

Following a discussion on Facebook where Phil Walker of Leeds University gave a firmer epistemic reason for the mainly-incorrect answer of August 17, Alex invited James Grime to write about this alternate line of reasoning. I’m still not having it though. And because everything written on the internet has to subsequently become a video, James has posted his explanation of the different interpretations to his YouTube channel.

If you’re still unsure, or still being bombarded by relatives who want an explanation, have a look at this fantastic interactive explanation by Mark Josef. When you click on the day you think is Cheryl’s birthday, it walks through the conversation (as well as Albert and Bernard’s internal monologues) and highlights any statements that would be inconsistent.

By the way, my wife ((I got married on Sunday! Hooray!)) asked why the characters in the original puzzle were called Albert, Bernard and Cheryl. In case you’re also wondering that, it’s a convention in this kind of thing to give the characters names whose first letters work through the alphabet, so in your working-out you can abbreviate them to A,B,C,… Famously, in cryptography problems Alice and Bob have a whale of a time sending messages to each other.

Now, with the original question definitively dealt with and the populace at large going mad for logic problems, the world’s mathmos are scrabbling to show off their favourite deduction problems.

Kit Yates is jumping on the bandwagon with this version, which he says was used as an interview question for several years:

Tanya Khovanova is the master of this sort of thing. Conway’s wizards on a bus puzzle is the apotheosis of the genre and Tanya has written a great paper about its solution, along with a generalised version. Probably inspired by the current hullabaloo (or maybe not – she is usually thinking about these things), Tanya posted an extremely concise puzzle to her blog yesterday.

Deduction is normally done by prisoners either in hats or with boxes. If you really want to blow your brain sockets, try the blue-eyed islanders puzzle. Terry Tao posted it to his blog once and a gargantuan comments thread full of people not getting it ensued.

Meanwhile, Tim Gowers is all “I hear you like deduction, so I put some deduction in your deduction so you can deduce while you deduce” with this transfinite version. Although Joel David Hamkins turned up in the comments and shared his version, which looks much nicer to me. Later on, he added yet another transfinite epistemic logic puzzle.

With all this talk of deduction, you might remember the QI-worthy observation that Sherlock Holmes doesn’t do deduction – he does abduction (hey, whaddya know: I did learn that on QI!). Deductive reasoning is the process of working from a set of premises to a certain conclusion by fixed rules of inference. Inductive reasoning involves using premises which provide evidence for a conclusion which is probably true. Finally, abductive reasoning is when you try to find the simplest explanation for an observation.

“CP”, you say, “that’s all well and good, but can you put all this in joke form?”

Yes.

The classic spikedmath.com rendering of the canonical public announcement logic joke.

The classic spikedmath.com rendering of the canonical public announcement logic joke.

Since this is a maths site, I should think about what all these puzzles have in common and how to formalise them. Clearly they’re logic puzzles, but the deductions based on announcements can’t be written down in classical logic. It turns out there’s a thing called public announcement logic which provides a whole load of new modal operators such as “I know $\phi$”, and “$\phi$ is not refutable”.

My go-to resource for explaining public announcement logic is The Muddy Children:
A logic for public announcement, a set of slides by Jesse Hughes.

muddy children

There’s a whole load of notation around public announcement logic, involving things like Kripke frames. The whole thing got going with Jan Plaza’s paper “logics of public communications”. For a paper introducing a new field of logic, it’s surprisingly readable!

The notation at the top of this post is a mangled mash of various things that sort of represent the conversation in #thatlogicproblem but no self-respecting logician would recognise it.

2 Responses to “#thatlogicproblem round-up”

(will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>