Surprisingly easy to misread T_T the problem itself is much less scary than it looks. Answer: $\left\lceil \log_2 n \right\rceil$. The idea is to notice that for a graph with $2m$ vertices, you can make one color a directed $K_{m,m}$, reducing to two graphs with $m$ vertices. That's all.

This was cute. Here's some philosophizing from test-solving if anyone's interested: Quote: I'd say it's #2 level, maybe a little easier/harder depending on whether one's seen the undirected ingredient (or a variant) before. The key is that the permissible single-color induced graphs are bipartite (as no vertex has both out- and in- neighbors of a single color). [One can reach this idea in many ways---from the construction direction, small cases or greedily choosing edges in a transitive tournament; from the proof/bounding direction, just thinking about what the single-color graphs look like.] For the corresponding undirected problem on minimum edge-coverings of K_N using bipartite graphs, we get an answer of ceiling(log_2(N)) by a straightforward induction. And the resulting bound for the original problem (from this undirected ingredient) is tight in transitive tournaments because in the induction, we can point all the edges from one group to the other, and compatibly order the vertices step by step. The "undirected ingredient" is in PFTB somewhere; I want to say the chapter on cycles (in graph theory), but not sure.

Sorry if this is equivalent to what is said above, I did not understand some of the terminology. Let $C(n)$ be the minimum directed-edge-chromatic-number of all tournaments on $n$ vertices. 1. I claim that $C(2^k)\le k$ Proof: I will prove it by induction. For $k=1$ clearly it is true. Suppose it is true for $k$. Consider a tournament on $2^{k+1}$ vertices. Split it into two tournaments $A$ and $B$ with $2^k$ vertices and color each with colors $1,...,k$ independently. Now direct each of the remaining edges from $B$ to $A$ and color them with color $k+1$. So $C(2^{k+1})\le k+1$ so we are done by induction. 2. $C(n)>k$ for $n>2^k$ Proof: Suppose to the contrary that we can color the tournament with $n$ vertices with only $k$ colors $1,...,k$. Consider any vertex of the graph, and assume it is incident to some edges of color $i$. Either all of these edges are going into the vertex or leaving it, otherwise the problem condition would be violated. As a result, to each vertex we assign a $k$-bit binary number, where the $i$-th bit is $0$ if the edges of color $i$ are going into the vertex or $1$ if they are going out. If there are no edges of color $i$ incident to this vertex, we just assign a random number to the $i$-th bit as it won't affect the proof. Since $n>2^k$, two vertices $V$ and $W$ must be assigned the same binary number. However consider the directed edge joining $V$ to $W$ of color $j$. Since it is leaving one of the vertices and entering the other, the $j$-th bit in binary is different for $V$ and $W$, which contradicts our assumption. Therefore using 1. and 2. in combination, $k-1<C(2^k)\le k$, so $C(2^k)=k$, and for $2^k<n<2^{k+1}$, $C(n)=k+1$, which implies that $C(n)=\left\lceil \log_2 n \right\rceil$ as desired.

math154 is referring to 1983 ISL Problem 1 It is indeed in the Problems from the book chapter "cycles, paths, and other ways".

My solution may be similar to the one posted above, but anyway here it goes: The answer is $\lceil \log_2n\rceil$. We start by proving that if a tournament $G$ admits a proper directed-edge-coloring with $k$ colors, then $2^k\geq n$. Let $V=\{v_1, \ldots, v_n\}$ be the set of vertices of $G$, and for each $i\in\{1, \ldots, n\}$ let $A_i$ be the set of colors used in edges starting from $v_i$. The key claim is the following: Claim: If $i\neq j$, then $A_i\neq A_j$. Proof: Assume, for the sake of contradiction, that $A_i=A_j$ for some $i\neq j$. Take the edge that links $v_i$ and $v_j$; without loss of generality, assume it is directed from $v_i$ to $v_j$, and let $c$ be its color. Then $c\in A_i$, and, therefore, $c\in A_j$, by our assumption; but then there is an edge starting in $v_j$ with color $c$, as well as an edge ending in $v_j$ with the same color, contradiction. $\square$ Since the set of $k$ colors has $2^k$ distinct subsets, $2^k\geq n$. Now we will prove that for each non-negative integer $k$ there is a tournament with $2^k$ vertices that admits a proper directed-edge-coloring with $k$ colors. The proof is by induction: for $k=0$ the trivial tournament with $1$ vertex and no edges fulfills this condition. Now assume we have such a tournament $G$ with $2^k$ vertices: create a second copy $G'$ of it and link each vertex of $G$ to each vertex of $G'$ with a directed edge, and color all this edges with a new color, different from the ones already used. This clearly gives a proper directed-edge-coloring of a tournament with $2^{k+1}$ vertices, establishing the induction step. We can obviously extend this construction bacwards by removing vertices and corresponding edges, therefore the answer to the problem is the smallest non-negative integer $k$ satisfying $2^k\geq n$, which is $\lceil \log_2n\rceil$.

