Browse · MathNet
Print2025 International Mathematical Olympiad China National Team Selection Test
China 2025 counting and probability
Problem
Let be an integer. Two players, Alice and Bob, play the following game: Initially all edges of the complete graph are uncolored. They take turns coloring edges red, with Alice starting first. In each move, a player selects one or two uncolored edges to color red, with the constraint that after each move, no three vertices can have all three edges between them colored red. The game ends when no more edges can be colored. Prove that there exists a real number such that for any integer , no matter how Bob plays, Alice can ensure that at the end of the game, the number of red edges does not exceed .
Solution
We consider the graph formed by red edges. Initially, is an empty graph on vertices, and the condition requires that remains triangle-free throughout the game.
Step 1: We show that if at Alice's turn, has 24 isolated vertices, then Alice can create a 5-cycle among these vertices in four moves. Let be the set of these 24 isolated vertices. Alice first selects three vertices and colors and red. After Bob's move, still contains at least 17 isolated vertices. Alice then selects two isolated vertices and colors and red. After Bob's move, has at least 11 isolated vertices remaining. Alice then selects two more isolated vertices and colors and red.
Consider the four edges , , , and , which are currently uncolored. After Bob's move, at least one of them remains uncolored, say . Now still has at least 5 isolated vertices. Alice selects one of them, , and colors and red. This creates a 5-cycle in . By following this strategy, after four moves by each player, the number of isolated vertices in decreases by at most 24.
Step 2: Alice follows the strategy described in Step 1. After moves, she can ensure that contains disjoint 5-cycles. Alice then colors edges arbitrarily until becomes a maximal triangle-free graph.
We now estimate the number of edges in . Let , and denote the disjoint 5-cycles by . Between any two cycles and , there are at most 10 edges. For each vertex not in any , there are at most 2 edges from to each . The remaining vertices outside all can have at most edges between them (by Turán's theorem). The cycles themselves contribute edges. Thus, the total number of edges is bounded by:
Taking satisfies the requirement.
Step 1: We show that if at Alice's turn, has 24 isolated vertices, then Alice can create a 5-cycle among these vertices in four moves. Let be the set of these 24 isolated vertices. Alice first selects three vertices and colors and red. After Bob's move, still contains at least 17 isolated vertices. Alice then selects two isolated vertices and colors and red. After Bob's move, has at least 11 isolated vertices remaining. Alice then selects two more isolated vertices and colors and red.
Consider the four edges , , , and , which are currently uncolored. After Bob's move, at least one of them remains uncolored, say . Now still has at least 5 isolated vertices. Alice selects one of them, , and colors and red. This creates a 5-cycle in . By following this strategy, after four moves by each player, the number of isolated vertices in decreases by at most 24.
Step 2: Alice follows the strategy described in Step 1. After moves, she can ensure that contains disjoint 5-cycles. Alice then colors edges arbitrarily until becomes a maximal triangle-free graph.
We now estimate the number of edges in . Let , and denote the disjoint 5-cycles by . Between any two cycles and , there are at most 10 edges. For each vertex not in any , there are at most 2 edges from to each . The remaining vertices outside all can have at most edges between them (by Turán's theorem). The cycles themselves contribute edges. Thus, the total number of edges is bounded by:
Taking satisfies the requirement.
Techniques
Turán's theoremColoring schemes, extremal argumentsGames / greedy algorithms