Martin Kraft

Personal Blog

Solving the Trunk Puzzle

This is my solution to a logic puzzle from Discrete Mathematics and Its Applications by Kenneth H. Rosen, which I recently picked up and am working through. It’s exercise 17c from Section 1.2.

Question

As a reward for saving his daughter from pirates, the King has given you the opportunity to win a treasure hidden inside one of three trunks. The two trunks that do not hold the treasure are empty. To win, you must select the correct trunk.

The trunks are inscribed with the messages:

“Exactly two of the inscriptions are true,” says the Queen.

… determine whether the Queen who never lies could state this, and if so, which trunk the treasure is in.

Solution

Compound Proposition

Let’s assign each trunk a propositional variable p1, p2, or p3 with a true value if the trunk contains the treasure and a false value if it does not. Using these variable the inscriptions on trunk 1, trunk 2, and trunk 3 can be written p3, p1, and ¬p3, respectively.

The Queen’s proposition that “exactly two of the inscriptions are true” can be written in English as “one of either the first inscription is false, or the second inscription is false, or the third inscription is false”. That sentence can be expressed as the compound proposition:

p3p1 ∧ ¬p3) ⊕ (p3 ∧ ¬p1 ∧ ¬p3) ⊕ (p3p1 ∧ ¬(¬p3))

That can be simplified by removing the duplication of ¬p3 and the contradiction (p3 ∧ ¬p1 ∧ ¬p3). Finally we can remove the double negation ¬(¬p3) because ¬(¬p3) ≡ p3.

p3p1 ∧ ¬p3) ⊕ (p3 ∧ ¬p1 ∧ ¬p3) ⊕ (p3p1 ∧ ¬(¬p3))

The remaining compound proposition is:

p3p1) ⊕ (p3p1)

Truth Table

Our compound proposition can be used to construct a truth table:

# p1 p2 p3 ¬p3 ¬p3p1 p3p1 p3p1) ⊕ (p3p1)
1 T T T F F T T
2 T T F T T F T
3 T F T F F T T
4 T F F T T F T
5 F T T F F F F
6 F T F T F F F
7 F F T F F F F
8 F F F T F F F

Examining the truth table, row 4 is the only row that is both satisfiable and where the treasure exists in only one of p1, p2, or p3, or in other words where p1p2p3. Therefore trunk 1 contains the treasure.

Posted