v_Enhance wrote: A tournament is a directed graph for which every (unordered) pair of vertices has a single directed edge from one vertex to the other. Let us define a proper directed-edge-coloring to be an assignment of a color to every (directed) edge, so that for every pair of directed edges $\overrightarrow{uv}$ and $\overrightarrow{vw}$, those two edges are in different colors. Note that it is permissible for $\overrightarrow{uv}$ and $\overrightarrow{uw}$ to be the same color. The directed-edge-chromatic-number of a tournament is defined to be the minimum total number of colors that can be used in order to create a proper directed-edge-coloring. For each $n$, determine the minimum directed-edge-chromatic-number over all tournaments on $n$ vertices. Proposed by Po-Shen Loh The answer is $\lceil \log_2n \rceil.$ A construction is as follows: Label the vertices $\{1,2,3, \cdots n\}$ and write each label in binary. Then for any two vertices $u,v,$ let $k$ be the first position from the right which is different in their binary representations. Then if the $k$th digit is $0$ in $u$ and $1$ in $v,$ then draw the edge $u \to v.$ Clearly, this works. We now prove the result by induction on $n.$ It is trivial for $n=1.$ Now say we want to prove the result for $n,$ and assume wlog that $n$ is even, say by deleting a vertex if needed. Fix a color, say red, and consider the set $S$ of all the vertices formed by the tails of these red edges. Consider the partition of the vertices of our graph into $S, V \setminus S.$ At least one of these sets has a size at least $n/2,$ say $S.$ Then we claim that there cannot be any red edge "contained" in $S.$ Indeed, if there is, then its head would lie on some $v \in S$ (since it is contained in $S)$ which already has a red edge going out of it, contradicting the hypothesis. [asy][asy] import geometry; import olympiad; unitsize(1cm); int x=1; pair A=(-x,-x); pair B=(x,-x); pair C=(x,1.5+x); pair D=(-x,1.5+x); draw(A--B--C--D--cycle, black); dot((0,1.5)); dot((-0.2,0)); draw((0,1.5)--(2,1), arrow=Arrow(HookHead),red); draw((-0.2,0)--(0,1.5), arrow=Arrow(HookHead), red); label("$v$",(-0.2,1.7)); [/asy][/asy] Hence, $S$ has $n/2$ vertices and no edge is red. So $$\chi \ge 1+\log_2 (n/2)=\log_2(n)$$Hence the induction is complete. $\blacksquare$ Motivational note: The basic idea was that if $\chi=f(n)$ is the desired number, then we want to recursively discover $f(n).$ One trick is by trapping some vertices into a set that avoids a particular color. How to do this can be discovered by experimentation. For example, one discovers that there exists no monochromatic triangle. This idea can be generalized by saying that if an edge $e$ joins the tails of two edges of the same color $c,$ then $e$ itself cannot be colored $c.$ This is a useful fact and remains true on replacing tails by heads. So a greedy way would be to join the tails (or heads) of all the red edges. And looking at the worst case, we would want to join the tails of the red edges if they are more in number than the heads of the red edges. This is precisely the argument of dividing the vertex set into $S$ and $V \setminus S$ above, and the solution is not too hard to obtain after this.

