I consider $57$-cyclic, is the answer $\boxed{57}$?

The answer is $57$. Because the outdegree of each city is one, the graph looks like a bunch of connected subgraphs with a central cycle, and branches coming out of that cycle. For each subgraph, we take the cycle and assign them to $57$ groups such that the condition is satisfied, which is always possible. Then we assign the cities in the branches to the $57$ groups as well, repeat for each subgraph.

Sorry, but is there any motivation in getting that 57 is the answer? Thanks!

MathPanda1 wrote: Sorry, but is there any motivation in getting that 57 is the answer? Thanks! Small cases. $57 = 28\times 2 + 1$. During the APMO, I tried numbers smaller than $28$ to spot a pattern, and it’s easily generalizable once you actually see the pattern. (My paper was filled with graphs, and I drew shapes around cities which belong to the same group – it became harder when I ran out of shapes.)

Sorry, but I don't get the above solutions. Can someone explain how "the one with length 57 is the worst" or elaborate on how assigning each cycle to 57 groups is always possible? In other words, can someone please provide a clearer solution?

The graph can be partitioned into connected components, consisting of a cycle and trees leading into the cycle. For the cycle, label them in order ($0, 1, \dots, 56, 0, 1, \dots$) so $0 \rightarrow 1 \rightarrow \dots \rightarrow 56$. Then for each tree, suppose it leads to a vertex in group $k$. We label the trees by depth in decreasing order $k - 1, k - 2, \dots$ (taking mod 57). By our labeling of the cycle, there won't be any conflicts. Thus, $57$ is sufficient. To show it is necessary, Take any graph where one connected component has a cycle of length $57$, then nothing in this cycle can be in the same group.

Some other useful characterizations of Endomorphism-Associated Digraphs may be found here

Because for each cities , there is only one way out , so it can be partitioned into some regions , which are some cycles , or some path . We prove $57$ is the maximum number . Consider an establishment which contains of a $57 - $ cycle , and a $1959- $ cycle , any $2$ cities in the $57 - $ cycle can't be in the same group so we must use at least $57$ groups in this establishment Note that cities in other regions can be in the same group Consider a path , $x_1 \rightarrow x_2 \rightarrow x_3 .. \rightarrow x_k$ , if $i \equiv j $ (mod $29$ ) so they can be in the same group , then we need to used at most $29$ groups And for some cycle , suppose it's length is $y = 29k+r$ and the cycle is $y_1 \rightarrow y_2 \rightarrow .. \rightarrow y_n \rightarrow y_1$ . Except $r$ last cities , if $i \equiv j $ (mod $29$ ) then $y_i , y_j$ can be in the same group , and the last $r$ cities , each city in one group , so we need to use at most $29+r \leq 57$ groups So , the answer is $57$

Can someone explain how it is possible to get from one city to the other in less than 29 steps within the 57-cycle.

Plops wrote: Can someone explain how it is possible to get from one city to the other in less than 29 steps within the 57-cycle. If there's a 57-cycle then $k=56$ would fail because mod $57$ and the $28-$argument-thing. So $k\geq 57$ and $57$ works because: Note that there can't be any tree, and for $k\geq 57$ we can only consider cycles with length at least $58$. Label the cities $1,2,...,2016$, suppose $1,2,...,29$ are in the same cycle, consider groups $G_1,G_2,...,G_{29}$ where $G_i$ consists of city $i$, if we construct by adding as most as possible numbers of number in $G_i$ in the form $29T+i$, there is at most $1$ problematic number in such form for each $i$. However, $i=29$ has $0$ so we're done.

The answer is $57$. Notice that every vertices has out-degree 1 so they form a cycle. Now, if a cycle has $57$ vertices then no two vertices from that cycle can be in the same group, so at least $57$ groups are needed. On the other hand, given a cycle $V_1\to V_2\to...\to V_{n}$. For each $1\leq i\leq n-27$ we can put it in group $k$ where $k$ is the unique integer such taht $1\leq k\leq 29$ and $k\equiv i\pmod{29}$. And create another 28 groups for the reamining vertices.

The proof that there exists a "coloring" in $57$ colors has a common idea with this ARO 2002 problem https://artofproblemsolving.com/community/c6h5923p19834.

We claim the answer $57.$ Take the obvious digraph interpretation. Bound. Consider graph which contains a cycle of length $57=28\cdot 2+1.$ It's trivial, that all vertices of cycle must belong to different groups, hence $k\geq 57$ $\Box$ Construction. To each vertex we will assign a number from $0,1,2,\dots ,56$ - the number of group it will belong to. We consider separately connected components of graph; since the outdegree of each vertex is $1,$ this component is a cycle with several trees leading to the cycle. Firstly we consequentally label vertices of cycle by $$0,1,2,\dots ,55,56,55,54,\dots 2,1,0,1,\dots $$in order of cycle. Next we delete edges of cycle and consider left trees separately. Let $X$ be a vertex of tree, which was in cycle, and it is already labeled by $n$; divide all vertices of tree by sets $V_n,V_{n+1},V_{n+2},\dots $ as follows: $V_n$ consists of one vertex $X$; $V_i$ is a set of vertices, which lead to the vertices of $V_{i-1}$ for $i>n.$ Finally, we label vertices from $V_k$ by residue of $k$ modulo $57.$ Clearly, this labeling works, so we are done $\Box$

The answer is $57$. Interpret the problem as coloring a graph with $k$ colors. Proof of necessity: Take any graph with a $57$-cycle. No two vertices of this cycle can be the same color. $\blacksquare$ Proof of sufficiency: Consider connected components only, each of which has an equal number of edges and vertices. Momentarily undirecting the edges and considering a spanning tree plus an extra edge, it follows that each connected component has exactly one edge, and a number (possibly zero) trees extending off of the cycle. Redirecting all the edges and inducting on each tree starting from a leaf, each edge in a tree points "towards" the cycle. Looking at the (undirected) cycle only, starting with an arbitrary vertex and inducting, we find that it must also be a directed cycle. Color the cycle as follows: suppose it has length $29a+b$, with $0 \leq b<29$. Then color $29a$ consecutive vertices in the order $1,\ldots,29$, and then color the remaining $b$ using each color from $30$ to $57$ at most once. This clearly works. Then to color the trees, root each tree at its vertex in the cycle and color from the root outwards (with the root already being done). At each step, when we consider a vertex $v$, there are at most $28$ cities which can be reached in at most $28$ flights from $v$, and any vertex that can reach $v$ with some number of flights has not yet been colored, so we can certainly pick a color for $v$ and continue. This finishes the problem. $\blacksquare$ Remark: $28 \mid 2016$ is a red herring!

Split the graph into connected subgraphs, then since each has $n$ edges and $n$ vertices it must be a tree plus an edge. Color the cycle using mod $57$ and backpropagate along the trees in consecutive order (every vertex must end in a cycle, so it flows down along the tree and into the cycle), finishing. $57$ is minimal by taking a cycle with $57$ cities.