My first ISL!! Anyways, a straightforward problem. The general $100$ replaced by $\ell$ case is the same. Construct a graph $G$ with a vertex corresponding to each city, and an edge between each pair of cities for which a flight between the cities exists. Consider any vertex $v \in V(G)$. Let $d_4(v)$ be the number of vertices of distance $4$ from $v$ in $G$. Let $\{v_1, v_2, \dots , v_p\}$ be the set of vertices of distance $1$ from $v$ in $G$. Now for each $i\in\{1,2,\dots,p\}$, let $V_i$ be the set of vertices $w$ not in any $V_j$ for $j<i$ at distance $4$ from $v$ for which a path of length $3$ not including $v$ exists between $v_i$ and $w$. Let $|V_i| = n_i$. If all values of $n_i$ are zero, then $d_4(v) = 0$. So assume, WLOG that $n_1, n_2, \dots, n_q$ are non-zero (if not, re-index so that this is the case). Now note that all vertices in $V_i$ are distance $3$ from $v_i$, and for each $j\in\{1,2,\dots,q\}$ different from $i$, there must be at least one additional vertex of distance $3$ from $v_i$. Now since no vertex can have more than $\ell$ vertices at distance $3$, we have for each $i \in \{1,2,\dots,q\}$: \[n_i + q - 1 \leq \ell\] And we have that: \[d_4(v) \leq \sum_{i=1}^{q} n_i \leq \sum_{i=1}^{q} (\ell+1 - q) = (\ell+1-q)q\] But $f(q) = (n+1-q)q$ is maximum when $f'(q) = \ell+1 - 2q = 0$, or when $q = \frac{\ell +1}{2}$, so we have: \[d_4(v) \leq \left(\frac{\ell+1}{2}\right)^2\] Thus the number of vertices at distance $4$ from any vertex is at most $\left\lfloor{\frac{\ell+1}{2}}\right\rfloor^2$.

The bound is tight, by the way. For instance, take a single central vertex with $51$ linear branches of length $3$ and have $50$ vertices connected to the ends of each of these branches. Each vertex has distance exactly $3$ from at most $100$ other vertices (equality holds for the vertices at distance $1$ from the central vertex) while the central vertex is at distance exactly $4$ from $2550$ vertices. The general construction is analogous.

Personally, aside from C1 I found this to be the most straightforward problem on the shortlist. Consider an arbitrary vertex $v$, and say a vertex is an $d$-vertex if it is a distance $d$ from $v$. A beanstalk is defined as the union of several paths of length $4$ from $v$ to some $4$-vertices (called the beans) which all pass through a particular $1$-vertex (called the root). Consider a set of $m$ beanstalks with distinct roots such that any $4$-vertex is in at least one beanstalk, and no beanstalk has beans contained within the beans of another. One may show that for any two beanstalks $B$, $B'$ the root of $B$ is a distance $3$ from at least one vertex of $B'$. Upon realizing this, we find that each beanstalk may have at most $100-(m-1)$ beans. Thus the total number of beans is at most \[ m(101-m) \le 2550. \] Equality occurs, for example, if there are $51$ disjoint beanstalks each with $50$ beans. Indeed this equality case is the key motivation for the entire solution.

This isn't nearly as elegant as v_Enhance's solution but in the same vein (and using the same terminology), assume there existed at least $2551$ $4$-vertices incident to some $v$. Then since $v$ has at most $100$ $3$-vertices, there are at most $100$ beanstalks. By the pigeonhole principle, some beanstalk must then have at least $\left \lceil \frac{2551}{100} \right \rceil = 26$ beans. As mentioned by v_Enhance, each beanstalk root is incident to at least one vertex in all other beanstalks. In particular a root of a beanstalk with at least $26$ beans is a distance of three from each of those beans while also being a distance three from a vertex in other beanstalks. To satisfy the $100$ rule, there can be at most $74$ other beanstalks, for a total of $75$ beanstalks. So we went from at most $100$ beanstalks to at most $75$ beanstalks. We can iterate this argument, beginning with at most $a$ beanstalks and ending up with at most $101 - \left \lceil \frac{2551}{a} \right \rceil$. Building a sequence: $a_0 = 100$ $a_n = 101 - \left \lceil \frac{2551}{a_{n-1}} \right \rceil$ A simple induction shows that this is non-increasing in $[0,100]$. We need to show that there are no fixed points, i.e. no positive integral $a$ such that: $101 - \left \lceil \frac{2551}{a} \right \rceil = a$ $\Longleftrightarrow 100-a < \frac{2551}{a} \le 101-a$ The algebra shows that the RHS inequality is never satisfied so there are no fixed points, meaning that the sequence is monotonically decreasing. Then eventually we end up with at most $25$ beanstalks, so that some beanstalk has at least $101$ beans, breaking the $100$ rule.

lyukhson wrote: In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible numbers of flights required to go from one of them to the other. It is known that for any city there are at most $100$ cities at distance exactly three from it. Prove that there is no city such that more than $2550$ other cities have distance exactly four from it. Fix a vertex $v \in V(G)$. Now we say a vertex $u$ is $d$-distant (or simply a $d$-vertex) from $v$ if the distance between them is exactly $d$. Call a length-$4$ path from $v$ to it's $4$-vertices a vine. A bunch of vines emanating from the same $1$-vertex (to $v$) is called a vineyard. A vertex of the vine other than $v$ is called a grape. Now we prove the following claim. Claim. It is possible to select a bunch of vines with no two sharing a grape, such that all $4$-vertices are covered by some of them. (Proof) Start with an arbitrary $1$-vertex $u$ and consider all vines passing through it. For any subsequent vine, pluck it in our collection if it has no grape in common with a previously plucked vine. Continue as long as it is possible to do so; hence we get a set $S$ of vines. Now we claim that all $4$-vertices are terminal grapes of some vine. Consider a $4$-vertex $x$ which has not been covered yet and draw a vine from $v$ to $x$. Since our process has stopped, this vine must share a grape with a vine in $S$. Thus, $x$ is a grape of some vine in $S$; however, distance four ensures it is a terminal one. $\blacksquare$ Suppose $S$ describes $m$ vineyards. Note that $m \le 100$ since all $3$-vertices are in different vineyards. Observe that any $1$-vertex $u$ has a $3$-vertex in all vineyards it does not belong in; hence it's own vineyard can have no more than $100-(m-1)=101-m$ distinct terminal grapes. Consequently, the number of $4$-vertices is no more than $$m(101-m) \le 2550$$as desired. $\blacksquare$ Remark. Equality occurs for the graph with $51$ linear branches of length $3$ emanating from a vertex, each leading into $50$ free vertices.

