[Algorithm Theory (Miscellaneous).]

A journalist has come to a company of $\mathrm{N}$ people. He knows that in this company there is a person $\mathrm{Z}$ who knows all the other members of the company, but no one knows him. The journalist can ask each member of the company the question: "Do you know so-and-so?" Find the smallest number of questions sufficient to definitely find Z. (Everyone answers the questions truthfully. One person can be asked multiple questions.)

#
Can anything be said about the members of company A and B if A knows B (if A does not know B)?

## Solution

To directly determine that a person $\mathrm{Z}$, one needs to ask $2 *(\mathrm{~N}-1)$ questions: $\mathrm{N}-1$ to the person themselves (whether they know each member of the company) and N-1 to the other members of the company (whether they know the person). Clearly, this approach is unlikely to be optimal. Let's consider the method of elimination. It is obvious that there can only be one $\mathrm{Z}$ in the company. Suppose the journalist asks A whether he knows B. Then, if A does not know B, A is not Z; if A knows B, B is not Z. Thus, with each question, regardless of the answer, the journalist reduces the pool by one person. It is clear that he will manage to do so in N-1 questions, as it is sufficient to eliminate N-1 people, and the remaining one will be $\mathrm{Z}$.

## Answer

$\mathrm{N}-1$.