Exercise 5. Seventeen people dine every Saturday evening around a round table.

How many times is it possible to dine if everyone wants to have two new neighbors each time?

What is the result for eighteen people?

Note: This exercise is the same as Exercise 1 (middle school students had to solve 1, high school students 5), but in a less specific case. The proposed solution below is very general, but difficult for an average high school student to access. This exercise was therefore intended to identify students who are best able to tackle formidable Olympic problems.
Solution: The first thing to notice is the following. Let $n$ be the number of guests (17 or 18), and $k$ be the number of dinners; we are interested in a particular guest among the $n$. Knowing that he has two neighbors at each dinner, and that he must never meet the same person more than once, he will therefore meet $2 k$ different people in total. Since there are only $n-1$ people he can meet, we have $2 k \leq n-1$, which means - in both cases - that there are at most 8 possible dinners.

Now let's show that there indeed exist 8 arrangements such that two people are never neighbors more than once. We number the guests and the seats from 0 to $n-1$ (since the table is round, the $(n-1)$-th seat is therefore next to the 0-th), and the arrangements from 1 to 8.

For $n=17$, we can proceed as follows: at the $i$-th dinner, we place the $j$-th person at the $i j$-th seat modulo 17. (The complete scheme of arrangements is presented a bit further down. In a less abstract, but longer and vaguer way, we can say that
on the first Saturday, we place all guests in order; on the second Saturday, we place one out of two; on the third, one out of three; and so on; knowing that when the numbers exceed 17, we "return to 0".) We need to verify two things.

First, let's verify that this is a valid arrangement. Each guest receives one and only one seat, because between 0 and 16, there is one and only one number congruent to a given residue modulo 17. No seat is occupied by two guests: indeed, let $j$ and $j^{\prime}$ be two guests who occupy the same seat at the $i$-th dinner. Then we have $i j \equiv i j^{\prime}(\bmod 17)$, or $17 \mid i j-i j^{\prime}$, or $17 \mid i\left(j-j^{\prime}\right)$. Since 17 is prime and $0<i<17$, $i$ is coprime with 17, so $17 \mid j-j^{\prime}$. Therefore, $j \equiv j^{\prime}(\bmod 17)$, which means $j=j^{\prime}$. And since there are as many seats as guests, all seats are necessarily occupied.

Now let's verify that this is indeed a solution to the problem. Since the difference between the numbers of two adjacent seats is congruent to $\pm 1$ modulo 17, this means that at the $i$-th dinner, the difference between the numbers of two adjacent people is congruent to $\pm i$ modulo 17. The numbers $\pm 1, \pm 2, \ldots, \pm 8$ are all different modulo 17: two given people can therefore be neighbors only once.

We could also have explicitly presented the scheme of arrangements:

| Place $\quad 012345678910111213141516$ |
| :--- |
| 1st dinner 012345678910111213141516 |
| 2nd dinner 024681012141613579111315 |
| 3rd dinner 036912151471013162581114 |
| 4th dinner 048121637111526101415913 |
| 5th dinner 051015381316111649142712 |
| 6th dinner 061217132814391541016511 |
| 7th dinner 071441118155122916613310 |
| 8th dinner 081671561451341231121019 |

and verify that each guest appears once and only once in each row and has different neighbors in each row. But such a solution, although less abstract, would be much more laborious (366 checks to make in total!), and has the drawback of being "parachuted": one can see that it works, but one does not understand very well why it works.

For $n=18$, a possible solution is to start from the previous arrangement and to intercalate the new person each time. Since we already know that the first 17 people are well placed as required, it is enough to ensure that the last person (who, in this case, bears the number 17: this is not an error, as we numbered from 0) has different neighbors each time. We can, for example, place her between 3 and 4 at the first dinner, between 11 and 13 at the second, then between 2 and 5, between 10 and 14, between 1 and 6, between 9 and 15, between 0 and 7, and finally between 8 and 16 at the eighth dinner: each number between 0 and 16 appears at most once in this list. The complete arrangement is therefore as follows:

```
Place \(\quad 01234567891011121314151617\)
    1st dinner 01231745678910111213141516
    2nd dinner 02468101214161357911171315
    3rd dinner 03691215147101316217581114
    4th dinner 04812163711152610171415913
    5th dinner 05101538131176111649142712
    6th dinner 06121713281439171541016511
    7th dinner 01771441118155122916613310
    8th dinner 08171671561451341231121019 .
```