Let $f(n)$ be the answer for $n$ vertices; I claim $\lceil log_2 n\rceil$. First choose a color $c$. Let $S$ be the set of all vertices which have an edge of color $c$ from $V$ to another vertex, and let $T$ be the set of all vertices $V$ which have an edge of color $c$ going to $V$. We see that $S, T$ are disjoint, so we have $|S|+|T|\le n$, so either $|S|\le n/2$ or $|T|\le /2$. Suppose $|S|\le n/2$; then, $|G\ S|\ge n/2$, so $G\S$ has at least $f(n/2)$ colors. But there are no edges of color $c$ in $G\S$, so it has at most $f(n)-1$ colors. Hence, $f(n)-1\ge f(n/2)$, completing the induction. Construction for $f(n)$: label the vertices $1$ through $n$, and for all $i>j$, direct the edge between $i, j$ from $j$ to $i$. Next, let $k$ be the largest number such that the $k$th place in the binary representation of $i$ is 1 while the $k$th place in the binary representation of $j$ is 0 (every number is written with infinitely many leading 0's). It is not hard to prove this construction works.

Solved with jclash, mfang92, nukelauncher. The answer is $\lceil\log_2 n\rceil$. Assume such a tournament on $n$ vertices can be colored with $k$ colors. For each color $i\le k$, we may designate each vertex as either $i$-incoming or $i$-outgoing, meaning the vertex is incident to an incoming edge of color $i$ or an outgoing edge of color $i$, respectively. By hypothesis no vertex may be both $i$-incoming and $i$-outgoing, and if a vertex is not incident to any edge of color $i$, it does not matter whether we designate it as $i$-incoming or $i$-outgoing --- for convenience say it is $i$-incoming. We assign to each vertex a signature --- a binary string of $k$ bits such that the $i$th bit equals $0$ if the vertex is $i$-incoming and $1$ if the vertex is $i$-outgoing. Note that: no two vertices may have the same signature, since otherwise it is impossible to draw an edge between them; if two vertices have different signatures, then it is possible to draw an edge between. There are $2^k$ possible signatures, so we must have $n\le2^k$. Conversely if $n\le2^k$, then we can select a subset of the $2^k$ possible signatures and assign them to the vertices. Between any two vertices draw an edge, thereby forming a valid tournament. Thus the answer is $\lceil\log_2 n\rceil$.

A great problem to my 100th post here's my solution: I'll claim that the answer is $\lceil\log_2 n\rceil$ let $f(n)$ be minimum directed-edge-chromatic-number over all tournaments on $n$ vertices. claim(1):$n \ge f(2^n)$ proof: I'll prove it inductively it's obviosly for $n=1$ now imagine the tournament of $2^{n+1}$ is the $3-D$ space and split it into tow tournaments each of $2^n$ vertices one above and the other is below do the inducton hypothesis for each part then draw a directed edge from every vertex below to every vertex above and color them in a new color so this clearly work $\blacksquare$ claim(2): $f(2^n +1) >n$ proof: suppose the contrary assign to each vertex $v_i$ a subset $S_i$ of the set $1,2,3,...,n$ so that the incoming edge to $v_i$ is colored from $S_i$ since $f(2^n+1) \le n$ there's two vertecis $v_i,v_j$ such that $S_i=S_j$ but $(v_j\rightarrow v_i) \in S_i \implies (v_j\rightarrow v_i) \in S_j$ a contradiction $\blacksquare$ thus $n+1 \ge f(2^{n+1}+1) \ge f(2^{n+1}+m) \ge f(2^n+1) \ge n+1$ thus $f(n)=\lceil\log_2 n\rceil$ and we win

The minimum value of $\chi$ is $\lceil \log_2 n\rceil$. First, we provide an inductive construction. For $n=2$, the construction is a single edge. To get from construction for $2^n$ to construction for $2^{n+1}$, make two copies $G_1,G_2$ of the construction for $2^n$ then make all edges between vertices $v_1$ of $G_1$ and $v_2$ of $G_2$ are $v_1\to v_2$ and colored with the $n+1$-th color. Note this construction is sufficient because to obtain a construction for $\chi$ with $n$ not a power of two, all we need do is delete vertices of the graph. Now, suppose that we can color a graph of $2^n+1$ vertices with $n$ colors. For each vertex $v$, let $C(v)$ denote the set of colors of edges leading towards $v$. By the pigeonhole principle, some two vertices $u,v$ have the same sets $C(v),C(u)$. WLOG suppose there is an edge $u\to v$. This edge must have a color in $C(u)=C(v)$, but this contradicts the assumption of the problem.

The answer is $\lceil{ \log_2 n \rceil}$. Suppose for the sake of contradiction that a $2^k+1$-vertex graph can be colored with at most $k$ colors. There must exist two vertices in the graph with the same set of colors on edges directed outwards, say $u$ and $v$. Then it is impossible to draw either $u \to v$ or $v \to u$, a contradiction. It suffices to show that this minimum can be attained whenever $n=2^k$, since we can delete vertices off the graph. We show this by induction; divide the graph into two disjoint sets of vertices with size $2^{k-1}$, say $A$ and $B$. Let all edges from a vertex in $A$ to a vertex in $B$ go from $A \to B$. Now color all such edges a color $c$, and note that by the inductive hypothesis the edges in $A$ and $B$ can be colored with $k-1$ colors $\neq c$. Thus the total number of colors used is equal to $(k-1)+1 = k$, as desired.

The key observation is that our problem is equivalent to the following problem: Reduced Problem wrote: What is the minimum number of colors $f(n)$ required to color edge of a (undirected) $K_n$ such that there is no monochromatic odd cycle? It is easy to see if the original problem has a $k$-coloring, then our new problem also has a $k$-coloring. Conversely, if our new problem has a $k$-coloring, then we color the directed graph of our original problem accordingly. We look at any particular color, and we just have to assign directions accordingly. Since there is no odd cycle, so for that color we can divide the graph into two components $A,B$. Then for any edge, we always directed towards the vertex of $B$. Now lets solve our new problem. If we look at a particular color and use the sub-graph in that color is bipartite, then considering the bigger of the two components we directly get $$f(n) = f \left( \left\lceil \frac{n}{2} \right\rceil \right) + 1$$which directly gives $f(n) \ge \left\lceil \log_2 n \right\rceil$ (by induction on $n$). Now we prove we can color $K_{2^m}$ with $m$ colors. We again have to induct on $m$. Divide the graph into two components $X,Y$ with size $2^{m-1}$ each. color any $X-Y$ edge by the same color. Now by our induction hypothesis, $X$ can be colored by some other $m-1$ colors. Color $Y$ also by those same $m-1$ colors. So we obtain a $K_{2^m}$ can be colored by $m$ colors. Lastly, note that for any $n < 2^m$, we can color $K_n$ by $m$ colors by removing some vertices from $K_{2^m}$. $\blacksquare$

We claim the answer is $\lceil \log_2 n \rceil$. We can inductively construct a graph on $n$ vertices by taking the colorings for a $\lfloor n/2 \rfloor$ tournament and a $\lceil n/2 \rceil$ tournament, and connecting them with $\lfloor n/2 \rfloor\lceil n/2 \rceil$ edges of a new color. To prove that this is optimal, assume otherwise. Each vertex is either only the starting point of edges of color $i$ (call this property $i$-good), or is only on the receiving end (or doesn't coincide with any.) We can now assign a string of $1$s and $0$s for each vertex, with position $i$ of vertex $v$ corresponding to whether or not $v$ is $i$-good. Since the graph is complete, no two vertices can share the same label, as the color $c$ of the edge between them has label $1$ on one vertex but $0$ on the other. So, if we use $k$ colors, we can only have $2^k$ vertices, done.

It's a useful trick by looking at the the sets of monochromatic edges in graph coloring problems. However the trick is always ignored..... (For example, in vertex coloring, the coloring number can also be defined by the smallest number to divide the vertex set into independent sets, it's trivial but useful)

Knowing the official solution of IMC 2022/4 helps. The answer is $\lceil {log_2(n)} \rceil$. Consider a working coloring with $k$ colors; assign each vertex a binary string of length $k$ such that there is a $1$ on the $i-$th position if there is an incoming edge of color $i$ and $0$ otherwise (obviously the strings are well-defined due to the problem statement). No two of these strings can coincide, otherwise there can't be an edge between these two vertices (they will differ in some position). Hence $2^k \leq n$ and we are done with the proof of the bound. This implies the construction as well: select $n$ binary strings with length $k=\lceil {log_2(n)} \rceil$; for any two vertices $a,b$, let their strings differ in the $i-$th position; add an edge of color $i$ directed from the sequence with $0$ in this position to the sequence with $1$.

The answer is $\chi = \lceil \log_2 n \rceil$. For every color $c$, there exists a set $A_c$ of vertices that contain only heads of red arrows, and a set $B_c$ of vertices that contain only tails of red arrows. First for any graph, I claim that I can perform operations to reach a tournament with $\chi$ at most equal to the $\chi$ of the original graph and for which there exists a color $c$ with $|A_c| \leq \frac n2$ and $|B_c| \leq \frac n2$. Suppose that there were none in the original graph. Then, take some color $c_1$ in the original graph, and add all vertices not currently in $A_{c_1}$ or $B_{c_1}$ into one of these sets by re-coloring arrows, which does not increase $\chi$. Now, because it is impossible to reach such a configuration in the original graph, and $A_{c_1} \sqcup B_{c_1} = V(G)$, we must WLOG have $|A_{c_1}| < \frac n2$. We may color all edges between $A_{c_1}$ and $B_{c_1}$ red in a bipartite fashion. Then, there must exist a color $c$ with $A_c, B_c \subset A_{c_1}$ as it is impossible to draw an edge with color $c$ between $A_{c_1}$ and $B_{c_1}$. However, we must have $|A_c|, |B_c| < |A_{c_1}| < \frac n2$, as needed. In this configuration, we may now do something similar, taking every vertex in the graph not in $A_c$ or $B_c$ and assigning them to each, re-coloring corresponding edges such that $|A_c| = |B_c| = n/2$ when $n$ is even and $\frac{n-1}2, \frac{n+1}2$ respectively when $n$ is odd. However, notice that it now suffices to color $A_c$ and $B_c$ independently of each other (none of them can use the color $c$), so $$\chi(n) = \chi(n/2) + 1 \text{ or } \max(\chi((n+1)/2), \chi((n-1)/2))) + 1.$$Now we can simply induct up to get the desired conclusion.

