. Yesterday, $n \geq 4$ people sat around a round table. Each participant remembers only who his two neighbours were, but not which one sat on his left and which one sat on his right. Today, you would like the same people to sit around the same round table so that each participant has the same two neighbours as yesterday (it is possible that yesterday's lefthand side neighbour is today's right-hand side neighbour). You are allowed to query some of the participants: if anyone is asked, he will answer by pointing at his two neighbours from yesterday.

(a) Determine the minimal number $f(n)$ of participants you have to query in order to be certain to succeed, if later questions must not depend on the outcome of the previous questions. That is, you have to choose in advance the list of people you are going to query, before effectively asking any question.

(b) Determine the minimal number $g(n)$ of participants you have to query in order to be certain to succeed, if later questions may depend on the outcome of previous questions. That is, you can wait until you get the first answer to choose whom to ask the second question, and so on.

#
(a) $f(n)=n-3$.

- Asking $n-4$ questions is not enough since the $n-4$ people queried might be sitting in a consecutive string, in which case the $n-4$ answers allow one to sit $n-2$ people in the same positions as yesterday, but there is still an ambiguity among the two remaining ones.
- Let us show that $n-3$ questions suffice. Among the 3 people who are not queried, at least 2 must sit next to people who have been queried. If exactly 2 do, then both these people must be neighbours of the third, so that the neighbours of everybody are known and we are done. If all 3 unqueried people sit next to a queried person, then at least one of them has two queried neighbours, and again it follows that the neighbours of everybody are known, so that we are done.

(b) $g(n)=n-1-\left\lceil\frac{n}{3}\right\rceil\left(=n-1-\left\lfloor\frac{n+2}{3}\right\rfloor=\left\lfloor\frac{2 n}{3}\right\rfloor-1=\left\lceil\frac{2 n-5}{3}\right\rceil\right)$.

Say there is a link between two people if and only if they are neighbours. There are in total $n$ links, which we all need to identify. By asking a person for his neighbours, we can discover at most two new links. More precisely, if at any point we query a participant who has not yet been pointed as a neighbour, we discover exactly two new links (we call this a type-0 query). If we query a participant who has been pointed once as a neighbour, will discover exactly one new link (we call this a type-1 query). Of course, querying a participant who has already been pointed twice provides no information (and we assume in the rest of this solution that it never happens).

First note that, since $f(4)=1$, we also have $g(4)=1$. We now prove the formula for $g(n)$ for $n \geq 5$.

- Let us show that $n-1-\left\lceil\frac{n}{3}\right\rceil$ questions suffice. Our strategy consists in making sure that the first $\left\lceil\frac{n}{3}\right\rceil$ queries are type-0. Let us show that this is always possible. A type-0 query requires a participant that hasn't been queried or pointed before. Since the number of those participants decreases by three at most after each query, we see that it is always possible to perform $\left\lceil\frac{n}{3}\right\rceil$ type- 0 queries first. During this phase we discover $2\left\lceil\frac{n}{3}\right\rceil$ links.

The remaining queries will be either type- 0 or type-1, and each of them discovers at least one new link. We perform them until $n-1$ links have been discovered, after which we are done (the last link can be deduced without query). The number of queries in this second phase is therefore at $\operatorname{most}^{1} n-1-2\left\lceil\frac{n}{3}\right\rceil$, and the total is at most $\left\lceil\frac{n}{3}\right\rceil+\left(n-1-2\left\lceil\frac{n}{3}\right\rceil\right)=n-1-\left\lceil\frac{n}{3}\right\rceil$.

- We now show that $n-2-\left\lceil\frac{n}{3}\right\rceil=\hat{g}(n)$ questions are not enough.

(i) Consider the pool of unqueried and unpointed participants ; each type-0 must query this pool. Since, from the point of view of the questioner, all elements of the pool are undistinguishable, we can assume that each type-0 query asks the second leftmost participant in the pool (except if there is only one element left in the pool). One can then check that the pool, which starts as a string of $n$ contiguous participants, will stay contiguous after each type- 0 and type1 query. Furthermore, using our assumption, we see that each type-0 query removes three participants from the pool. Therefore there can be at most $\left\lceil\frac{n}{3}\right\rceil$ type-0 queries in the scenarios corresponding to our assumption.

(ii) Assume there are $k$ type- 0 queries. Since there are $\hat{g}(n)$ queries, the number of discovered links is equal to $2 k+(\hat{g}(n)-k)=\hat{g}(n)+k=n-2+k-\left\lceil\frac{n}{3}\right\rceil$. If $k$ is strictly less than $\left\lceil\frac{n}{3}\right\rceil$, we discover strictly less than $n-2$ links, which is clearly insufficient (indeed, there are at least three missing links, and one can check that whatever the configuration of the missing links, there are always several orders compatible with the discovered links).

(iii) We now analyze the remaining case with $k=\left\lceil\frac{n}{3}\right\rceil$ type-0 queries ${ }^{2}$, in which we discover $n-2$ links. On the one hand, if the missing links are disjoint, there are always two orders compatible with the discovered links (for example when $n=7$ and links are missing between the $(4,5)$ and $(7,1)$ pairs of neighbours, the two orders are $1-2-3-4 \quad 5-6-7$ and $1-2-3-4 \quad 7-6-5)$. On the other hand, a situation where the two missing links would be adjacent would allow the identification of the correct order. However, this never happens in the scenarios corresponding to the assumption we made in (i). Indeed, two adjacent missing links imply that some participant is unqueried and unpointed at the end of the process. Since we perform $k=\left\lceil\frac{n}{3}\right\rceil$ type-0 queries (the maximum), the reasoning from (i) shows that the pool of unqueried and unpointed participants is empty at the end of the process, which contradicts the existence of two adjacent missing links.[^0]


[^0]:    ${ }^{1}$ Here we use the assumption $n \geq 5$, since quantity $n-1-2\left\lceil\frac{n}{3}\right\rceil$ is negative when $n=4$.

    ${ }^{2}$ Note that this cannot happen when $n \in\{4,5,7\}$ since we have $\left\lceil\frac{n}{3}\right\rceil>\hat{g}(n)$ in those cases.