The Country Of Brilliant

Level pending

Let $G$ be a graph with $2014$ vertices. Each pair of vertices is connected by a directed line (line with an arrow pointing at one direction). One can directly travel from one vertex to another iff the line joining those vertices points to the other vertex. Given two vertices $v_1, v_2,$ let $f(v_1, v_2)$ denote the minimum number of vertices (including $v_2$ but excluding $v_1$ ) one must go through to travel from $v_1$ to $v_2$ (if one cannot reach $v_2$ from $v_1,$ $f(v_1, v_2)= \infty$ ). For a given vertex $v,$ let $M(v)$ denote the maximum possible value of $f(v, j)$ where $j$ ranges over all other vertices of $G.$ Let $N(G)$ denote the minimum possible value of $M(v)$ where $v \in G.$ As $G$ ranges over all possible graphs with $2014$ vertices where each pair of vertices is connected by a directed line, find the maximum value of $N(G).$

Details and assumptions

The maximum value of $N(G)$ should be independent of the configuration of $G.$
As an explicit example, here's a graph with five vertices where each pair of vertices is connected by a directed line.

In this case, one can directly travel from $A$ to $C$ but not from $C$ to $A.$ One can directly travel from $D$ to $A$ but not from $A$ to $D.$ In this particular case, we have $f(A,D)= 2,$ since the shortest path one can take from $A$ to $D$ goes through two vertices excluding $A$ (there are two such paths: $A \rightarrow C \rightarrow D$ and $A \rightarrow B \rightarrow D$ ). It can be verified that $\max f(A, v)=2,$ which is attained when $v \in \{D, E\},$ so $M(A)=2.$

Since the original wording of this problem got a lot of disputes and clarification requests, I've changed the wording (although it's still essentially the same problem with a minor [read: major] correction; thanks to whoever launched that dispute!). I am sorry for the original problem being incorrect and vague. Is it more clear now?
This problem is inspired by an ISI entrance examination problem.

The answer is 2.

1 solution

Sreejato Bhattacharya
Apr 15, 2014

First, we shall show that there exists a graph $G$ for which $N(G)>1.$ To do this, we just have to construct a graph where there exists no vertex $v$ for which $M(v)=1.$ In other words, we have to construct a graph where there exists no vertex from where one can directly go to all other vertices. This is trivial: take three vertices $v_1, v_2, v_3$ and construct a graph where one can go from vertex $v_1$ to all other vertices except $v_2,$ and one can go from $v_3$ to $v_2.$

Image link: http://s27.postimg.org/lemsd82wz/Untitled.png

Note: In the image above the connections with $v_2, v_3$ to other vertices is not shown.

This graph satisfies all our requirements.

Now, we shall show that $N(G) \leq 2$ for all such graphs $G.$ In other words, we shall show that there exists a vertex $v$ such that $f(v,j)$ is either $1$ or $2,$ where $j$ is any other vertex belonging to $G.$

Label the vertices $v_1, v_2, ..., v_{2014}.$ For all $n \in [1, 2014],$ let $S_n$ denote the set of vertices that can be directly reached from vertex $v_n.$ Note that $a \not \in S_b \implies b \in S_a$ for all distinct vertices $a,b.$ Consider a $n$ for which $|S_n|$ is maximized. For any $v_j \in S_n,$ we have $f(v_n, v_j)=1.$ We shall show that for all $v_j \not \in S_n,$ $f(v_n, v_j)= 2.$ Note that if $v_n \in S_k$ where $v_k \in S_n$ for some $k,$ we will be done (the optimal path being $v_n \rightarrow v_k \rightarrow v_j$ ) . Suppose not, so for all $v_k \in S_n,$ $v_k \in S_j.$ This implies $S_n \subset S_j.$ Also, $v_n \in S_j,$ so $|S_j| \geq |S_n|+1,$ which is a contradiction since we have assumed $|S_n|$ to be maximized.

In conclusion, our answer is $\boxed{2}.$ Note that the answer is independent of the number of vertices in $G.$

The Country Of Brilliant

The answer is 2.

1 solution

0 pending reports