Maths Olympiad Prep

Library / /8 of 8

Combinatorics Difficulty 9.1 IMO level Prove it Balkan Mathematical Olympiad

A social network has 20252025 users. Two different users are either friends or not friends. A user is considered lonely if they have no friends. Initially, there are no lonely users, and two users Alice and Bob are not friends. A user may swap all their friends, meaning if they were friends with someone before the swap, they are no longer friends, and vice versa. Must there exist a way to arrange the 20252025 users in a sequence so that if, one-by-one in that sequence, each user swaps their friends, no user is ever lonely at any point during the process?

Solution

Let a longest path of the graph be P=V1V2VkP = V_1V_2 \dots V_k.

Case 1: PP consists of all vertices and there is no edge between V1V_1 and VkV_k.
Swap vertices ViV_i increasing ii from 11 to kk. V1V_1 and VkV_k will never be lonely, as they will connect after the first swap and disconnect after the last swap. Vertex ViV_i for 2ik12 \le i \le k-1 will never be lonely as it will be connected to Vi+1V_{i+1} before it is swapped and to Vi1V_{i-1} after it is swapped (because Vi1V_{i-1} was swapped before).

Case 2: PP consists of all vertices and there is an edge between V1V_1 and VkV_k.
Thus V1V2VkV1V_1V_2 \dots V_kV_1 is a cycle that contains all vertices. As the graph is not complete, there exist 22 vertices which are not connected, VaV_a and VbV_b (a<ba < b). Swap VaV_a, then ViV_i for a+1ib1a+1 \le i \le b-1 (one path from VaV_a to VbV_b along the cycle), then ViV_i for a1,a2,,1,n,n1,,b+1,ba-1, a-2, \dots, 1, n, n-1, \dots, b+1, b (the other path along the cycle). VaV_a and VbV_b will be connected during the procedure. For other vertices, the same argument as in Case 1 holds (they are always connected to at least one of the 22 neighbours on the cycle).

Case 3: PP does not contain all vertices.
Notice that PP must contain at least 33 vertices, because otherwise every vertex would have a degree of 11, which is impossible because the number of vertices is odd.
Any swap ordering in which we swap first V1V_1, last VkV_k, other vertices ViV_i in increasing order doesn't cause any vertices besides possibly V1V_1 and VkV_k to be lonely. For internal vertices ViV_i the same argument from Case 1 holds. Vertices outside of PP are not connected to V1V_1 and VkV_k (otherwise, the longer path would exist). As we swap V1V_1 first and VkV_k last, they will be connected to V1V_1 before their swap and to VkV_k after.
If PP contains at least 44 vertices, then if we swap V1V_1, then V2V_2, then vertices outside of PP, then remaining vertices of PP, we notice that V1V_1 and VkV_k will always be connected to some vertex outside PP or to their respective neighbors on PP.
If PP contains 33 vertices, then we swap V1V_1, then one of the outside vertices, then V2V_2, then the remaining outside vertices, then VkV_k. Similarly to above, V1V_1 and VkV_k will always be connected either to their neighbour in PP or to some outside vertex.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.