Maths Olympiad Prep

Library / /2 of 2

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Turkey

In a country between each pair of cities there is at most one direct road. There is a connection (using one or more roads) between any two cities even after the elimination of any given road. We say that the city AA can be kk-directionally connected to the city BB, if: we can orient at most kk roads such that after arbitrary orientation of remaining roads for any fixed road LL (directly connecting two cities) there is a path passing through roads in the direction of their orientation starting at AA, passing through LL and ending at BB. Suppose that in a country with nn cities, any two cities can be kk-directionally connected. What is the minimal value of kk? (Azer Kerimov).

Solution

The answer is: k=2n3k = 2n - 3. If all pairs of cities are directly connected (complete graph) then all roads from AA and all roads to BB must be oriented: k(n1)+(n1)1=2n3k \ge (n-1) + (n-1) - 1 = 2n - 3 or if deg(A)=deg(B)=n1\deg(A) = \deg(B) = n - 1, all other vertices have degree 22, then again we have to orient all 2(n2)+1=2n32(n-2) + 1 = 2n - 3 roads. Now we prove that by orienting of at most 2n32n - 3 roads the existence of a required road for any fixed road LL can be guaranteed. We say that a path containing not oriented roads A1A2,A2A3,,Al1AlA_1A_2, A_2A_3, \dots, A_{l-1}A_l is minimal, if there is no road AlAjA_lA_j with 1i,jl,ij11 \le i, j \le l, |i - j| \ne 1. At the first stage we orient all roads belonging to the minimal path Γ1\Gamma_1 without self-intersections starting at AA and ending at BB: Γ1={A1A2,A2A3,,Al1Al}\Gamma_1 = \{A_1A_2, A_2A_3, \dots, A_{l-1}A_l\}, where A=A1,Al=BA = A_1, A_l = B. If Γ1\Gamma_1 includes all cities, then we are done. At the second stage we orient all roads of a minimal path Γ2\Gamma_2 starting at some city B1=Ap1Γ1B_1 = A_{p_1} \in \Gamma_1 and ending at some city Bm=ApmΓ1B_m = A_{p_m} \in \Gamma_1 and including new cities B2,B3,,Bm1B_2, B_3, \dots, B_{m-1} not lying on Γ1\Gamma_1. Such a path exists since our graph is 2-connected: there is a path between any two cities even after the elimination of any given road. We say that a path B1B2,B2B3,,Bm1BmB_1B_2, B_2B_3, \dots, B_{m-1}B_m is stretched, if there is no road AiBjA_iB_j with 1ip111 \le i \le p_1-1 or p2+1ilp_2+1 \le i \le l and 2jm12 \le j \le m-1. In other words, Γ2\Gamma_2 is stretched means that B1B_1 is closer to AA than any other city inside Γ2\Gamma_2 and BmB_m is closer to BB than any other city inside Γ2\Gamma_2. If Γ1\Gamma_1 and Γ2\Gamma_2 contain all cities we are done. If not, at the third stage we orient all roads of some minimal and stretched path Γ3\Gamma_3, starting at some city on Γ1Γ2\Gamma_1 \cup \Gamma_2 and ending at some city lying on Γ1Γ2\Gamma_1 \cup \Gamma_2, including new cities. After qq steps Γ=i=1qΓi\Gamma = \cup_{i=1}^q \Gamma_i will contain all cities. Now any road ll either belongs to some Γi\Gamma_i or connects Γi\Gamma_i to Γj\Gamma_j. If ll belongs to some Γi\Gamma_i, it is already oriented and there is a path starting at AA passing through ll and ending at BB. Indeed, let lΓsl \in \Gamma_s. This path has two parts, first part connecting AA with ll and the second part, connecting ll with BB. In order to get the first part, we take an edge ll and go back through oriented edges Γs\Gamma_s till the first edge of Γs\Gamma_s, then we go back through oriented edges of some other Γi\Gamma_i having intersection with Γs\Gamma_s (ii is not necessarily equal to s1s-1), and so on until getting AA. In order to get the second part, we take an edge ll and go through oriented edges Γs\Gamma_s till the first edge of Γs\Gamma_s, then we go through oriented edges of some other Γi\Gamma_i having intersection with Γs\Gamma_s (ii is not necessarily equal to s+1s+1), and so on until getting BB. This paths pass only through roads oriented at stages 1, 2, ..., qq. Now suppose that ll does not belong to i=1qΓi\cup_{i=1}^q \Gamma_i and somehow oriented, say it connects a city CΓiC \in \Gamma_i and DΓjD \in \Gamma_j. Then the required path again has two parts, first part connecting AA with CC and the second part connecting DD with BB. We get these parts as in the first case. It can be readily checked that since constructed paths Γ1,,Γq\Gamma_1, \dots, \Gamma_q are minimal and stretched, the required path is correctly defined.
Now we note that the total number of roads oriented at stages 1, 2, ..., qq is at most 2n32n - 3. Indeed, suppose that at some stage we draw a path Γi\Gamma_i including ll new cities. Then the number of oriented roads is l+1l + 1. Thus, the total number of oriented roads is maximal if Γ1\Gamma_1 includes one road and each other Γi\Gamma_i included two roads as in the second example constructed above. In this case the total number of oriented roads is 2n32n - 3. Done.

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.