Let $G$ be a complete directed graph with $100$ vertices such that for any two vertices $x,y$ one can find a directed path from $x$ to $y$. a) Show that for any such $G$, one can find a $m$ such that for any two vertices $x,y$ one can find a directed path of length $m$ from $x$ to $y$ (Vertices can be repeated in the path) b) For any graph $G$ with the properties above, define $m(G)$ to be smallest possible $m$ as defined in part a). Find the minimim value of $m(G)$ over all such possible $G$'s.
Problem
Source: China Mathematical Olympiad 2016 Q6
Tags: combinatorics
17.12.2015 14:07
In part a), can vertices $x$ and $y$ be the same vertex.
17.12.2015 15:38
If I am not wrong $x$ and $y$ are distinct.
18.12.2015 17:08
a) First we want to show that there exists a 3-cycle and a 4-cycle involving any vertex we choose. Consider an arbitrary vertex $X$. Partition the remaining vertices into 2 sets $A$ and $B$ as those directed away from and towards $X$, respectively. These sets are nonempty since otherwise there'd be no path originating from/ending at $X$ linked to any other vertex. If all vertices in $A$ are directed away from $B$, then no path from a vertex in $A$ to a vertex in $B$ exists, a contradiction. Otherwise, such a link completes a 3-cycle involving $X$. Now let $C$ be the subset of $A$ of those vertices that are directed towards at least one vertex in $B$. If $|C|\ge 2$, there exists some $c_1, c_2 \in C$ where $c_1$ is directed to $c_2$. Then $X\rightarrow c_1 \rightarrow c_2 \rightarrow B \rightarrow X$ is a 4-cycle. Else, there must be some $a \in A$ such that $a$ is directed to $c$, if not there is no path that directs any element in $A$ besides $c$ to any element in $B$. Then $X\rightarrow a \rightarrow c \rightarrow B \rightarrow X$ is a 4-cycle. It's well-known that any sufficiently large (ie $\ge 6$) number can be expressed as a sum of a positive integer number of 3's and 4's. Hence, suppose there's some path from $x$ to $y$ of length $k(x,y)$, we can first traverse the 3- and 4-cycles from $x$ sufficiently many times to create a path of length $N-k(x,y)$, where $N$ is some huge number, then traverse the path, creating a path of total length $N$ regardless of $x$ and $y$. b) The minimum value is 3. Consider a graph consisting of 2 3-cycles (say $a_1 \rightarrow a_2 \rightarrow a_3 \rightarrow a_1$, and $b_1 \rightarrow b_2 \rightarrow b_3 \rightarrow b_1$), with all the $b_i$'s directed to all the $a_i$'s, all the $a_i$'s directed to everything else, and everything else directed to the $b_i$'s. The edges within "everything else" don't matter. It's not to difficult to check that this works. Clearly $m(G)$ is never 1. Hence it remains to show that $m(G)$ can never be 2.
19.12.2015 17:07
Quote: Hence it remains to show that $m(G)$ can never be 2. In fact,$m(G)$ can be $2$(if fattypiggy123 is right). a)It is well known that a complete digraph is strongly connected if it has a Hamiltonian circuit.The proof is in the link: http://math.stackexchange.com/questions/191943/strongly-connected-directed-clique-hamiltonian-cycle. Now,label the vertices of the cycle with $1,2,...100$ in clockwise order and $1 \rightarrow 2$,$2 \rightarrow 3,...100 \rightarrow 1$,etc. Lemma:For each vertex there exists a cycle of lenght $51$ that contains it. WLOG:The vertex is labeled with $1$.Consider the edge that contains $1$and $51$.If $51\rightarrow1$,then $1,2,...51,1$ is the desired cycle.If not,then $1,51,52,...100,1$ is the desired cycle. Now,from the Frobenius coin problem(https://en.wikipedia.org/wiki/Coin_problem),we have that any arbirtary large number can be presented as $100x+51y$,where $x$ and $y$ are nonnegative integers.Now,let $N$ be huge such that $N,N-1,...N-100$ can be presented as $100x+51y$,then if we want to go from vertex $i$ to vertex $j$(WLOG $i<j$) we go in cycles $51$ and $100$ and make $N-j+i$ edges and then go from $i$ to $j$ in $j-i$. b)First,I will provide an example for $8$ vertices and then induct. For $8$ vertices,the edges go like this:$1\rightarrow2,1\rightarrow3,1\rightarrow4,5\rightarrow1,6\rightarrow1,7\rightarrow1,8\rightarrow1,2\rightarrow3,3\rightarrow4,4\rightarrow2,5\rightarrow6,6\rightarrow7,7\rightarrow5,8\rightarrow5,8\rightarrow6,8\rightarrow7,2\rightarrow8,3\rightarrow8,4\rightarrow8,5\rightarrow2,2\rightarrow6,6\rightarrow3,3\rightarrow7,7\rightarrow4,4\rightarrow5,4\rightarrow6,3\rightarrow5,2\rightarrow7$. So $8$ is our base case. Lemma $1$:If it is possible for some $n>7$,then it is possible for $n+5$. Consider vertex $a$ and let $A$ be the set of vertices $b$ such that $a \rightarrow b$ for any vertex $b$ in $A$,let $B$ be the set of the remaing vertices and let |A|=$n$.Connect vertices in $A$ such that $m(A)=2$(it is possible by the inductive hypothesis).Connect the remaing $4$ vertices $a_1,a_2,a_3,a_4$ such that $a_1 \rightarrow a_2,a_2 \rightarrow a_3,a_3 \rightarrow a_1$ and for all $i=1,2,3$ $a_4\rightarrow a_i$.For every $g$ from $A$,let $g\rightarrow a_4$.Now consider $3$ arbirtary vertices from $A$($a_5,a_6,a_7$) and connect $a_4 \rightarrow a_i$ for $i=5,6,7$.Now,pick another $3$ vertices that are mutualy distinct from $a_5,a_6,a_7$ and name them $a_8,a_9,a_10$ and connect $a_1 \rightarrow a_8,a_8 \rightarrow a_2,a_2 \rightarrow a_9,a_9 \rightarrow a_3,a_3 \rightarrow a_10,a_10 \rightarrow a_1$ and other edges connect arbirtary.It is not hard to prove that this graph also has $m=2$. Lemma $2$:If it is possible for $x$ and $y$,it is possible for $x+y+1$.Pick vertex $a$,let $I$ be the set of the vertices $b$ such that $a\rightarrow b$ and $O$ the set of vertices $b$ such that $b\rightarrow a$.Make subgraphs $I$ and $O$ satisfay $m=2$ and |I|=x and |O|=y.If vertex $a$ is from $I$ and $b$ from $O$,then $a\rightarrow b$.It is not hard to prove this works. Now,from Lemma$1$ and Lemma$2$,it is easy to get that it is possible for $100$. If fattipiggy123 isn't right,then for part b) the proof will be the same expect the answer will be $m=3$.
19.12.2015 20:27
Here's another solution to (b) assuming $x,y$ distinct in the problem. Let the vertices be residues mod 100. For any residue $n$ and any $i \in \{1, 2, \ldots, 49\}$, make a directed edge from $n$ to $n+i$, except reverse it for $i = 25$ so $n+25$ goes to $n$. This means $n$ goes to $n+75$ for all $n$. We have specified the orientation of all edges except those between $n$ and $n+50$, which we just orient arbitrarily (we won't use them). We wish to show for any residues $m,n$ with $m \neq 0$, we can get from $n$ to $n+m$ in two steps. - If $m \in \{2,3,4,\ldots,98\}$, then $m$ can be easily written as a sum of two numbers $m_1, m_2$ among $\{1,2,3,\ldots,24,26,27,28,\ldots,49\}$, so we just do $n \to n+m_1 \to n+m_1+m_2$. - If $m = 1$, then we do $n \to n+75 \to n+75+26$. - If $m = 99$, then we do $n \to n+75 \to n+75+24$. A similar method of construction works for $k$ vertices if $k \geq 11$. Direct $n$ to $n+i$ when $i \in \{1,2,\ldots,\lfloor (k-1)/2 \rfloor\}$ except reverse it for $i = 3$ so $n+3$ goes to $n$. A sum of two of $1,2,4,5,6,7,\ldots$ can make anything from 2 to $k-2$ since $\lfloor (k-1)/2 \rfloor \geq 5$, and we do $n \to n+2 \to n+2+(k-3)$ and $n \to n+4 \to n+4+(k-3)$ to get the last two cases.
26.02.2018 05:53
If I'm not mistaken, a probabilistic approach should immediately trivialize (b).
07.09.2021 12:22
(a) Claim 1. There exists a non-repeating directed cycle with length equals $4$ or $5$. Proof. We first show that there exists a cycle of length at least $4$. By a well-known fact, there exists a Hamiltonian path $V_1\to...\to V_{100}$. Notice that if $|i-j|\geq 3$ and $V_j\to V_i$ is an edge then we are done. Otherwise, notice that the only possible edges $V_i\to V_j$ with $i<j$ is the case when $j=i+2$. However, since $100$ is even, it is impossible to travel from $V_{100}$ to $V_1$, contradiction. Now suppose the length of this cycle is $k$, label the vertices as $V_1\to V_2\to...\to V_k\to V_1$. Then if $V_1\to V_4$ is an edge then $V_1\to V_4 ...\to V_k\to V_1$ will be a $k-2$-cycle. If $V_4\to V_1$ is an edge then $V_1\to V_2\to V_3\to V_4$ will be a $4$-cycle. Applying this process to the $k-2$-cycle and we are done. $\blacksquare$ Claim 2. There exists a vertex $V$ which is a part of the $a$-cycle and a $b$-cycle, where $(a,b)=1$. Proof. If the cycle in Claim 1 has length $4$, say $V_1\to V_2\to V_3\to V_4\to V_1$. If $V_1\to V_3$ is an edge then $V_3\to V_4\to V_1$ is a 3-cycle. By symmetry if $V_3\to V_1$ is an edge then $V_1\to V_2\to V_3$ is a $3$-cycle, hence $V_1$ is the part of a $3$-cycle and a $4$-cycle. If the cycle in Claim 2 has length $5$ then similarly we can show that $V_1$ is the part of either a $3$-cycle or a $5$-cycle. $\blacksquare$ Now by notice that by Frobenius Problem $V$ is a part of a $k$-cycle for all sufficiently large $k\geq M$. Pick $m$ sufficiently large. For each vertices $V_1,V_2$ let $d(V,V_1)+d(V,V_2)=f(V_1,V_2)$. Then we can construct a path $$V_1\to V\to V\to V_2$$where the middle step has length $m-f(V_1,V_2)$. Then we are done. (b) The answer is $2$. Obviously $m(G)=1$ is impossible. We now consturct an example where $m(G)=2$. In the following matrix, we define the entry $a_{ij}$ to be $1$ if $V_i\to V_j$ and $-1$ if $V_j\to V_i$. $$\begin{pmatrix} &1&1&1&-1&-1&-1\\-1&&1&-1&1&-1&1\\-1&-1&&1&-1&1&1\\ -1&1&-1&&1&1&-1\\1&-1&1&-1&&1&-1\\ 1&1&-1&-1&-1&&1\\1&-1&-1&1&1&-1&& \end{pmatrix}$$this graph satisfies $m(G)=2$ and $|V|=7$. The graph $$\begin{pmatrix} &1&1&1&-1&-1&-1&-1&1\\-1&&1&-1&1&-1&1&-1&-1\\-1&-1&&1&-1&1&1&1&1\\ -1&1&-1&&1&1&-1&-1&-1\\1&-1&1&-1&&1&-1&1&1\\ 1&1&-1&-1&-1&&1&-1&-1\\1&-1&-1&1&1&-1&&1&-1\\ 1&1&-1&1&-1&1&-1&&1\\-1&1&-1&1&-1&1&1&-1&& \end{pmatrix}$$satisfies $m(G)=2$ and $|V|=9$. Now suppose we have a graph $G(V,E)$ with $m(G)=2$. We now construct a graph $G'(V',E)$ with $m(G')=2$ and $|V'|=|V|+7$. Considet the the union of $G$ and the vertices $V_1,...,V_7$ connected as in the first graph above with $|V|=7$. For each vertex $V$ in $G$ we draw an edge from $V$ to $V_1,V_2,V_4,V_6$ and from $V_3,V_5,V_7$ to $V$. It is easy to see that it satisfies the condition. This completes the proof.
27.07.2024 10:01
Solution to Part (b) using probabilistic method: we prove $m=3$ works. For any edge $vw,$ define the direction uniformly and randomly ($1/2$ probability $v\to w$ and $1/2$ probability $w\to v$). Then $\Pr [\text{no }v\to u,u\to w]=(3/4)^{98}.$ $$\mathbb E[\#\{(v,w):\text{no }v\to u,u\to w\}]=100\times 99\times (\frac 34)^{98}<1.$$Therefore there exists $G$ with $m(G)=3.\Box$