IMC 2013 · Day 1 · P3

We prove that for any $n \ge 2$ the answer is 6.

First we show that less than 6 trips is not sufficient. In that case the total quantity of students in all trips would not exceed $5n$. A student meets $n - 1$ other students in each trip, so he or she takes part on at least 3 excursions to meet all of his or her $2n - 1$ schoolmates. Hence the total quantity of students during the trips is not less then $6n$ which is impossible.

Now let's build an example for 6 trips.

If $n$ is even, we may divide $2n$ students into equal groups $A$, $B$, $C$, $D$. Then we may organize the trips with groups $(A, B)$, $(C, D)$, $(A, C)$, $(B, D)$, $(A, D)$ and $(B, C)$, respectively.

If $n$ is odd and divisible by 3, we may divide all students into equal groups $E$, $F$, $G$, $H$, $I$, $J$. Then the members of trips may be the following: $(E, F, G)$, $(E, F, H)$, $(G, H, I)$, $(G, H, J)$, $(E, I, J)$, $(F, I, J)$.

In the remaining cases let $n = 2x + 3y$ be, where $x$ and $y$ are natural numbers. Let's form the groups $A$, $B$, $C$, $D$ of $x$ students each, and $E$, $F$, $G$, $H$, $I$, $J$ of $y$ students each. Then we apply the previous cases and organize the following trips: $(A, B, E, F, G)$, $(C, D, E, F, H)$, $(A, C, G, H, I)$, $(B, D, G, H, J)$, $(A, D, E, I, J)$, $(B, C, F, I, J)$.