I'm sorry but I have some (stupid) questions: -are all the pairs of cities linked two-way? since you wrote that "some" of them are, and then for "every pair" there's one aviaroute -what is an interchange -in which order do you visit the cities since you tlak about ascending order. You start from X, you go to one city Y linked to X by an aviaroute, and then? I'm really sorry if these questions are stupid, and thanks for the translations.

It should be flight in first sentence not aviaroute.Flight is an edge in graph.Aviaroute is a path in graph.

Let $A,B,C$ are some cities and $(A,B)$ and $(B,C)$ - two-way flights. Then if we want fly from $A$ to $C$ we should fly from $A$ to $B$ , then change airliner (it is interchange, maybe I chose wrong word for it ) and fly from $B$ to $C$. PS. I make some changes in problem, maybe problem became more clear.

Thanks a lot for your two answers, it's really clear now!

I will prove it for prime $p$ instead of $2016$, but it can be easily generalized. The solution will be splitted in three parts:two lemmas and their application to this problem. Some notation at the begining: let $f(X)$ be the nubmer of numerations counted by the major of $X$. Let $s_X(A)$ be the number of cities in the country such that the $A$ is in the route from $X$ to that city(maybe as an endpoint, so for example $s_{X}(X)=n$...). Lemma 1: $f(X)=\frac{(n-1)!}{\prod_{v \neq X}s_{X}(v)}$. Proof:The proof is inductive. Root the tree in $X$, and let it's childrens be $A_1, A_2, \cdots , A_n$. Now, proceed to computing $f(X)=f(A_1) \cdots f(A_n) \frac {n!}{s_X(A_1)! \cdots s_X(A_n)!}$, and after the easy computation, we get the desired result. Lemma 2:$v_p(n!)>\sum_{v \in G} v_p(s_X(v))$ for $n>p$ Proof: The proof goes again by induction. Base:$n=p$, is obvious. Then, let again $X$ be the root and $A$'s his children. By a well-known result(multinomial coeficents are integers...) $v_p((n-1)!)>v_p(s_X(A_i)!)>$(By summing the inductive hypothesis for all $A_i$'s)$\sum_{v \neq X} v_p(s_X(v))$. Done. By combining these two lemmas we easily get the required result, because $n>p$ from $p|f(A)$, for $A \neq X$.

aleksam wrote: Lemma 1: $f(X)=\frac{(n-1)!}{\prod_{v \neq X}s_{X}(v)}$. Proof:The proof is inductive. Root the tree in $X$, and let it's childrens be $A_1, A_2, \cdots , A_n$. Now, proceed to computing $f(X)=f(A_1) \cdots f(A_n) \frac {n!}{s_X(A_1)! \cdots s_X(A_n)!}$, and after the easy computation, we get the desired result. I think there is something wrong about this claim. For example could you explain why: \[f(X)=f(A_1) \cdots f(A_n) \frac {n!}{s_X(A_1)! \cdots s_X(A_n)!}\]It would be true if instead of $f(A_i)$ we put $f'(A_i)$, where $f'(A_i)$ means the number of ways the branch of the tree (a subtree), initiated from $A_i$ and away from $X$, can be enumerated. As you see, it's something different than $f(A_i)$.

There is a very easy solution actually. Let's color the cities in two colors: white and black so that no two linked cities have the same color. Then, we can easily know that the sum of the result of countings for the same colored cities are the same. Which means that the result of the last city is also a multiple of 2016.

Yes, it was the official solution. The problem was proposed by Fedor Petrov.

I got a strange result while solving this problem. For adjacent two cities $ u,v $ and the number of cities connected to $ u $ and $ v $ are $ x-1,y-1 $. ( I mean the number of cities that we can travel from $ u $ without touching $ v $ and the same for $ u $. ) Then, I got $ f(u):f(v)=x:y $.

toto1234567890 wrote: There is a very easy solution actually. Let's color the cities in two colors: white and black so that no two linked cities have the same color. Then, we can easily know that the sum of the result of countings for the same colored cities are the same. Which means that the result of the last city is also a multiple of 2016. please let me know how to prove it

toto1234567890 wrote: There is a very easy solution actually. Let's color the cities in two colors: white and black so that no two linked cities have the same color. Then, we can easily know that the sum of the result of countings for the same colored cities are the same. Which means that the result of the last city is also a multiple of 2016. Here is a way to prove it found by Dor Mezer: Clearly the vertices numbered $1$ and $2$ are adjacent and have different colors. We'll provide a bijection between countings of white vertices and counting of black vertices. Simply switch $1$ and $2$. It clearly works.

Consider the graph equivalency of the problem. We assign a natural number to each of the edges and let the weight of a vertice be the sum of all numbers in the edges it is connected in. It is equivalent to the number of labelings in which one of them is 1 and the other is 2. Now by induction we can finish the proof.

kreegyt wrote: I'm sorry but I have some (stupid) questions: -are all the pairs of cities linked two-way? since you wrote that "some" of them are, and then for "every pair" there's one aviaroute -what is an interchange -in which order do you visit the cities since you tlak about ascending order. You start from X, you go to one city Y linked to X by an aviaroute, and then? I'm really sorry if these questions are stupid, and thanks for the translations. Suppose that cities $A$ and $B$ are connected by a straight flight. The same for cities $B$ and $C$. Obviously, cities $A$ and $C$ are connected by one unique aviaroute, despite they are not connected by a straightflight. Cities $A$ and $B$ are also connected by one unique aviaroute.

We rephrase the question: rephrased question wrote: Take $M\in \mathbb{N}$. Given is a tree with $n$ vertices. For each vertex $v$ let $f(v)$ be the number of ways to assign $1$ to $n$ to the vertices, such that on any path beginning on $v$, the assigned numbers are in ascending order. Suppose $n-1$ of $f(v)$s are multiples of $M$. Show the last is also a multiple of $M$. Let the original tree be $\mathcal{T}$. Define $\mathcal{T}_{v_1-v_2}$, where $v_1$ and $v_2$ are adjacent, as the subgraph obtained by considering only vertices closer to $v_1$ than $v_2$. One way to visualise this is to consider the edge $v_1-v_2$, cut it, and take the $v_1$ half of it. In particular, $\mathcal{T}_{v_1-v_2}\cup \mathcal{T}_{v_2-v_1}$ would be $\mathcal{T}$, without the edge $v_1-v_2$. Claim: If $v_1$ and $v_2$ are adjacent, then $$\frac{f(v_1)}{|\mathcal{T}_{v_1-v_2}|}=\frac{f(v_2)}{|\mathcal{T}_{v_2-v_1}|}.\hspace{20px}\text{------ }(\star)$$Intuitively, the $f$ values of two adjacent vertices is proportional to the size of their subgraph when we cut the edge. Proof. 1. Let $A_{v_1}$ be the set of the assignments satisfying the condition with starting vertex $v_i$. i.e. $|A_{v_1}|=f(v_1)$. We henceforth view assignments as an arrangement of the vertices in a row, where being at position $i$ represents being assigned number $i$. 2. Let $B_{v_1}$ be the set of possible assignments of $1$ to $|\mathcal{T}_{v_1-v_2}|$ to the vertices of $\mathcal{T}_{v_1-v_2}$ such that any path in $\mathcal{T}_{v_1-v_2}$ starting on $v_1$ is numbered ascendingly. i.e. $|B_{v_1}|$ would be $f(v_1)$ in $\mathcal{T}_{v_1-v_2}$. 3. Let $C_{v_1}$ be the set of possible black/white colourings of a row of $n-1$ squares such that exactly $|\mathcal{T}_{v_1-v_2}|-1$ of them are black. 4. Define $A_{v_2},B_{v_2},C_{v_2}$ similarly. We claim that there is a bijection taking triplets $\{x\in B_{v_1},\hspace{2px} y\in B_{v_2},\hspace{2px} z\in C_{v_1}\}$ to elements of $A_{v_1}$. This is because: 1. Given an assignment $A_{v_1}$: Consider only vertices in $\mathcal{T}_{v_1-v_2}$. These give an element of $B_{v_1}$. Consider only vertices in $\mathcal{T}_{v_2-v_1}$. These give an element of $B_{v_2}$. Now colour elements in the original assignment black if they were in $\mathcal{T}_{v_1-v_2}$. Ignore the first element, which is $v_1$. Replace the numbers with squares, keeping the colouring. This gives an element of $C_{v_1}$. 2. Given elements $x,y,z$, we can construct the original assignment in reverse order as the steps above. Since it is a bijection, this means $|B_{v_1}|\cdot |B_{v_2}|\cdot|C_{v_1}|=|A_{v_1}|=f(v_1)$. Similarly, $|B_{v_2}|\cdot|B_{v_1}|\cdot|C_{v_2}|=|A_{v_1}|=f(v_2)$. This means $\frac{f(v_1)}{|C_{v_1}|}=\frac{f(v_2)}{|C_{v_2}|}$. But $|C_{v_1}|=\binom{n-1}{|\mathcal{T}_{v_1-v_2}|-1}$ and $|C_{v_2}|=\binom{n-1}{|\mathcal{T}_{v_2-v_1}|-1}=\binom{n-1}{|\mathcal{T}_{v_1-v_2}|}$ since $|\mathcal{T}_{v_1-v_2}|+|\mathcal{T}_{v_2-v_1}|=n$. Doing the algebra, we get $\frac{f(v_1)}{|\mathcal{T}_{v_1-v_2}|}=\frac{f(v_2)}{|\mathcal{T}_{v_2-v_1}|}$ as desired. We now completely ignore the original definition of $f$, and instead treat it as any function satifying ($\star$), where $f$ takes integer values. We want to show: if $M$ divides $n-1$ values of $f$, it divides the last as well. Obviously, we only need to show the result over prime powers. Note that if $\gcd(f)>1$, we can divide it out. Hence assume their $\gcd$ is 1. Suppose on the contrary that there is a vertex $K$ such that $p\nmid f(K)$ but divides everything else. We show that this is impossible. We root the tree at $K$. By rooting it, we can define the subgraph of any vertex $v$, which we call $\mathcal{S}_v$, as the subgraph formed by considering only vertices for which we have to pass through $v$ to get to $K$. Note that $\mathcal{S}_K=\mathcal{T}$. We can also define the depth of a vertex: the distance (# of edges) from it to $K$. Consider the vertices adjacent to $K$, say $v_1,v_2,\cdots ,v_t$. If there is some $v_i$ such that $p\nmid |S_{v_i}|$, then $f(K)=f(v_i)\cdot \frac{n-|S_{v_i}|}{|S_{v_i}|}$ by the claim above. Since $p\mid f(v_i)$, $p\mid f(K)$ as well, a contradiction. Otherwise, $p\mid |S_{v_i}|$ for all $i$, which means $p\mid n-1$. Let $v_p(n-1)=X$. There must be some vertex $v_i$ such that $v_p(|S_{v_i}|)\le X$. Note that since $p\nmid f(K)$, $v_p(f(v_i))\le X$. We claim there exists a sequence of vertices $a_0=K,a_1=v_i,a_2,a_3,\cdots$ such that the depth of $a_i$ is $i$, $v_p(|f(a_i)|)\le X$, and $a_i$ is connected to $a_{i+1}$ (we end when we hit a leaf). We do this by induction, with $i=0$ true by definition while $i=1$ is done above. Suppose we have found $a_0,a_1,\cdots a_i$. We claim that we can find a suitable $a_{i+1}$. Let $a_{i}$ be connected to vertices $u_1,u_2,\cdots u_d$ (we remove $a_{i-1})$. Since $\frac{f(u_j)}{|S_{u_j}|}=\frac{f(a_i)}{n-|S_{u_j}|}$, if there is some $p\nmid |S_{u_j}|$ then we can pick it and we are done. Else we must have $p\mid |S_{u_j}|$ for all $j$. Let $y$ be $\min v_p(|S_{u_j}|)$ and WLOG $y=v_p(|S_{u_1}|)$. By definition we have $|S_{a_i}|\equiv 1 \pmod{p^y}$. Since $\frac{f(a_{i})}{|S_{a_i}|}=\frac{f(a_{i-1})}{n-|S_{a_i}|}$, we have $v_p(f(a_i))=v_p(f(a_{i-1}))-v_p(n-|S_{a_i}|)\le X-v_p(n-|S_{a_i}|)$ by the induction hypothesis. If $v_p(|S_{a_i}|-1)\ge X$ then $v_p(n-|S_{a_i}|)\ge X$ so $v_p(f(a_i))\le 0$, a contradiction. Thus $v_p(|S_{a_i}|-1)<X$ which means $v_p(n-|S_{a_i}|)=v_p(|S_{a_i}|-1)$. This means $v_p(f(a_i))\le X-v_p(|S_{a_i}|-1)\le X-y$. Since $\frac{f(u_j)}{|S_{u_1}|}=\frac{f(a_i)}{n-|S_{u_1}|}$, we get $v_p(f(u_j))=v_p(f(a_i))+v_p(|S_{u_1}|)\le X-y+y\le X$. Thus $u_1$ satisfies the conditions and our induction is done. Finally, consider the last 2 vertices $a_m, a_{m+1}$ of the sequence. $a_{m+1}$ is a leaf. Thus $f(a_m)=(n-1)f(a_{m+1})$. Then $v_p(f(a_m))=v_p(n-1)+v_p(f(a_{m+1}))\ge X+1$, a contradiction to it being $\le X$. We are finally done.