The answer is $\lceil \log_2(n)\rceil$. Note that the condition implies that if a vertex has an ingoing edge of some color, it cannot have an outgoing edge of that color. The key idea is to label each vertex with the subset of colors of ingoing edges that it has. Claim: In a proper coloring, no two vertices can have the same subset label. Suppose FTSOC that vertices $A$ and $B$ both have the subset $S$. Then, clearly $S\neq \emptyset$ since there has to be some edge between $A$ and $B$ of some color. Then, note that the edge between $A$ and $B$ must have some color $c\in S$. WLOG this edge goes from $A$ to $B$. However, by definition of $S$, $A$ also has an ingoing edge of color $c$, contradiction. Thus, if there are $k$ colors, $2^k\geq n$ so $k\geq \lceil \log_2(n)\rceil,$ which shows the bound. To show attainability, we first show that $2^k$ vertices can be done with $k$ colors. We will use induction. This is clearly true for $k=1$. For $k+1$, partition the $2^{k+1}$ vertices into two sets of $2^k$ vertices. In each set, make a coloring with $k$ colors which we know is possible by induction. Then, have all edges between vertices in two different sets go from the first set to the second, and color all such edges in the final $k+1$th color. This gives a valid $k+1$ coloring for $2^{k+1}$ vertices. Since $2^k$ vertices can be done with $k$ colors, we can also delete vertices as needed to get anything between $2^{k-1}+1$ and $2^k$ with $k$ colors. Hence, the answer of $\lceil \log_2(n)\rceil$ is achievable, so we are done.

