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.
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:
- Trunk 1: “The treasure is in Trunk 3”
- Trunk 2: “The treasure is in Trunk 1”
- Trunk 3: “This trunk is empty”
“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.
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:
(¬p3 ∧ p1 ∧ ¬p3) ⊕ (p3 ∧ ¬p1 ∧ ¬p3) ⊕ (p3 ∧ p1 ∧ ¬(¬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.
(¬p3 ∧ p1
∧ ¬p3) ⊕ (p3 ∧ ¬p1 ∧ ¬p3) ⊕ (p3 ∧ p1 ∧ ¬(¬p3))
The remaining compound proposition is:
(¬p3 ∧ p1) ⊕ (p3 ∧ p1)
Our compound proposition can be used to construct a truth table:
|#||p1||p2||p3||¬p3||¬p3 ∧ p1||p3 ∧ p1||(¬p3 ∧ p1) ⊕ (p3 ∧ p1)|
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 p1 ⊕ p2 ⊕ p3. Therefore trunk 1 contains the treasure.Posted