Let $n=100.$ Assume a vertex $v$ has more than $\dfrac{n^2}{4}+\dfrac{n}{2}+1$ vertices that are $4$ away from it. Let $N_3$ be the set of vertices that are $3$ way from $v,$ $N_2$ be the set of vertices that are $2$ away from $v$ and have a neighbor in $N_3,$ and define $N_1$ similarly. If $c=|N_1|$ and $b=|N_2|,$ we trivially get $c\leq b.$ For each vertex $w_i \in N_1,$ let $W_i$ be the set of vertices that are $4$ away from $v$ that contain $w_i$ in its path to $v$ (i.e. are $3$ away from $w_i$). By the problem statement, $w_i$ can have at most $n$ vertices that are $3$ away from it. These vertices must include everything in $W_i$ as well as $N_2$ that does not have an edge with $w_i$, so we get $$|W_i| + b - x_i \leq n$$where $x_i$ is the number of vertices that have an edge with $w_i$ in $N_2.$ If $x_i > 1,$ then $w_i$ must have an edge with more than one vertex in $N_2$ (say $w_j$) and thus $|W_j|$ must be added. Thus, it can be seen that each edge from $w_i$ to $N_2$ can only increase the LHS, and we get the simpler inequality $$|W_i| + b - 1 \leq n.$$ Summing over all $c$ elements in $N_1,$ we get $$\sum_{i=1}^c(|W_i|-1) + c^2\leq \sum_{i=1}^c(|W_i|-1) + bc \leq nc.$$Noting that each vertex that is $4$ away from $v$ must lie in at least one of the $W_i,$ we get that $\sum_{i=1}^c |W_i| \geq \dfrac{n^2}{4}+\dfrac{n}{2}+1.$ Thus $$\dfrac{n^2}{4}+\dfrac{n}{2}+1-c+c^2 \leq \sum_{i=1}^{c}(|W_i| - 1)+c^2\leq nc \implies \dfrac{n^2}{4}+n\left(\dfrac{1}{2}-c\right)+c^2-c+1 \leq 0.$$The discriminant of this quadratic in $n$ must be negative, so $c^2-c+\dfrac{1}{4}-(c^2-c+1) \leq 0,$ which is always true. We may now conclude.

Pretty sraightforward graph theory probolem!!!

joybangla wrote: Thus the number of vertices at distance $4$ from any vertex is at most $\left\lfloor{\frac{\ell+1}{2}}\right\rfloor^2$. I think you meant $\left\lfloor{\left(\frac{\ell+1}{2}\right)^2}\right\rfloor$ because if we plug $\ell=100$ in $\left\lfloor{\frac{\ell+1}{2}}\right\rfloor^2$ we get 2500 which is wrong.

v_Enhance wrote: Now consider a set of $m$ beanstalks with distinct roots such that any $4$-vertex is in exactly one beanstalk. Why can we assume this?

Hmm, not sure what I was doing all those years ago I think the easier claim is "consider a set of $m$ beanstalks with distinct roots such that any $4$-vertex is in at least one beanstalk, and no beanstalk has beans contained within the beans of another". This I think should also be sufficient.