The answer is $\lceil \log_2(n)\rceil$. Suppose that a tournament on $n$ vertices labeled $1, 2, \ldots, n$ can be colored with $k$ colors labeled $1, 2, \ldots, k$. Construct a $n \times k$ matrix $A$ where $a_{ij}$ is $1$ if there is an outgoing edge of color $j$ incident to vertex $i$ and $0$ otherwise. Note that in $A$: no two rows $r$ and $s$ can be the same, or else it is impossible to draw an edge between vertices $r$ and $s$; if two rows $r$ and $s$ are different from each other, it is possible to draw an edge between vertices $r$ and $s$. Thus, all rows of $A$ are distinct. We can quickly obtain the bound $n \le 2^k$ if colorings with $k$ colors exist by noting that there are $2^k$ binary strings of length $k$. On the other hand, suppose that $n \le 2^k$ and we want to use $k$ colors. Then select a subset of $n$ binary strings of length $k$ and use them to construct the rows of a $n \times k$ matrix. The tournament corresponding to this matrix is valid, so a coloring using $k$ colors works iff $n \le 2^k$, or when $k \ge \lceil \log_2(n)\rceil$, and we are done.

Same as others. The answer is $\lceil {\log_2(n)} \rceil$. Suppose the minimum is obtained with k colors. Give each vertex v a string of length k with a 1 in the $i$th position when there's an incoming edge of color $i$, and 0 otherwise. Note that all strings are distinct, otherwise they can't be connected by some color j (there will be a 0 in one and 1 in the other); in particular, $2^k \le n$. For the construction, take any two vertices u,v, differing in the $i$th place, represented by adding an edge of color $i$, directed from 0 to 1 in that place. (Note that in this way, any two vertices differ in EXACTLY one spot.) We conclude.

