3

Logic is one of the facets of math that is more 'fun', but this one is beyond me. Consider using logic statements and/or truth tables. 'Or' here is inclusive, that is 'A or B' means 'A or B or both, but not neither'.

King Warren suspects the Earls of Akaroa, Bairnsdale, Claremont, Darlinghurst, Erina and Frankston of plotting a conspiracy against him. He questions them in private and they each tell him:

Akaroa: If Darlinghurst and Erina are both loyal, then Frankston and either Bairnsdale or Claremont are traitors.

Bairnsdale: If either Claremont or Erina are traitors, then either Darlinghurst is a traitor and Claremont isn’t, or Erina is and Akaroa isn’t.

Claremont: Anyone here could be a traitor except for me.

Darlinghurst: If Frankston is a traitor and Bairnsdale’s involvement in the conspiracy implicates Erina’s involvement, then Claremont is a traitor.

Erina: If Akaroa is a traitor and the fact Bairnsdale is not a traitor means that Claremont is, then Akaroa is not a traitor.

Frankston: If Claremont is a traitor so is Akaroa.

Each traitor will give false information but each loyal Earl will give true statements. At least how many traitors are there, and who are they?

Thomas Andrews
  • 177,126
Y-dog
  • 627
  • 2
    In Akaroa's statement, you mention Claremont twice. Is that right? It seems the part "and either Bairnsdale or Clarement" can be removed and you'll get an equivalent statement. – Samuel Jun 06 '13 at 12:40
  • Is 'either ... or' meant to be interpreted as exclusive or or inclusive or? – Abel Jun 06 '13 at 12:42
  • If you don't mind my asking, what's the source of this puzzle? Searching for King Warren and the other names turn up a similar (but distinct) problem, e.g., number 24 from the Australian Mathematics Competition 2009 Intermediate Division Competition. Many people will be less willing to post if it looks like you're looking for test answers. – Joshua Taylor Jun 06 '13 at 12:51
  • 1
    Don't add the tag "logic" back in. Yes, this is a logic puzzle, but no, this does not fit the M.SE definition of the logic tag, which is about formal theories of logic, not about puzzles of this sort. – Thomas Andrews Jun 06 '13 at 12:57
  • I happen to know that question (24) as well, i did (and enjoyed) the AMC that year. This was someone's challenge from the school logic unit. That is, we were all supposed to make or research a question for the class to solve, but most people did not get the chance to present answers. Now i've finished school here is probably the best place to ask. – Y-dog Jun 06 '13 at 12:58

1 Answers1

5

Introduce boolean variables $A,B,C,D,E,F$, where $A$, for instance, is true if Akaroa is not a traitor and false otherwise, and analogously for the rest of the variables. Then we have five equations

$$\begin{align} A&=(D\wedge E)\to (\neg F \wedge (\neg B \vee \neg C))\\ B&=(\neg C\vee \neg E)\to (\neg D\wedge C\vee E\wedge\neg A)\\ C&=C\\ D&=(\neg F\wedge(\neg B\to\neg E))\to\neg C\\ E&=(\neg A\wedge(B\to\neg C))\to A\\ F&=\neg C\to\neg A. \end{align}$$

We could simply try all $2^6=64$ combinations of truth values to $A,\ldots,F$ and see which solutions there are. It can be done by hand or easily by computer. There might, by chance, be a short elegant algebraic solution, but I don't want to look for it right now. This problem is an instance of 3SAT, and I don't want to spend superpolynomial time solving this problem (assuming P$\neq$NP).

Added: I input this into Mathematica, and if I didn't make any mistakes, there are 26 solutions. One of them is that everyone is a traitor, and the largest number of loyal earls is 5, which happens twice. The solutions are, sorted by the number of traitors:

$$\begin{matrix} A&B&C&D&E&F\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 0& 1\\ 0& 1& 1& 0& 0& 0\\ 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 0& 0\\ 1& 0& 1& 0& 0& 0\\ 0& 0& 1& 1& 0& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 1& 1& 0& 1& 0\\ 1& 0& 0& 1& 1& 0\\ 1& 0& 1& 0& 0& 1\\ 1& 0& 1& 0& 1& 0\\ 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 1& 1& 0& 1\\ 1& 0& 1& 1& 1& 0\\ 1& 1& 1& 0& 0& 1\\ 1& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 1& 1& 1& 0& 1& 1 \end{matrix}$$

If one would happen to know the answer beforehand, or guess it, then it is easy to verify by hand: just check that $A=0,B=C=D=E=F=1$ is a solution and that $A=B=C=D=E=F=1$ is not a solution. Thus the answer to the puzzle is: the least number of traitors is one, and then it is either Akaroa or Darlinghurst.

Samuel
  • 5,550
  • 1
    I think we're looking for a short and elegant solution, but what you've said is very true. This question essentially involves 6 Boolean Variables. – Y-dog Jun 06 '13 at 13:02
  • 1
    There's no need to spend super-polynomial time on this. In general, 3SAT is in NP, but that doesn't mean a specific instance is. – Foo Barrigno Jun 06 '13 at 13:19
  • Note, $E$ should be $\to A$, since $E$ says that it implies $A$ is not a traitor, which means $A$ is true. – Thomas Andrews Jun 06 '13 at 13:41