Problem 1025
Twenty-five mathematicians attend a performance.The highlight of the show is when the mage must guess integer numbers, between 0 and 1025 inclusive, that mathematicians have chosen between them before the show starts.
To find each of these numbers, the mage must ask questions, one at most by mathematician, to which the only answers allowed are "yes" or "no".
- 1A. What minimum number of questions does the mage have to ask to be certain of finding the first number, knowing that the mathematicians questioned must tell the truth?
For the second number, it is agreed that one of the mathematicians will lie if he is questioned, the others telling the truth. But the mage does not know which one, or if he is one of the mathematicians questioned!
- 2A. What is the minimum number of questions the mage must ask to be certain of finding the second number?
The problem that generated the most confusion after the 1021. The authors have been clearly wrong, not considering two solutions better than that proposed: one in information theory respecting the spirit of the problem, and a purely logical. About me, having had the same idea as the authors, I am satisfied that they have counted as correct these 3 answers.
For the solution under consideration (Hamming coding), I have only made a program that experimentally verifies the property exhaustively (corruption of all bits for all possible words).
The code is here.
For the solution under consideration (Hamming coding), I have only made a program that experimentally verifies the property exhaustively (corruption of all bits for all possible words).
The code is here.
- 1A. 11.
- 2A. 15 (the answers 11 and 14 have yet been accepted).
Remark from the authors:
Readers have reported an algorithm (Pelc) giving the answer 14, and thus seeming more efficient than the above solution (Hamming). Others, using an analogy with the enigma of the two doors, answered 11. These strategies are based on additional hypotheses not foreseen by the authors. But to the extent that they are not contradictory with the statement, they have been retained.