We claim that $\chi = \left\lceil \log_2{n} \right\rceil$. We first show that a $2^n$ tournament can be colored in at minimal $n$ colors. Suppose that a $2^{n-1}$ tournament can be colored in at minimal $n-1$ colors, and that inductively when this tournament can be $n-1$ colored, there exists a vertex such $n-1$ edges all colored differently point toward it, and thus all other vertices point at it, call it the pointed at vertex. This holds for the base case of $n = 1$. Then, let $T$ be a $2^n$ tournament. We first show $T$ must be colored in at most $n$ colors. We can subdivide $T$ into two $2^{n-1}$ tournaments $A$ and $B$. If $A$ or $B$ is not colored in only $n-1$ colors the result holds. We can color all the connections between $A$ and $B$ a new color. This minimal coloring can be attained by having all edges be directed from $A$ to $B$ and being colored the new color. It remains to show that a $2^{n}+1$ tournament requires at least $n+1$ colors. FTSOC assume it can be colored in $n$ colors. Then there must be two vertices with the same colors being output by pigeonhole, which then can't be connected, contradiction.

Not to bad! We claim that $\chi = \lceil \log_2 n \rceil$. For a fixed $\chi$, consider a tournament on $n$ vertices we denote as $V_i$ for integers $1 \le i \le n$. Call the colors $1, 2, \dots, \chi$. Suppose a receiver of a vertex $V_i$ is a directed edge that points to $V_i$. We can assign a subset $S_i$ to each vertex $V_i$ that contains the colors of every receiver of it. First, we claim that no vertices have the same $S_i$. For the sake of contradiction, suppose there exists integers $1 \le j, k \le n$ such that $S_j = S_k$. Let $c$ be the color of the edge between $V_j$ and $V_k$. Clearly $c \in S_j, S_k$ but this violates the condition of the problem. Hence, all $S_i$ are distinct. Observe that there are $2^\chi$ possible $S_i$, hence $n \le 2^\chi \implies \lceil \log_2 n \rceil \le \chi$. Now that we have shown the lower bound, we have to prove it is attainable for any $n$. When $n = 2^k$ for some nonnegative integer $k$, we get $k \le \chi$. We quickly aim to show that $\chi = k$ is achievable with induction. The $k = 0$ case is vacuously true, now if the claim is true for $k = t$ where $t$ is a nonnegative integer, let $G_{t}$ be a valid-colored tournament with a minimum of $\chi = t$ colors on $2^t$ vertices. Simply take two disjoint $G_{t}$, and direct every edge from one vertex of one $G_{t}$ to the other with a new distinct color. We obtain a valid-colored tournament with $n = 2^{t + 1}$ and $t + 1$ colors. Now for $2^t < n < 2^{t + 1}$ where $t$ is a nonnegative integer, simply take the valid construction for $n = 2^{t + 1}$ and remove a sufficient number of vertices and edges attached to those vertices, admitting a proper solution when $2^t < n < 2^{t + 1}$. Our proof is complete.

