Maths Olympiad Prep

Library / /397 of 520

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it

Prove that the for all n>1000n>1000, we can arrange the number 1,2,,(n2)1,2,\dots, \binom{n}{2} on edges of a complete graph with nn vertices so that the sum of the numbers assigned to edges of any length three path (possibly closed) is not less than 3n1000log2log2n3n-1000log_2log_2 n.

Solution

To prove that for all n>1000 n > 1000 , we can arrange the numbers 1,2,,(n2) 1, 2, \dots, \binom{n}{2} on the edges of a complete graph with n n vertices so that the sum of the numbers assigned to the edges of any length three path (possibly closed) is not less than 3n1000log2log2n 3n - 1000 \log_2 \log_2 n , we can proceed as follows:

1. Split the vertices into two sets:
Let A A and B B be two sets such that 0AB1 0 \leq |A| - |B| \leq 1 . Specifically, let A=n2 A = \lceil \frac{n}{2} \rceil and B=n2 B = \lfloor \frac{n}{2} \rfloor . This ensures that the sizes of A A and B B are as balanced as possible.

2. Assign numbers to edges between sets:
For any edge e=xy e = xy where xA x \in A and yB y \in B , assign an integer less than or equal to AB=n24 |A||B| = \lfloor \frac{n^2}{4} \rfloor . This means that the edges between the two sets A A and B B will have the smallest numbers assigned to them.

3. Assign remaining numbers to other edges:
Assign any of the remaining values to all the other edges, i.e., the edges within set A A and within set B B .

4. Analyze the sum of numbers in any triangle:
Consider any triangle in the graph. At least one of the edges of the triangle must join two vertices that are either both in A A or both in B B . The number assigned to this edge is at least AB+1=n24+1 |A||B| + 1 = \lfloor \frac{n^2}{4} \rfloor + 1 .

5. Compare with the required bound:
Since n24+1 \lfloor \frac{n^2}{4} \rfloor + 1 is a lower bound for the sum of the numbers assigned to the edges of any triangle, we need to show that this is greater than or equal to 3n1000log2log2n 3n - 1000 \log_2 \log_2 n .

6. Verify the inequality:
n24+1>3n1000log2log2n \lfloor \frac{n^2}{4} \rfloor + 1 > 3n - 1000 \log_2 \log_2 n
For large n n , n24 \frac{n^2}{4} grows much faster than 3n 3n and 1000log2log2n 1000 \log_2 \log_2 n . Therefore, for n>1000 n > 1000 , the inequality holds true.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.