论文标题
如何解决“有史以来最难的逻辑难题”及其概括
How to Solve "The Hardest Logic Puzzle Ever" and Its Generalization
论文作者
论文摘要
Raymond Smullyan提出了一个难题，乔治·布洛斯（George Boolos）称之为“有史以来最难的逻辑难题”。[1]这个难题有真实的，撒谎和随机的神灵，他们用我们不知道的含义回答是或否问题。挑战是找出每个神是哪种类型。这个难题吸引了一些普遍的关注 - 例如，一个流行的难题介绍已经被观看了1000万次。[2]已经开发了各种“自上而下”的解决方案。[1,3]在这里提出了系统的自下而上的拼图方法，并提出了其概括。我们证明，当且仅当随机神小于非随机神灵的情况下，对于任意的枢机主教来说，就可以解决n个神的难题。我们使用4.15个问题为5个神灵和2个撒谎的神灵开发解决方案。
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. The puzzle has attracted some general attention -- for example, one popular presentation of the puzzle has been viewed 10 million times.[2] Various "top-down" solutions to the puzzle have been developed.[1,3] 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, for arbitrary cardinals. We develop a solution using 4.15 questions to the 5 gods variant with 2 random and 3 lying gods.
