XXXIII OM - III - Problem 1

Indicate such a way of arranging $ n $ girls and $ n $ boys around a round table so that the number $ d_n - c_n $ is maximized, where $ d_n $ is the number of girls sitting between two boys, and $ c_n $ is the number of boys sitting between two girls.
Consider any arrangement of $ n $ girls and $ n $ boys. Let's call a group of $ k $ girls (for $ k > 1 $) any sequence of $ k $ girls sitting next to each other, if the first and the $ k $-th girl in this sequence are seated next to a boy at the table. Let $ D_n $ be the number of groups of girls in a given arrangement. Similarly, we define a group of $ k $ boys. Let $ C_n $ be the number of groups of boys. Since every group of girls is adjacent to a group of boys or a single boy, and every group of boys is adjacent to a group of girls or a single girl, we have

\[
D_n = C_n
\]

If $ D_n = 0 $, then each girl is adjacent to two boys, which implies that each boy is adjacent to two girls, so $ C_n = 0 $ and $ d_n - c_n = 0 $. If, however, $ D_n \geq 1 $, then from the equality (*), we get

\[
d_n - c_n = \left[ \frac{n}{2} \right] - 1
\]

On the other hand, $ C_n $ is the number of groups of boys, and each group contains at least two boys, so $ C_n \leq \frac{n}{2} $. Moreover, $ C_n $ is an integer, so $ C_n \leq \left[ \frac{n}{2} \right] $. Therefore,

\[
d_n - c_n \leq \left[ \frac{n}{2} \right] - 1
\]

for any arrangement of $ n $ girls and $ n $ boys.
We will now show an arrangement where $ d_n - c_n = \left[ \frac{n}{2} \right] - 1 $. If $ n = 2k $, we seat two boys, one girl, two boys, one girl, and so on, finally the last two boys and the remaining girls. In this arrangement, $ k - 1 $ girls have boys on both sides, while no boy has two female neighbors.
If $ n = 2k + 1 $, we seat similarly: two boys, one girl, two boys, one girl, and so on, finally the last three boys and the remaining girls. In this situation, $ k - 1 $ girls sit between two boys, and no boy has two female neighbors.
Therefore, the maximum value of $ d_n - c_n $ is $ \left[ \frac{n}{2} \right] - 1 $.