40th Hellenic Mathematical Olympiad

We will prove that the maximum value is 13. Indeed, if the set contains 14 students, because they sit in 13 desks, from the Pigeonhole Principle, there will be two students who sat in the same desk. Therefore the maximum value is at most 13.

Figure 4

For the other direction, we will prove that no matter how the students sat in the two terms, we can find a total of 13 students so that no two sat together during the year.

Indeed, we represent the students as points on the plane and join them with a red line segment if they sat together in the first term and with a black one if they sat together in the second term. Suppose there is a circle consisting of an odd number of segments. Then each vertex is connected by a black and a red segment (with the two neighbors in the circle). Therefore, if we start with red, since the number of segments is odd, we will end up with red again.

This is absurd, since each vertex is connected to a red (for the first term) and a black (for the second term) line segment.

Since there is no odd cycle, this means that the set of vertices can be divided into two subsets $A$, $B$ such that there are no segments between vertices in set $A$ and no segments between vertices in set $B$.

Since the students are 26, there is one set with cardinality at least 13, and the result follows.

Figure 5

---

Alternative solution.

As in the first solution, $N\le 13$ is immediate from the Pigeonhole Principle. We will show that the equality holds.

We consider a graph of twenty six vertices, which correspond to the students, with an edge between two vertices if and only if the corresponding students have sat together in the first or second term.

Each connected component has an even number of vertices, since students sit in pairs in each term. Otherwise, there would be some student sitting alone in some term, absurd.

Since students sit with two different classmates throughout the year, one in each term, each vertex is of degree 2. So each connected component is an Euler cycle. Indeed, if we start moving from a vertex passing through each edge only once, due to the degree of each vertex being 2, we should end up at the vertex we started from.

It suffices, then, to consider each connected component as a directed cycle $v_1,v_2,...,v_{2k}$ and consider the half vertices alternately, i.e. $v_{2v_1},v_{2v_2},...,v_{2v_{2k}}$, which are not connected by an edge. Since from each component we take half the vertices, $N=13$.

In the example below, our graph has four coherent components. We can simply select all green or all yellow vertices.

Figure 6