We claim our answer is $\boxed{\lceil \log_2n \rceil}$. We first show this is a lower bound through induction, with base case $n=1$ trivial. Consider a fixed color $C$. Place all vertices which are the starting points of an edge with color $C$ into set $A$, and the rest into set $B$. The inductive hypothesis tells us neither tournament subset has color $C$ edges. One of the subsets has at least $\tfrac n2$ vertices, so our lower bound is the desired \[\lceil \log_2\left(\frac n2\right) \rceil + 1 = \lceil \log_2n \rceil.\] To show attainability for powers of 2, simply duplicate the graph for $n=2^{k-1}$ and direct each vertex from one graph to all vertices of the other graph with a single color distinct from all previous colors. For non-powers of two, just chop off unnecessary vertices from the next power of 2. $\blacksquare$

We claim that the minimum value of $\chi$ is $\lceil \log_2 n\rceil$. We will provide a construction using induction. For the base n = 2, the construction is an edge. For the inductive step to go from $2^n$ to $2^{n+1}$, take two duplicates aka $G_1,G_2$ of the construction for $2^n$ and after that connect the edges between the vertices of $G_1$ and the vertices of $G_2$, which would be colored with the n+1-th color. The construction we now made is enough, since to get a construction for $\chi$ with $n \not = 2^k$, we just have to delete vertices of the graph $\Rightarrow$ from this we get that $\chi \leq \lceil \log_2 n\rceil$. Now assume that we can color a graph of $2^n+1$ vertices with only n colors. For each vertex v, let S(v) denote the set of colors of edges that go in v. There are $2^n$ possible sets. By Dirichlet, there exist two vertices u, w that have the same sets S(u), S(w). Now assume there is an edge $u \to w$. This edge must have a color in S(u) = S(w), but this contradicts the statement of the problem $\Rightarrow$ from that we get that $\chi \geq \lceil \log_2 n\rceil$ $\Rightarrow$ the answer is $\lceil \log_2 n\rceil$.

The answer is $\boxed{\lceil \log_{2} n \rceil}$. In order to prove this, we first show that a graph with $2^n+1$ vertices cannot be colored with $n$ colors. Suppose FTSOC the graph can be colored with $n$ colors. For any given vertex $x$, let $C(x)$ be the set of colors that are directed towards $x$. By the Pigeonhole Principle, there exists two vertices $u$ and $v$ such that $C(u)$ and $C(v)$ are identical. Then, we run into a contradiction when considering the edge between $u$ and $v$. Then, it suffices to prove that a graph with $2^n$ vertices can be colored with $n$ colors since we can arbitrarily remove vertices; we use induction to do so. The base case with $1$ vertex is vacuous. Then, given a graph with $2^n$ vertices, we may split it into two disjoint sets, $A$ and $B$, that have $2^{n-1}$ vertices each. Both $A$ and $B$ can be colored with $n-1$ colors due to our inductive hypothesis. Then, assume that all edges from a vertex in $A$ to a vertex in $B$ go from $A \to B$ and color them all a color $c$ that has not already been used. This results in a valid coloring and uses $n-1+1 = n$ colors.

