The full solution of a logical problem is given.
In this note I shall consider the following logical problem.
problem. There is a group of N persons, some of which are reiiafde and the rest are unreliuble being known that the reliable persons are a majority. A reliable person answers only the truth to all questions while an unreliable one answers sometimes the truth and sometimes a lie. A mathematician (not belonging to the group) wants to find out "who is who" in the group. For that he may ask any person about any other one in the group if the latter is a reliable person or not. What is the least number of questions by which he can find out for sure who is who in the group?
Let Q(N) be the least number of questions. The first upper bound, Q(N) s 2N-3, was obtained (I believe so) by Konyagin, the author of the problem. A little later I could prove the estimate Q(N) s [$(N -l)]. After that another proof of this estimate was found by Shlosman. As concerns the lower bound, Ruzsa proved that Q(N) 3 [#N -3)] and Galvin improved his result to the following: If NH, then if N=O (mod 61, otherwise (private communications). The purpose of this note is to prove the following result. ' Theorem. Q(N) = [$(N -I)], N 2~ 3.
Let at first N be odd, N = 2k + 1. We must prove that Q(av) = 3k. For that we shall prove at first that Q(N) 6 3k and next that Q(N) > 3k. As a matter of fact at the first stage we shall give an algorithm which solves the problem for 3k