Interesting Esoterica

How to Solve "The Hardest Logic Puzzle Ever" and Its Generalization

Article by Daniel Vallstrom
  • Published in 2022
  • Added on
Raymond Smullyan came up with a puzzle that George Boolos called "The Hardest Logic Puzzle Ever".[1] The puzzle has truthful, lying, and random gods who answer yes or no questions with words that we don't know the meaning of. The challenge is to figure out which type each god is. Various "top-down" solutions to the puzzle have been developed.[1,2] Here a systematic bottom-up approach to the puzzle and its generalization is presented. We prove that an n gods puzzle is solvable if and only if the random gods are less than the non-random gods. We develop a solution using 4.13 questions to the 5 gods variant with 2 random and 3 lying gods. There is also an aside on mathematical vs. computational thinking.

Links

Other information

key
HowtoSolveTheHardestLogicPuzzleEverandItsGeneralization
type
article
date_added
2022-02-16
date_published
2022-09-14

BibTeX entry

@article{HowtoSolveTheHardestLogicPuzzleEverandItsGeneralization,
	key = {HowtoSolveTheHardestLogicPuzzleEverandItsGeneralization},
	type = {article},
	title = {How to Solve "The Hardest Logic Puzzle Ever" and Its Generalization},
	author = {Daniel Vallstrom},
	abstract = {Raymond Smullyan came up with a puzzle that George Boolos called "The Hardest
Logic Puzzle Ever".[1] The puzzle has truthful, lying, and random gods who
answer yes or no questions with words that we don't know the meaning of. The
challenge is to figure out which type each god is. Various "top-down" solutions
to the puzzle have been developed.[1,2] Here a systematic bottom-up approach to
the puzzle and its generalization is presented. We prove that an n gods puzzle
is solvable if and only if the random gods are less than the non-random gods.
We develop a solution using 4.13 questions to the 5 gods variant with 2 random
and 3 lying gods. There is also an aside on mathematical vs. computational
thinking.},
	comment = {},
	date_added = {2022-02-16},
	date_published = {2022-09-14},
	urls = {http://arxiv.org/abs/2201.09801v2,http://arxiv.org/pdf/2201.09801v2},
	collections = {protocols-and-strategies,puzzles,the-act-of-doing-maths},
	url = {http://arxiv.org/abs/2201.09801v2 http://arxiv.org/pdf/2201.09801v2},
	year = 2022,
	urldate = {2022-02-16},
	archivePrefix = {arXiv},
	eprint = {2201.09801},
	primaryClass = {math.GM}
}