Interesting troll problem...We claim that the minimun number of colors needed over all tournaments of $n$ vertices is $\boxed{\lceil \log_2(n) \rceil}$. Proof of necessity: Label the vertices to be $v_1,v_2, \cdots v_n$ then let $C_i$ be the color set of the edges "coming" from $v_i$ for a functional $k$-coloring, then notice that we cannot have $C_{\kappa}=C_{\ell}$ for $v_{\kappa} \ne v_{\ell}$ because if we did, suppose WLOG that $v_{\kappa} \to v_{\ell}$ is an edge of color $c \in C_{\kappa}$ then $c \in C_{\ell}$ as well but if $v_{\ell}$ had a positive outdegree this violates the problem condition and if it had outdegree zero then $C_{\ell}$ is null which also can't happen, therefore for each vertex $v_i$ their $C_i$ is a unique subset of the $k$ colors which means that $2^k \ge n$, which is enough to conclude $k \ge \lceil \log_2(n) \rceil$. Proof of sufficiency: Consider a vertex $v_i$ from the previous labeling and label it again by $i$ in base $2$, then suppose that for some $j \ne i$ we had that $1 \le i,j \le n$ and that on base $2$ they had a difference of digit in rightmost digit position $l$ then WLOG $i$ had $0$ and $j$ had $1$ then you draw $v_i \to v_j$ and give it color $l$ and do this for all other pairs of vertices to make an $n$ tournament, it's clear to see that this satisfies the problem condition as after a switch $0 \to 1$, the switch $1 \to 0$ does not have the same color, therefore only $\lceil \log_2(n) \rceil$ colors were used. Since both sides of the proof are complete, we are done

We claim that the answer is $\lceil \log_2 (n) \rceil.$ We show this by induction on $n.$ The base cases, $n=1,2$ are trivial. Now suppose that for all $n < \ell$ our proposition holds. Then suppose that we had $\ell$ vertices. If $\ell=2m,$ then by our inductive hypothesis we can use $\lceil \log_2 m \rceil$ for the two groups of $m$ vertices. Then, clearly we must use at least one extra color for the connections between these two groups (which forms the complete bipartite graph $K_{m, m}$), thus giving $\lceil \log_2 m \rceil+1=\lceil \log_2 \ell \rceil$ vertices, which is indeed the minimum. However, if $\ell=2m+1,$ with $2^k \leq m \leq 2^k-2,$ then by similar reasoning the minimum is $\lceil \log_2 m \rceil+1=\lceil \log_2 2m \rceil=\lceil \log_2 \ell \rceil.$ Finally, if $\ell=2m+1$ with $m=2^k-1,$ Then we can do the same thing as above, but this time we require at least $\lceil \log_2 (m+1) \rceil + 1 = k+1=\lceil \log_2 \ell \rceil$ vertices. Therefore, our induction is complete, and the answer is $\boxed{\chi = \lceil \log_2 (n) \rceil}.$

Each \(\text{c}:=\left\{0,\dots,\text{c}-1\right\}\)-diedge-colored (in the prescribed sense) tournament \(\mathcal{T}\) on vertices \(\text{n}:=\left\{0,\dots,\text{n}-1\right\}\) is readily seen to define an injection \(\iota_{\mathcal{T}}\colon\text{n}\to 2^{\text{c}}\) where vertex \(\text{i}\colon\text{n}\) is mapped to the subset of colors \(\text{j}\colon\text{c}\) for which \(\text{i}\) has an outedge of color \(\text{j}\). Thus \(\chi\left(\text{n}\right)\geq\left\lceil\log_{2}\left(\text{n}\right)\right\rceil\). Conversely, each injection \(\iota\colon\text{n}\to 2^{\text{c}}\) given vertices \(\text{n}:=\left\{0,\dots,\text{n}-1\right\}\) and colors \(\text{c}:=\left\{0,\dots,\text{c}-1\right\}\) defines a \(\text{c}\)-diedge-colored tournament \(\mathcal{T}_{\iota}\) (in the prescribed sense) where vertex \(\text{i}_{0}\) directs to vertex \(\text{i}_{1}\) iff the minimal element \(\text{j}\) of the symmetric difference of \(\iota\left(\text{i}_{0}\right)\) and \(\iota\left(\text{i}_{1}\right)\) belongs to \(\iota\left(\text{i}_{0}\right)\) and the didge defined has color \(\text{j}\). Thus \(\chi\left(\text{n}\right)\leq\left\lceil\log_{2}\left(\text{n}\right)\right\rceil\). I.e., \(\boxed{\chi\left(\text{n}\right)=\left\lceil\log_{2}\left(\text{n}\right)\right\rceil}\). \(\blacksquare\)