Liars and the group \((\mathbb{Z}_2)^n\) (Q2036226)

There is a magic trick where the magician presents a set \(\mathbb{A}\) consisting of \(2^n\) numbers to a spectator, who chooses secretly one of the numbers. The magician then asks the spectator \(n\) questions which she must answer truthfully. From this, the magician can determine the number that the spectator has chosen. In an extended scenario with \(|\mathbb{A}| = 2^{n-1}\), the spectator can secretly decide whether to always tell the truth or always lie. In this article, a further generalisation is presented. Here, the spectator is allowed to choose her response behaviour from a given set \(\mathbb{L}\) of lying scenarios, for example, she can lie exactly once in five questions except for the last question. The magician can now determine the chosen number using simple operations of the group \((\mathbb{Z}_2)^n\). The article establishes relations between \(|\mathbb{A}|\) and \(|\mathbb{L}|\) that allow the chosen number to be determined unambiguously. The article is easy to understand for anyone who has a basic knowledge of group theory.