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.

Image link: hhttp://s13.postimg.org/4r5v65rh3/Untitled.png

Image link: hhttp://s13.postimg.org/4r5v65rh3/Untitled.png

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.

×

Problem Loading...

Note Loading...

Set Loading...