Образователни технологии
PROBLEM 3 ON THE IMO’2019 PAPER
Резюме. The aim of the present note is to discuss Problem 3 on the IMO’2019 paper. The \(60^{\text {th }}\) edition of the International Mathematical Olympiad (IMO) took place in the city of Bath, United Kingdom, 11–22 July 2019, with the participation of 621 students from 112 countries. The event is the most prestigious scientific Olympiad for high school students. Problem 3 is one of the difficult ones on the paper. It was solved fully (7 points) by 28 participants, 4 students were marked with 6 points, 9 with 5 points, 5 with 4 points, 6 with 3 points, 3 with 2 points, 46 with 1 point and 520 with 0 points. The mean result of all the 621 participants in the Olympiad is 0, 572, which shows the high level of the problem difficulty.
Ключови думи: Olympiad; problem solving; graph; vertex; edge; connectivity; complete graph
The problem under consideration is the following:
A social network has 2019 users, some pairs of whom are friends. Whenever user \(A\) is friends with user \(B\), user \(B\) is also friends with user \(A\). Events of the following kind may happen repeatedly, one at a time: Three users \(A, B\), and \(C\) such that \(A\) is friends with both \(B\) and \(C\), but \(B\) and \(C\) are not friends, change their friendship statuses such that \(B\) and \(C\) are now friends, but \(A\) is no longer friends with \(B\), and no longer friends with C. All other friendship statuses are unchanged. Initially, 1010 users have 1009 friends each, and 1009 users have 1010 friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.
We are going to use the obvious interpretation of the problem by graphs, whose vertices are the users, while the edges between the vertices are the friends between the corresponding users. A graph is connected when it has at least one vertex and there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is called disconnected. A graph \(G\) is therefore disconnected if there exist two vertices in \(G\) such that no path in \(G\) has these vertices as endpoints.
A particular case of a connected graph is the so called complete graph, every pair of whose distinct vertices is connected by a unique edge. The complete graph with \(n\) vertices is denoted by \(K_{n}\). In Graph theory , the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex. A vertex is called to be even if the number of the incident edges is even. Analogously, a vertex is called to be odd if the number of the incident edges is odd. An adjacent vertex of a vertex \(v\) in a graph is a vertex that is connected to \(v\) by an edge. In the sequel the event from the IMO problem will be called operation.
Let \(G\) be the graph in the IMO problem. Note that the vertices of \(G\) may be grouped in two groups. One of them contains 1010 vertices, and each vertex of this group is adjacent to 1009 vertices. The remaining 1009 vertices belong to the second group. Each of them is adjacent to 1010 vertices.
Lemma 1. \(G\) has odd vertices.
Proof: The vertices which have 1009 adjacent vertices each are with odd de grees and consequently they are odd.
Lemma 2. \(G\) is a connected graph.
Proof: Consider a vertex \(X\) with 1009 adjacent vertices \(A_{1}, A_{2}, \ldots, A_{1009}\). It is clear, that the set, which contains \(X\), the vertices \(A_{1}, A_{2}, \ldots, A_{1009}\) and the edges that connect them with \(X\), represents a connected graph. In this case we have the so called subgraph of the given graph. Let \(Y \in G\) be a vertex of the graph, different from \(X\). It is adjacent to 1009 or 1010 vertices. Let its adjacent vertices be 1009. Denote them by \(B_{1}, B_{2}, \ldots, B_{1009}\). Consider the subgraph, which contains \(Y\), the vertices \(B_{1}, B_{2}, \ldots, B_{1009}\) and the edges connecting them with \(Y\). This subgraph is connected too. In total both graphs have \(1010+1010=2020\) vertices and since 2020 > 2019 , they have one common vertex at least. This is sufficient to affirm that \(G\) is connected. In the second case let all the 1010 adjacent vertices of \(Y\) be \(B_{1}, B_{2}, \ldots, B_{1010}\). We may consider a third graph, which contains \(Y\), the vertices \(B_{1}, B_{2}, \ldots, B_{1010}\) and the edges that connect them with \(Y\). It is connected too. Now, this graph together with the first one is connected again and in total it has \(1010+1011=2021\) vertices. But \(2021 \gt 2019\) and the two subgraphs have a common vertex again. Thus, \(G\) is connected.
Lemma 3. \(G\) is a complete graph.
Proof: It follows directly from the problem condition. More, for a \(1011 \leq n \leq 2019\) the graph \(G\) does not contain a subgraph with \(n\) vertices, which is \(K_{n}\), i.e, which is a complete graph. For example, if we assume that \(G_{1011}\) is a subgraph of \(G\), which is \(K_{1011}\), then all its 1011 1 vertices (which are more than 1009) have 1010 neighbors each and this contradicts the problem condition. Also, all its 1011 vertices (which are more than 1010) have 1010 neighbors (which are more than 1009) and again this contradicts the problem condition. The reasoning is analogous for all \(1011 \lt n \leq 2019\).
Lemma 4. The parity of the vertices of \(G\) is invariant with respect to the operation under consideration (i.e. with respect to the events from the problem conditions).
Proof: The scheme below shows what happens after the realization of the operation under consideration on the triplet (\(B, A, C\) ) : the degree of \(A\) decreases by 2, while the degrees of \(B\) and \(C\) remain unchanged.
A graph is called to be solvable if by consecutive operations it could be reduced to a graph, whose vertices are with degrees not greater than 1.
Statement. If a graph \(G\) is connected and has a vertex of degree 1, then it is solvable.
Proof: Assume that the statement is false and consider the set of all connected graphs with a vertex of degree 1 each and such that the statement is false for each of them. Consider the graph in the set with minimal number of edges and denote it by \(M\). Let \(A\) be a vertex in \(M\) of degree 1 and let \(B\) be the vertex with which \(A\) is connected. Let (additionally to \(A) C_{1}, C_{2}, \ldots, C_{k}\) be the remaining neighbor vertices of \(B\).
Case 1. It exists such an edge \(B C_{i}(1 \leq i \leq k)\), that the graph remains connected after deleting this edge. In this case, if we apply the operation on the triplet \(\left(A B C_{i}\right)\) and if we delete the edge, we will obtain a graph with less edges, which will be connected and will have a vertex of degree 1 (it is the vertex \(A\) ). The new graph is solvable because otherwise the condition for the chosen graph \(M\) to be minimal will be violated. Since the new graph is solvable, the initial one \(G\) will be solvable too and this is a contradiction already.
Case 2. If the condition of case 1 is not verified, then let \(F_{i}(1 \leq i \leq k)\) be a subgraph, which contains \(C_{i}\) and all vertices connected with \(C_{i}\). It is clear that \(F_{i}\) is a connected graph, which contains \(B\) but it does not contain \(C_{j}\) for all \(j \neq i\) (because of the case we are considering). Note that \(B\) is of degree 1 in \(F_{i}\). Consequently \(F_{i}\) is solvable because \(M\) is minimal. Solve \(F_{i}\) consecutively for all \(1 \leq i \leq k\). It turns out that \(G\) is solvable and this contradicts the assumption.
We are ready to present the solution of the IMO problem.
Solution of the IMO problem. Similarly to the proof of the above statement, consider the set of the connected and not complete graphs with 2019 vertices with an odd edge each and such that the assertion is not true for all of them. Take the graph \(M\) with minimal number of edges. Let \(A\) be an odd vertex assuming that it is of degree 3 at least.
Case 1. Let each pair of neighbor vertices of \(A\) be connected by an edge.
\(M\) is connected but it is not complete and consequently there exists a vertex \(B\), which is at a distance 2 edges from \(A\), for example the edges \(A C\) and \(B C\). Apply the operation on the triplet (\(A, C, B\) ) (see the figure). The graph remains connected and consequently it is solvable, which contradicts the assumption.
Case 2. Let \(B\) and \(C\) be neighbors of \(A\), which are not connected by an edge (see the first figure). Connect them (see the second figure), applying the operation on the triplet (\(B, A, C\) ) . The vertices \(B\) and \(C\) induce (considered together with their connecting edges) a connected subgraph. If it does not contain \(A\), then consider the remaining part that contains \(A\) (see the third figure). If it contains \(A\) (see the fourth figure), consider the whole graph (without the deleted edges \(A B\) and \(A C\), of course). In both cases the problem is reduced to the consideration of a connected graph with vertex \(A\), which is odd according to lemma 4 and we may repeat the reasoning from case 1 and case 2 depending on the situation.
REFERENCES
Rosen, Kenneth H. (2011). Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill (ISBN 978-0-07-338309-5).
Biggs, N., Lloyd, E. & Wilson, R. (1986). Graph Theory. Oxford University Press, pp. 1736 – 1936.
Tutte, W. T. (2001). Graph Theory. Cambridge University Press, p. 30 (ISBN 978-0-521-79489-3), retrieved 2016-03-14.
Grozdev, S. (2007). For High Achievements in Mathematics: The Bulgaria Experience (Theory and Practice). Sofia: ADE (ISBN 978-954-92139-1-1).