This is a lovely problem, but an absolute pain to write up. At first I thought this was easy for a C6 (since I got the key ideas pretty fast), but after having to write up all the gory details, I see why it was placed where it is. I expect that the below solution is basically incomprehensible, but hopefully correct. The solution makes a lot more sense conveyed face to face I think. Here goes nothing. Take the obvious graph theory interpretation. Let $k=50$. We'll show that if there are at most $2k$ vertices distance $3$ away from any vertex, then there are at most $k^2+k$ vertices distance $4$ away. Fix some root vertex $a$, and let $S$ be the set of vertices distance $4$ from $a$. Our goal is to show that $|S|\le k^2+k$. The key idea of the bound is not to focus on the fact that there are at most $2k$ vertices distance $3$ from $a$, but rather that there are at most $2k$ vertices distance $3$ from the neighbors of $a$ (as usual, the set of those neighbors is $N(a)$). To formalize this, we're going to need to define the notion of chunks. For any $x\in S$, let $p_x$ be some path of length $4$ from $a$ to $x$. Furthermore, for any $y\in N(a)$, let \[A_y=\bigcup_{ \substack{x\in S\\ y\in p_x} }p_x.\]Think of this as a neighbor $y$ of $a$ with all the distance $4$ vertices that you use $y$ to get to, along with all the vertices in between. These are almost what we'll called chunks, but we're going to want the chunks to be somewhat disjoint. More precisely, what we want is all of the vertices in the $A_y$s that are distance $2$ from $a$ to be separate for each chunk. To fix this, if $A_y$ and $A_{y'}$ have the same critical vertices a level below from $y$ and $y'$, then simply replace both of those with their union (note that we combine the two if and only if all of the critical vertices are the same). Keep repeating this process, and at the end, we're left with some sets $B_1,\ldots,B_r$, which we'll call chunks. To follow the proof, you can think of those original $A_y$s to have been disjoint, and those the chunks. For each chunk $B_i$, let $y_i$ be some element of $B_i\cap N(a)$ (you can think of this as the $y$ of $A_y$). We claim that every member of $B_i\cap S$ can be reached from $y_i$. If there was no joining of $A_y$s, then this is obvious as all the paths to members of $S$ pass through $y$. However, when we took unions of $A_y$s, we glued at all the points distance $2$ from $a$. Thus, if $B_i$ has both $A_y$ and $A_{y'}$, then the vertices distance $1$ from $y$ and $y'$ are identical. Thus, any member of $S$ that can be reached from $y'$ can also be reached from $y$, since we pass through some common critical vertex (distance $2$ from $a$). Let $\alpha_i=|B_i\cap S|$. Then, we have just shown that $y_i$ is distance $3$ from those $\alpha_i$ vertices. Note that we only glued $A_y$s if all the critical vertices matched. Thus, if we have $B_i\ne B_j$, then there is some critical vertex of $B_j$ that's not in $B_i$ at all. Thus, $y_i$ is distance $3$ from some critical vertex of $B_j$. Note that there is a subtlety here, which is that $y_i$ could be connected to that critical vertex through some external to the chunks path of length $\le 2$. If $y_i$ is connected to that critical vertex $z$ of $B_j$ through an edge, then $y_i$ is distance $3$ away from the distance $4$ vertices of $B_j$ (otherwise those vertices would be closer to $a$, which is a contradiction). If $y_i$ is connected to that critical vertex $z$ by a path of length $2$, then it is distance $3$ from all neighbors of $z$ that are distance $3$ from $a$ and are in $B_j$. This is true unless $z$ is connected by a path of length $2$ to those distance $3$ vertices of $B_j$ (if it was a single edge, then the distance $4$ vertices of $B_j$ would be too close to $a$), in which case it is again distance $3$ from the distance $4$ vertices of $B_j$. Regardless, $y_i$ is distance $3$ from some vertex in the chunk $B_j$, so there are at least $\alpha_i+r-1$ vertices of distance $3$ from $y_i$. Suppose for sake of contradiction that $\sum_{i=1}^r\alpha_i>k^2+k$. Note that we may have this inequality and still at most $k^2+k$ edges - the point is that $\sum_{i=1}^r\alpha_i\le k^2+k$ certainly implies at most $|S|\le k^2+k$, so we're proving something slightly stronger. If this is so, then there is some $i$ such that $\alpha_i>\frac{k^2+k}{r}$, so there are more than $\frac{k^2+k}{r}+r-1$ vertices distance $3$ from $y_i$. But by AM-GM and the fact that $r$ is integer, we see that \[\frac{k^2+k}{r}+r-1\ge 2k,\]so there are more than $2k$ vertices a distance $3$ from $y_i$, which is the desired contradiction. Thus, $|S|\le k^2+k$, as desired. Remark This solution is motivated from the equality case, where we have a tree rooted at $a$ and all the chunks are super distinct and nice. Here is a picture of an equality case for $k=4$, which hopefully makes following the proof a bit easier.

I think the equality case motivates a lot of the steps below. Pick an arbitrary vertex $V$, and suppose $a_1,a_2,\dots, a_n$ are its neighbors. Suppose $B$ is the set of vertices that are at distance $4$ from $V$. For every $a_i$, we define $X_i$ as the number of vertices $v$ in $B$ such that there exists a path of length 3 from $a_i$ to $v$ which does not share vertices or edges with paths in previous ones. Suppose $X_1\ge X_2\ge\dots X_m>0$. We want to bound $|B|$ by adding the $|X_i|$. Consider the vertex $a_i$. The number of vertices that have distance $3$ to $a_i$ is at least $X_i+m-1$. Then we have the inequality $$X_i+m-1\le 100$$for every $i$. Summing all over $i$, we have $$|B|=\sum_{i} X_i \le m(100-m+1)\le 2550.$$In particular, an example of the equality case is illustrated in the figure below. \begin{tikzpicture} \filldraw [black] (0,0) circle (1.5pt) node[anchor=south] {$V$} (1.414,1.414) circle (1.5pt) node[anchor=south east] {$a_1$} (-1.414,1.414) circle (1.5pt) node[anchor=south west] {$a_2$} (-1.414,-1.414) circle (1.5pt) node[anchor=north west] {$a_{49}$} (1.414,-1.414) circle (1.5pt) node[anchor=north east] {$a_{50}$} (2,2) circle (1.5pt) node[anchor=north west] {$b_1$} (-2,2) circle (1.5pt) node[anchor=north east] {$b_2$} (-2,-2) circle (1.5pt) node[anchor=south east] {$b_{49}$} (2,-2) circle (1.5pt) node[anchor=south west] {$b_{50}$} (3,2) circle (1.5pt) node[anchor=west] {$c_1$} (2,3) circle (1.5pt) node[anchor=south] {$c_2$} (-2,3) circle (1.5pt) node[anchor=south] {$c_3$} (-3,2) circle (1.5pt) node[anchor=east] {$c_4$} (-3,-2) circle (1.5pt) node[anchor=east] {$c_{97}$} (-2,-3) circle (1.5pt) node[anchor=north] {$c_{98}$} (2,-3) circle (1.5pt) node[anchor=north] {$c_{99}$} (3,-2) circle (1.5pt) node[anchor=west] {$c_{100}$}; \draw (-2,-2) -- (2,2) (-2,2) -- (2,-2) (2,3) -- (2,2) -- (3,2) (-2,3) -- (-2,2) -- (-3,2) (-2,-3) -- (-2,-2) -- (-3,-2) (2,-3) -- (2,-2) -- (3,-2); \end{tikzpicture} (You can run it with tikz package loaded) Each $b_i$ connects to 51 distinct elements that have distance 4 from $V$. Then we have $51\times 50=2550$ elements with distance 4 from $V$.

Consider a vertex $V$, and ignore all vertices which are more than $4$ away from it (i.e. delete them from the graph.) Suppose we deleted $V$, and let the connected components formed with at least one vertex $4$ away from $V$ be $x_1,\ldots,x_k$. Let $m(x_i)$ be the set of vertices in $x_i$ exactly $4$ away from $V$, and let $V(x_i)$ be one of the vertices in $x_i$ which is a neighbor of $V$. Note that the amount of vertices exactly $3$ away from $V(x_i)$ is at least $|m(x_i)|+(k-1)\le 100$, so $|m(x_i)\le 101-k$. Thus, the amount of vertices exactly $4$ away from $V$ is at most $k(101-k)\le 50\cdot 51=2550$.

Cool problem. As other users have noted ; the equality case motivates most of the solution.

Take the obvious graph theory interpretation. Let a funny tree be a union of disjoint paths of length 4 from $v$ (and all share a common vertex at $v).$ Also, let $d_4(v)$ denote the number of vertices that are distance 4 away from $v$ and $d_3(v)$ denote the number of vertices that are distance 3 away from $v.$ We also let k be the number of disjoint paths that are connected to $v.$ Note that $G$ is connected. Now, take a funny tree of $G$ and delete all other edges/vertices. We will prove the upper bound: First, take an adjacent vertex $u$ to $v.$ Note that $ k-1 + d_4(v) \le d_3(u) \le 100,$ so $d_4(v) \le 101-k.$ Now, we multiply by the number of paths to get $k(101-k) \le 2550.$ We now show a working construction for the equality case: take a vertex and connect $50$ disjoint paths of length 3 to the vertex. Then, at the end of each of those disjoint $50$ paths, connect $51$ edges. It is easy to see this construction works. The following is a graph of the construction with 50 replaced by 4 and 51 replaced by 4: [asy][asy] import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -25.87679931321831, xmax = 19.899150736259937, ymin = -15.133392279692472, ymax = 11.825566445099064; /* image dimensions */ /* draw figures */ draw((-3.26,-2.24)--(-1.34,-0.88), linewidth(1)); draw((-3.26,-2.24)--(-4.24,-0.56), linewidth(1)); draw((-3.26,-2.24)--(-5.62,-3.18), linewidth(1)); draw((-3.26,-2.24)--(-0.76,-4.32), linewidth(1)); draw((-1.34,-0.88)--(2.449479177025517,0.5775831370965989), linewidth(1)); draw((2.449479177025517,0.5775831370965989)--(3.078720965577765,2.317251611329283), linewidth(1)); draw((3.078720965577765,2.317251611329283)--(6.150901462626976,2.3542658341852976), linewidth(1)); draw((-4.24,-0.56)--(-5.5826071827296495,1.7250240456330501), linewidth(1)); draw((-5.5826071827296495,1.7250240456330501)--(-8,2), linewidth(1)); draw((-8,2)--(-8.062560114082627,4.279005422698055), linewidth(1)); draw((-0.76,-4.32)--(3.5599058627059548,-4.604408062745439), linewidth(1)); draw((3.5599058627059548,-4.604408062745439)--(4.300190319826247,-6.121991199842036), linewidth(1)); draw((4.300190319826247,-6.121991199842036)--(3.6709485312739987,-8.083745011210807), linewidth(1)); draw((-5.62,-3.18)--(-8.580759234066832,-3.5680098227770314), linewidth(1)); draw((-8.580759234066832,-3.5680098227770314)--(-10.09834237116343,-5.196635628441672), linewidth(1)); draw((-10.09834237116343,-5.196635628441672)--(-14.429006445317135,-5.455735188433774), linewidth(1)); draw((-10.09834237116343,-5.196635628441672)--(-10.468484599723574,-8.898057914043127), linewidth(1)); draw((-10.09834237116343,-5.196635628441672)--(-7.100190319826246,-10.415641051139726), linewidth(1)); draw((-10.09834237116343,-5.196635628441672)--(-12.726352193940464,-3.271896039928915), linewidth(1)); draw((-8.062560114082627,4.279005422698055)--(-4.916351171321384,5.426446331234506), linewidth(1)); draw((-8.062560114082627,4.279005422698055)--(-9.321043691187121,5.907631228362695), linewidth(1)); draw((-8.062560114082627,4.279005422698055)--(-10.542513045435603,3.908863194137909), linewidth(1)); draw((-8.062560114082627,4.279005422698055)--(-10.986683719707777,3.1685787370176177), linewidth(1)); draw((3.078720965577765,2.317251611329283)--(2.930664074153709,4.093934308417982), linewidth(1)); draw((3.078720965577765,2.317251611329283)--(1.5981520513371836,3.7237920798578363), linewidth(1)); draw((3.078720965577765,2.317251611329283)--(5.225545891226614,1.0957822570808027), linewidth(1)); draw((3.6709485312739987,-8.083745011210807)--(5.225545891226614,-9.083129028323201), linewidth(1)); draw((3.6709485312739987,-8.083745011210807)--(3.5228916398499424,-10.45265527399574), linewidth(1)); draw((3.6709485312739987,-8.083745011210807)--(1.376066714201096,-9.009100582611172), linewidth(1)); draw((3.6709485312739987,-8.083745011210807)--(0.6357822570808042,-7.343460554090516), linewidth(1)); /* dots and labels */ dot((-3.26,-2.24),dotstyle); dot((-1.34,-0.88),dotstyle); dot((-4.24,-0.56),dotstyle); dot((-5.62,-3.18),dotstyle); dot((-0.76,-4.32),dotstyle); dot((2.449479177025517,0.5775831370965989),dotstyle); dot((3.078720965577765,2.317251611329283),dotstyle); dot((6.150901462626976,2.3542658341852976),dotstyle); dot((-5.5826071827296495,1.7250240456330501),dotstyle); dot((-8,2),dotstyle); dot((-8.062560114082627,4.279005422698055),dotstyle); dot((3.5599058627059548,-4.604408062745439),dotstyle); dot((4.300190319826247,-6.121991199842036),dotstyle); dot((3.6709485312739987,-8.083745011210807),dotstyle); dot((-8.580759234066832,-3.5680098227770314),dotstyle); dot((-10.09834237116343,-5.196635628441672),dotstyle); dot((-14.429006445317135,-5.455735188433774),dotstyle); dot((-10.468484599723574,-8.898057914043127),dotstyle); dot((-7.100190319826246,-10.415641051139726),dotstyle); dot((-12.726352193940464,-3.271896039928915),dotstyle); dot((-4.916351171321384,5.426446331234506),dotstyle); dot((-9.321043691187121,5.907631228362695),dotstyle); dot((-10.542513045435603,3.908863194137909),dotstyle); dot((-10.986683719707777,3.1685787370176177),dotstyle); dot((2.930664074153709,4.093934308417982),dotstyle); dot((1.5981520513371836,3.7237920798578363),dotstyle); dot((5.225545891226614,1.0957822570808027),dotstyle); dot((5.225545891226614,-9.083129028323201),dotstyle); dot((3.5228916398499424,-10.45265527399574),dotstyle); dot((1.376066714201096,-9.009100582611172),dotstyle); dot((0.6357822570808042,-7.343460554090516),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy]

Ok, I think I've overestimetated this problem. It's a nice one though! Take an arbitrary vertex $v$ in $G$. For any vertices $x,y \in G$, define $dist(x,y)$ to be the distance between these two vertices. Let $S_2=\{s \in G | dist(s,v)=2\}$. Observe that for any $x \in N(v),$ $dist(x,s)=3$ for all $s\in S_2$ such that $xs$ is not an edge. $(\star)$ $\implies$ suppose that we have $m$ disjunt paths leaving out from $v$. $\implies$ from $(\star)$, for each $x \in N(v)$, the number of paths of length $3$ from $x$ that don't pass throught $v$ is at most $100-(|S_2|-1)=101-|S_2|$. Since $m \leq |S_2|$, we have that the maximum number of vertices $u \in G$ such that $dist(u,x)=3$, $x \in N(v)$ and the path doesn't pass throught $v$ is at most $(101-|S_2|)|S_2| \leq 2550$, by AM-GM. Hence, the total of vertices with distance $4$ from $v$ is at most $2550$, as desired. $\blacksquare$

Take the obvious graph theoretic interpretation and replace $100$ with $2k$. Pick any vertex, say $v$, I will show that at most $k(k+1)$ vertices have distance $4$ from it. Call a vertex good if it has distance exactly $4$ from $v$ First, perform the following optimizations, if there are any vertices that dont lead into a good vertex, delete them, because they dont matter. Keep deleting edges until we're left with a tree which has root $v$ and has the leaves as the good vertices. The only possible problem is if a good vertex comes in the path of another good vertex. But say this vertex is $a$ and is connected to $b$. Then delete edge $ab$ and add a new vertex $c$ and add edge $bc$, which solves this. So now, suppose $v$ is connected to $n$ vertices. All of these lead to some good vertices, call each of these paths as divisions. Pick a neighbour of $v$, say $z$. Say the division containing $z$ leads to $p$ good vertices. Now, look at how many vertices have distance $3$ from $z$. All of the $p$ good vertices as well as at least one vertex from each other division ($n-1$ of those). So, there are at least $p+(n-1)$ vertices of distance $3$ from $z$. So, we have $p+n-1 \le 2k \implies p \le 2k-n-1$ So, each division has at most $2k-n-1$ good vertices. So, the total good vertices is at most $n(2k-n-1) \le k(k+1)$ (by AM-GM, smoothing etc.), as claimed. Now, the problem is just the case $k = 50$ for which we have there are at most $50(51) = 2550$ good vertices, as claimed. $\blacksquare$

We firstly construct a "sudo-tree" as follows.Fix the vertex $"v_1"$ with the maximal property as given as the root.We consider the vertices which are at distance 4 from it and call them good.Then in our sudo tree ,add the paths from $"v_1"$ to the good vertices stepwise, and whenever we have two paths between $v_1$ and some $v_i$,say $v_1v_2..v_i$ and $v_1v_3..v_i$,then choose out of $v_2,v_3$,the one which has already appeared in the sudo tree otherwise choose arbitrarily.Note that the sudo tree is not an induced subgraph and we still have the notion of branches arising from $v_1$,because we always consider only one path from $v_1$ to some good vertex.Now,let there be $b$ branches and we have that every good vertex is a leaf here.Denote the first vertex of each branch(i.e. a neighbour of v_1) as parent of the branch .Then in the $i$ th branch, let $a_i$ be the number of vertices at distance 3 from its parent in the sudo tree.By construction,these $a_i$ vertices are good,so the total number of good vertices is just sum over all branches.Now,an observation,that for the parent in any branch,there exists a vertex on any other branch,such that the distance between these vertices is exactly $3$.Thus,we have that $a_i+b-1<=100$.Summing over,we get $a_1+...a_b<=b(101-b)<=2550$.The equality case exists,which is a tree formed by a root with 51 branches,where each branch ends in a vertex with $50$ leaves attached.

Construct a tree of minimal distance centered at the given vertex. For each vertex, we obtain a single path of unique distance. Partition the 4-dist vertices based on the first non-root vertex in their path. Then let the sizes of this partition be $r_1, r_2, \ldots, r_k \geq 1$. It follows that since distance is a discrete-continuous function and the distance between any 4-dist vertex and a 1-dist vertex is at least 3, that the path of any 4-dist vertex has some vertex that is 3-dist from a fixed 1-dist vertex if that 4-dist vertex is not in the corresponding partition. Furthermore, it is obvious that any pair of 4-dist vertices in different partitions have disjoint paths excluding the root (which has dist 1 from and 1-dist vertex by definition), so it follows that $(k-1) + r_i \leq 100$ for each $i$. Thus we bound the total number of 4-dist vertices by $r_1 + \ldots + r_k \leq (101-k)k \leq 2550$ as desired.

Hopefully this works. Consider a vertex $v$ and its neighbors $v_1, v_2, \dots, v_k$; let $n_i$ be the number of vertices that are at distance $3$ from $v_i$ and have distance $4$ from $v$ (i.e. the path from $v_i$ to each such vertex doesn't pass through $v$). We have that the vertices at distance $4$ from $v$ are at most $n_1+n_2+\ldots+n_k$. Applying the condition in the statement for all $v_i$ gives that $n_i+k-1 \leq 100$ (there at most $k-1$ vertices at distance $2$ from $v$, which are at distance $3$ from $v_i$ - the vertex directly adjacent to $v_i$ is excluded and the vertices at distance $2$ are at most $k$), so summing implies that $\sum n_i \leq k(101-k)\leq 2550$, done.

Not very elegant but doesn't require much imagination: almost a brute-force type solution where the problem is incrementally broken down until the remaining structure is simple. I liken it to peeling the layers of an onion back. Layer 0: Use the obvious graph interpretation with the cities being represented by a graph $G$ Most of this problem will be a smoothing process. Suppose for the sake of contradiction that the condition on distance 3 is true, and also that there exists a vertex $V$ such that there are more than $2550$ other cities which are distance $4$ from it. Construct a tree $T$ which is a subset of $G$, rooted at $V$ such that the parent of some vertex $w$ is distance $1$ closer to $V$ than $w$ is (the existence of such a tree can be explicitly proven through BFS). Refer to a vertex of distance $d$ from $V$ as a $d$-vertex. There are a number (possibly zero) of edges in $G \setminus T$: call these side edges. Note that a side edge must connect a $d$-vertex to another $d$-vertex or to a $d$-vertex to a $d+1$-vertex. We turn our focus to the $1$-vertices: I will show that some $1$-vertex has more than $100$ cities at distance exactly three from it. Note that (by the triangle inequality, for instance) such vertices must have distance at most $d$ from $v$, so we can in fact delete every vertex of distance at least $5$ from $G$ (and $T$), since none of these vertices are reachable from a $1$-vertex quickly enough. Now note that, by turning our attention to $1$-vertices only, we can perform any change to the graph which does not modify the number of $4$-vertices and does not increase the number of vertices of distance $3$ from any $1$-vertex. Specifically, we delete certain side edges and show that this will not increase the number of vertices of distance $3$ (since the number of $4$-vertices won't change): equivalently, we show that adding a side edge between those two vertices (where one didn't exist before) nonstrictly increases the number of vertices of distance $3$. This essentially only makes the problem harder, and will be used extensively throughout the rest of our layers. At the end of each layer, perform the optimizations that we proved were allowed in that layer. Layer 1: We can delete any side edge joining two $4$-vertices. This is because no path through this edge starting from a $1$-vertex can have distance $3$. Layer 2: We can delete any side edge joining a $3$-vertex and a $4$-vertex. This is because if we add that edge, any path going through it from a $1$-vertex $v$ has distance at least $3$, so we cannot change any vertex's distance from $v$ from $3$ to something smaller, which is the only way that adding a new edge can decrease the number of distance $3$ vertices from $v$. Layer 3: We can delete any side edge joining two $3$-vertices. The reasoning is the same as layer 2, I just like onions. Layer 4: We can delete any $3$-vertex $v$ which is not connected to any $4$-vertices. Clearly this will not change the number of $4$-vertices. Suppose that there exists a $1$-vertex $w$ where the deletion of $v$ will increase the number of distance $3$ vertices from $w$, i.e. there exists some vertex $a\neq v$ which is distance $<3$ from $w$ before deleting $v$, and that distance increases to $3$ after deleting $v$. Then the shortest path between $a$ and $w$ before deletion must go through $v$ and have distance at most $2$, but the distance between $v$ and $w$ is at least $2$, and we need one more edge to get to $a$: contradiction. Layer 5: We can delete any side edge joining a $2$-vertex and a $3$-vertex. Fix a $1$-vertex $v$, and suppose that the deletion of the edge makes some vertex $w$ increase from $<3$ to $3$. Clearly $w$ must be a $3$-vertex: $4$ is too far for the initial distance to be $<3$, and the edge can't interact with $2$-vertices here because the path 1-2-3-2-1 is far too long, and $1$-vertices as well as $v$ are too close for the final distance to be $3$, so our $<3$ actually equals $2$. By previous layers, $w$ must have some $4$-vertex adjacent to it, and furthermore that $4$-vertex is not adjacent to any other vertices. Then the distance between $v$ and that $4$-vertex was originally $3$, and is now $4$. Thus the total number of vertices distance $3$ from $v$ does not actually decrease. Layer 6: Henceforth we may ignore every $2$-vertex which is not adjacent to any $3$-vertices when counting the number of distance $3$ vertices from a $1$ vertex (for now we cannot delete these vertices, since their edges may affect us)—call these mute vertices. Note that any adjacencies between $2$-vertices and $3$-vertices at this point must come from edges in $T$. This clearly will decrease the number of distance $3$ vertices from any $1$ vertex. Layer 7: We can delete any side edge joining two $2$-vertices. Suppose that this deletion changes a vertex $x$ of distance $<3$ from a $1$-vertex $a$ to distance $3$. One can easily tell that $x$ must be a $2$-vertex for similar reasons as listed in layer 5, since any path through $\overline{vw}$ that passes through $a$ and a $3$-vertex has distance at least $3$, so it is clear that $<3=2$ (abusing notation). Because we aren't counting mute vertices, $x$ must have an adjacent $3$-vertex, whose distance from $a$ changes from $3$ to $4$, thus counteracting the effect on $x$. By layer 5, the adjacent $3$-vertex cannot be adjacent to any other $3$-vertices, hence this deletion will not increase the number of distance $3$ vertices from $a$. (Note that without layer 5, it could be possible that the adjacent $3$-vertex tries to counteract the change in distance of multiple $2$-vertices, which is not enough.) Layer 8: We can delete any side edge joining a $1$-vertex $v$ with a $2$-vertex $w$. Like before suppose a (non-mute) vertex $x$ goes from distance $<3$ from $1$-vertex $a$ to distance $3$. Here we have multiple cases: We have $x=w$, so clearly $a=v$. Then some $4$-vertex which is a child of $x$ in $T$ (this exists by layers 6 and 4) changes from distance $3$ to $5$, counteracting the change of the distance of $x$. $x\neq w$, but $x$ is a $2$-vertex. This is the same as the previous case, where a $3$-vertex child of $x$ in $T$ goes from distance $3$ to $4$. $x$ is a $3$-vertex. Then by layer $4$ some $4$-vertex child of $x$ in $T$ goes from distance $3$ to $4$. In all of these the total number of distance $3$ vertices from $a$ nonstrictly decreases, as desired. Layer 9: We can delete any edge joining two $1$-vertices. If this change makes some vertex $x$ increase its distance from $1$-vertex $a$ from $<3$ to $3$, then it is clear that $x$ is a non-mute $2$-vertex, and the same reasoning as seen in layer 7 applies. Layer 10: After making all these deletions, we are left with only the vertices in $T$, with some branches rooted at $v$ only extending to layer $1$ or $2$, and the rest extending to layer $4$. We can delete all of the former branches (not including $v$, of course), since the deletion of mute vertices changes nothing as we never counted them in the first place, nor can we accomplish anything by moving through them, and the $1$-vertices are all distance (at most, but in fact exactly) $2$ from every other $1$-vertex. At this point, the problem is reduced to algebra. Suppose we have $n$ $1$-vertices (after deletion), and vertex $i$ of these has $a_i>0$ $2$-vertex children and $b_i>0$ $4$-vertex children, so $$\sum_{i=1}^n b_i\geq 2551.$$On the other hand, we can easily see now that any $1$-vertex $i$ has $$b_i+\sum_{\substack{1\leq j\leq n\\j \neq i}} a_i\geq b_i+(n-1)$$vertices at distance $3$ from $i$, so by expectation some $1$-vertex has at least $$(n-1)+\frac{1}{n}\sum_{i=1}^n b_i\geq n+\frac{2551}{n}-1$$vertices at distance $3$ from it. One can easily see that the function $$f(x)=x+\frac{2551}{x}-1$$is increasing on $(0,\sqrt{2551}]$ and decreasing on $[\sqrt{2551},\infty)$ (for instance, by taking derivatives), so this function is minimized when $x \in \mathbb{Z}^+$ when $x=50$ or $x=51$. In either case, it is trivial to see that $f(x)>100$, so we have found a vertex with more than $100$ cities at distance exactly $3$ from it, as desired: contradiction. We are done. $\blacksquare$ Remark: Examination of the equality case is quite important. It indicates the following heuristics that are crucial in setting up the restrictive steps of our argument: We only need to consider $1$-vertices to find a vertex with more than $100$ cities at distance $3$ from it. We will probably be able to keep on deleting edges: the first few layers are probably able to be motivated immediately, without this, but when going further when things become nontrivial, our confidence is increased by the fact that the equality cases seem treelike. Some aren't trees but are very close to them (and the advertised adjustments maintain equality!), indicating that the adjustment might work (so we consider it and it does). For layer 6, we see that we will probably have a sizable amount of distance $3$ vertices from a $1$-vertex come from $4$-vertices, so if a certain $2$-vertex doesn't have $3$-vertex children (and thus no $4$-vertex descendants) it feels like we can delete it (which allows the next few layers to be true), but we can't exactly do that so after some thinking we come form this instead.

We use the graph theory interpretation. Assume the contrary and let $G=\{V, E\}$ be the graph with the least amount of edges that satisfies our condition. Let $v$ be a vertex such that there exist at least $2551$ other vertices with distance exactly $4$ from it. Denote by $A_x$ the set of vertices that have distance exactly $x$ from $v$ such that $A_0=\{v\}$. Clearly, we have $V=v \cup A_1 \cup A_2 \cup A_3 \cup A_4$. Observe that the vertices in $A_x$ can only be adjacent to vertices in $A_{x-1}\cup A_{x+1}$ since the vertices in $A_x$ are pairwise non-adjacent due to the minimality of $|E|$. Suppose that $u \in A_x$ is adjacent to at least $2$ vertices in $A_{x-1}$. Deleting one of these edges won't change the distance between vertices. Hence, $u$ is adjacent to exactly one vertex in $A_{x-1}$. Furthermore, if $u \in A_x$ where $0 \leq x \leq 3$ is not adjacent to any vertices in $A_{x+1}$, the graph resulting from deleting $u$ still satisfies our condition which contradicts the minimality of $|E|$. Let $|A_1|=k$. By the pigeonhole principle there is a vertex $w \in A_1$ for which there exist at least $\frac{2551}{k}$ vertices in $A_4$ with distance exactly three to $w$. Notice that each vertex in $A_1 \setminus \{w\}$ has distance exactly $2$ from $w$. It follows from the obvervations established in the previous paragraph that there are at least $|A_1 \setminus \{w\}|=k-1$ vertices in $A_2$ with distance exactly $3$ from $w$. Hence, there are at least $\frac{2551}{k}+k-1$ vertices with distance exactly three from $w$ which is greater than $100$ for integer values of $k$, a contradiction. $\blacksquare$

See note Suppose that vertex $v$ has more than $2550$ such points. Draw a subtree formed by running BFS from $v$. The point is that we can define sets of nodes $S_i$ consisting of vertices distance $i$ from $v$. In particular $|S_4|>2550$. Suppose $s=|S_1|$ and let $d_1,\dots,d_s$ be the number of vertices of $S_4$ in each of the subtrees of vertices in $S_1$. Claim: For any vertex $b\in S_4$ which is in the subtree of $a\in S_1$, the distance between $a$ and $b$ is exactly $3$. Proof: Not very hard; the distance is clearly at most $3$ and if $d<3$ then the distance between $v$ and $b$ is at most $1+d<4$, contradiction. (This actually generalizes in these BFS trees which is fun to play around with but not really that useful aside from this claim.) Claim: Define $a\in S_1$ as above. For any vertex $c\in S_1$, there is some vertex $u$ in the subtree of $c$ which has distance $3$ from $a$. Proof: Assume otherwise. Take a path $v\to c\to x\to y\to z$ and notice the following: The distance from $a$ to $y$ is at least $2$. It cannot be exactly $2$ or exactly $3$, and yet it is at most $4$, so it is exactly $4$. The distance from $a$ to $x$ is at least $3$, and yet it is also at most $3$. Therefore it is exactly $3$, a contradiction. Hence for each vertex in $S_1$, the number of vertices which are a distance exactly $3$ from that vertex is at least $d_i+(s-1)$. Summing, we find: \[100s\ge \sum d_i + s(s-1)\]\[100s>2550+s(s-1)\]\[s^2-101s+2550<0\]\[(s-50)(s-51)<0\]which is a contradiction. $\blacksquare$ Note: I think each vertex in $S_1$ is required to have a vertex in $S_4$ in the subtree, but this should work since redefining $S_1$ as the set of vertices where the subtrees have such a vertex doesn't change the proof.

Let $G$ be the graph defined by flights between cities. Let $o$ be a vertex. We will construct a tree $\mathcal{T}$ rooted at $o$ that is a subgraph of $G$ such that vertices have the same distance from $o$ in $\mathcal{T}$ and in $G$. First, add $o$ to the tree. Go through the vertices in order of their distance from $o$. For each vertex $v$, if it has distance $k$ from $o$, it must be connected to some vertex with distance $k-1$ from $o$. So, add that edge to the tree. Let $\mathcal{S}_k$ be the set of vertices with distance $k$ from $o$. Let $\mathcal{T}'$ be the result of $\mathcal{T}$ after removing $o$ and removing all connected components without an element of $\mathcal{S}_4$. Let $\mathcal{C}$ be a component of $\mathcal{T}'$ is rooted at $v\in \mathcal{S}_1$. Let $\mathcal{C}'$ be another component of $\mathcal{T}'$. Let $v'\in \mathcal{S}_1$ be the root of $\mathcal{C}'$. Let $u\in \mathcal{S}_4\cap \mathcal{C}'$. Then, the distance from $v$ to $v'$ is at most $2$ and the distance from $v$ to $u$ is at least $3$. So, some vertex on the path between $v'$ and $u$ has distance exactly $3$ from $v$. So, every component of $\mathcal{T}'$ besides $\mathcal{C}$ has a vertex with distance $3$ from $v$. If there are $m$ components of $\mathcal{T}'$, then this is $m-1$ vertices that have distance $3$ from $v$. In addition, $\mathcal{C}$ has $|\mathcal{C}\cap \mathcal{S}_4|$ vertices with distance $3$ from $v$. So, \[|\mathcal{C}\cap \mathcal{S}_4|+m-1\le 100\]\[|\mathcal{C}\cap \mathcal{S}_4|\le 101-m\]\[|\mathcal{S}_4|\le m(101-m) \le 2550.\]

Not that hard but still fun Take the obvious graph $G$. Fix a vertex $v$, and we show that $T \le 2550 = 50 \cdot 51$ vertices have distance $4$ from it. Claim: WLOG we can assume $G$ is a tree with depth $4$ and root $v$. Proof. Let $A_1, A_2, A_3, A_4$ be the vertices with distance $1$ through $4$ to $v$. Now consider adding vertices from $A_i$ for increasing $i$ one by one. If the new vertex $u \in A_i$ has two edges to two vertices in $A_{i-1}$ then removing one of the edges preserves the distance of vertices in $v$, similarly for any edges to other vertices in $A_i$. This also preserves the bound of at most $100$ cities being distance exactly three from all cities. We can similarly just discard vertices with depth more than $4$ as that preserves $T$. $\blacksquare$ Now, let there be $n$ vertices $s_1, s_2, \dots, s_n$ in $A_1$. Parititon the set of vertices with distance $4$ into $S_1 \sqcup S_2 \sqcup \dots \sqcup S_n$ based off which $s_i$ the path a vertex in the set to $v$ contains, so $T = |S_1| + \dots + |S_n|$. For a vertex $v \in A_1$, we get that \[ |S_v| + (n-1) \le 100. \]Summing over all $n$ vertices, we get \[ \sum_{i=1}^n \left(|S_i| + (n-1)\right) = T + n(n-1) \le 100n \iff T \le (101-n)n. \]Since $(101-n)n$ is maximized for integer $n \in \{50, 51\}$, the result follows.