That's amazing!!!! I was thinking about creating a problem to submit for IMO, and I 'invented' exactly this problem! Pierre.

I think the answer is all $n,k$ for $n\geq k\geq 3$. Is it the true answer?

no, it isn't. it is clear that $k=1$ is not possible. maybe there's a typo?

Yes there was a typo that I have corrected now. I've spent impossibly much time on this problem, but the solution is so simple (if it's correct)

iura wrote: I think the asnwer is all $n,k$ for $n\geq k\geq 3$. Is it the true answer? possibly no-for instance when $n=4$,(4 circles, each circle has 6 pts on it),$k=6$ is possible,though for 3 circles,$k=4$ is not.so your answer may not be 'complete'.( of course,$k \leq 2(n-1)$ since there are so many pts on each circle when there are $n$ circles in all.)

Well, since there are used $n$ colors, we get $k\leq n$ isnt't it?

oh - i didn't see that stipulation in the problem.

Well, I guess our German friends (Darij, Peter) should know the solution. I'm waiting for a confirmation or an infirmation of my answer. If it's correct - I show my solution, if no - sorry for my $4$ useless posts

I haven't read the proposed solution, since this problem is the one I'm least interested in, but the answer is: either $2\leq k\leq n\leq 3$ or $3\leq k\leq n$. So your answer is almost completely correct. Darij

Well I guess $2\leq k \leq n$ holds only for small $n$. Here's the proof that $k\neq 2$ for $n\geq 4$ Firstly we draw a (non-symmetric) matrix $(A_{i,j})$ with entries $1,\cdots,n$ s.t. for $i\neq j$ $a_{ij},a_{ji}$ are the colors of the intersections of circle $\#i$ and $\#j$ and $a_{ii}=0$. Denote $R_i$ the row number $i$ and by $C_i$ the column number $i$. The we must have for every $i$ in $R_i \bigcap C_i$ exactly $k$ distinct non-zero numbers. Let's prove $k\neq 2$. Firstly draw $R_1,C_1$ containing WLOG colors $1$ and $2$. Now at step $i$ we add the cells from $R_i \bigcap C_i$ which are not already added. We see that for $2\leq i\leq n-1$ these cells can add at most one color that never met before (if it would add two colors, this color and the color of $a_{1i}$ would be three colors in $R_i\bigcap C_i$ Moreover, we don't perform step $n$ since all cells of $R_n\bigcap C_n$ are already drawn. Hence we get at most $2+(n-2)=n$ colors. Since there are exactly $n$ colors, equalitites hold everywhere so every step adds a new color. But if step $i$ adds a new color, this means that all already drawn elements of $R_i \bigcap C_i$ (i.e. $a_{1i},\cdots, a_{i-1,i},a_{i1},\cdots,a_{i,i-1})$ have same color. For a given $n>i>1$, denote $U_i$ these cells. Then $U_i$ is monochromatic. Moreover $U_i$ partition the cells of the matrix (except the diagonal which we completely ignore, and except $R_n \bigcap C_n$). But every $U_i$ intersects $R_1\bigcap C_1$ hence the colors of $U_i$ are at most two. Also, $R_n \bigcap C_N$ can have at most one more color hence $n \leq 3$. The case $n=2,3$ is easily handled. Now let's prove that if $3\leq k \leq n$ we can draw such a matrix. If $k=n$ it's easy so let's look at $k<n$. Consider $R_1=0,1,\cdots,1,2,3,\cdots,k$ ($1$ meets $n-k$ times). Now let $R_i$ be $R_1$ shifted cyclically by $i-1$ positions to the right. We easily see that the matrix satisfies our conditions but we have only $k$ colors. To make their number $n$ we proceed like this: Choose four cells $a_{i,j},a_{j,i},a_{n+1-i,n+1-j},a_{n+1-j,n+1-i}$ which have the same color. If this color is not $1$ and meets elsewhere in the table, the we can change the color of this four cell into $k+1$ and the conditions will hold. Then make the same procedure for color $k+2$ etc. It's kid's play to prove that we have enough colors to perform all these operations QED BTW Darij, why do you say this problem was least interesting to you? If you are weaker in some section of mathematics, you should pay more attention especially to it if you want to increase your IMO performance. How many persons solved this problem at the contest? Me, I wouldn't solve it because I've spent so much time on it..

iura wrote: BTW Darij, why do you say this problem was least interesting to you? If you are weaker in some section of mathematics, you should pay more attention especially to it if you want to increase your IMO performance. How many persons solved this problem at the contest? Me, I wouldn't solve it because I've spent so much time on it.. Darij is aware of the fact that he also should devote some times to other sections of math olympiads than geometry and inequality but you always do that what you like best. Especially it will not help him if he gets yet still more mature in his favourite topics. You just cannot get more than 7 points per problem. But I guess it is the same with you about combinatorics. BTW what happened to Sasha. I haven't seen him on AoPS/ML for a while ? The official solution can be found on the second page of this .pdf-file. But Darij gave already a link but not yet so specific.

Hey people, if I'll ever start with combinatorics, then surely not with such case-distinction problems... darij

Thank you Orl, but it seems to me that I know German only from some songs and they do not sing mathematics.. I could just check the answer. About Sasha, nothing happened to him. he just doesn't enter the site so often. I understand him, in autumn I also stopped entering the site for a while because it can be really a drug if you can't stop.. I remember me, for instance: I opened about $20$ pages, then closed Internet and started to solve them. Since I'm home at $5$ pm, until I finished with all these pages there was time for bed and I didn't have time to study anything else about mathematics. But everyone needs some books, so I decided to leave the site for a while. It's a good site if you want to practice your solving skills, but there is some theory you have to do.. About combinatorics, I keep my opinion: You, Orl, said that Darij will get his gold medal in Mexico. But he can eassily miss it if he can't solve a combinatorics problem because it's not his style, and another problem simply because it's the hardest..

iura wrote: About combinatorics, I keep my opinion: You, Orl, said that Darij will get his gold medal in Mexico. But he can eassily miss it if he can't solve a combinatorics problem because it's not his style, and another problem simply because it's the hardest.. Yeah. You are right. Even Myth thinks like that. Maybe we should motivate Darij to practise some combinatorics.

iura wrote: Now let's prove that if $3\leq k \leq n$ we can draw such a matrix. If $k=n$ it's easy so let's look at $k<n$. Consider $R_1=0,1,\cdots,1,2,3,\cdots,k$ ($1$ meets $n-k$ times). Now let $R_i$ be $R_1$ shifted cyclically by $i-1$ positions to the right. We easily see that the matrix satisfies our conditions but we have only $k$ colors. To make their number $n$ we proceed like this: Choose four cells $a_{i,j},a_{j,i},a_{n+1-i,n+1-j},a_{n+1-j,n+1-i}$ which have the same color. If this color is not $1$ and meets elsewhere in the table, the we can change the color of this four cell into $k+1$ and the conditions will hold. Then make the same procedure for color $k+2$ etc. It's kid's play to prove that we have enough colors to perform all these operations QED iura, I'm sorry, maybe I'm just quite sleepy right now, but I don't see how you can guarantee that there exist enough of such cells $a_{i,j},a_{j,i},a_{n+1-i,n+1-j},a_{n+1-j,n+1-i}$ which have the same color that is not $1$, such that you can add an additional $n-k$ colours. In fact, for $n=8$ and $k = 4$, I can't even find two elements $a_{i, j}, a_{j, i}, i \neq j$, which have the same color that is not $1$. Perhaps this is because I've misread what you've written. Would you mind giving an example to illustrate it more clearly? Thanks!

It's me sleepy now, but I'm able too realize you are right. I don't know what I thought with then, but now I think maybe we should correct it like this: Place the '0' in $R_i$ at place $i$ (to be on the diagonal) and the rest cells be the row $R_1$ shifted $i-1$ positions to the left. Now the matrix must be simmetric. Now is it OK? (Remember, I am sleepy, I can't check at the moment)

I don't see how to get a symmetric matrix by doing a cyclic shift of the row $R_1$ (excluding $0$ - is that what you meant?) to the left...

anyway, the final result and the method of the proof are correct - but i just wrote a paper and therefore am too lazy to post the correct proof(i had to ask christian sattler sitting next to me)

OK, all I've said yesterday is real non-sense so let me construct the example in another way(the notations are from the first solution): Call a $n$-'free' set of cells a set of $n$ cells s.t. in every line and column lies exactly one of the set. We want to color the matrix in $k$ colors, s.t. the sets of cells colored in each of the color $2,\cdots,k$ is free. Then, observe that if $a_{i,j}, a_{j,i}$ have the same color $c>1$ then we can change their colors to any new color, so we can eventually add new colors until we reach $n$ colors. Basing upon this main, idea, let's try to construct the example. Lemma: if from a $m \times m$ subtable we deleted some $m$-free sets, the we can pick up a new $m$ free-set unless we already deleted all cells. Proof is easy from Marriage Lemma. Now using this lemma, let's construct the example: Choose the inverse diagonal $x+y=t$ where $t$ is odd (so that it doesn't intersect the main diagonal). Then we can color all elements of this diagonal in color $i$. Using the lemma, we color more cells in color $i$ to yield a $n$-free set. Now taking $t$ every time as close to $b$ as possible (to reach a more cells on the diagonal), we can ensure that we have enough monochromatic pairs $a_{i,j}, a_{j,i}$ to be changed. The other cells not on the main diagonal shall be colored $1$. This ends the proof I'm sure I didn't explain clearly the proof, so let me give an example: $n=8, k=4$. Firstly the empty matrix: $0.......$ $.0......$ $..0.....$ $...0....$ $....0...$ $.....0..$ $......0.$ $.......0$ Now add color $2$ on the diagonal $x+y=9$ (closest to $8$): $0......2$ $.0....2.$ $..0..2..$ $...02...$ $...20...$ $..2..0..$ $.2....0.$ $2......0$ Then we add color $3$ on the diagonal $x+y=7$ and complete it with $2$ cells to produce a $n$-free set. $0....3.2$ $.0..3.2.$ $..03.2..$ $..302...$ $.3.20...$ $3.2..0..$ $.2....03$ $2.....30$ Finally, we add color $4$ on the diagonal $x+y=11$ (actually, it doen't matter anymore, since we already have enough pairs) $04...3.2$ $40..3.2.$ $..03.2.4$ $..302.4.$ $.3.204..$ $3.2.40..$ $.2.4..03$ $2.4...30$ The rest we complete with $1$. $04111312$ $40113121$ $11031214$ $11302141$ $13120411$ $31214011$ $12141103$ $21411130$ Finally, to add colors $5$,$6$,$7$,$8$ we change monochromatic pairs symmetric with respect to main diagonal. $04111312$ $40113171$ $11081614$ $11805141$ $13150411$ $31614011$ $17141103$ $21411130$ We are done.

Thanks, iura!

Let $f(n,k)=1$ if it's possible and $0$ otherwise; similarly define $g(n,k)=1$ if we can find a coloring such that $C_i$ has color $i$ (this allows us to modify the number of distinct colors per circle more easily), so that $f(n,k)\ge g(n,k)$. Obviously $g(2,2)=g(3,2)=g(3,3)=1$. For $k=3$ and $n\ge4$, we can label $C_1C_2,C_2C_3,\ldots, C_nC_1$ with \[\{1,2\},\{2,3\},\{3,4\},\{4,4\},\ldots,\{n,n\}\]and then set $C_iC_j=2$ if $j-i\not\equiv\pm1\pmod{n}$, so $g(n,3)=1$ for $n\ge4$ as well. Moreover, $g(n+1,k+1)\ge g(n,k)$. Indeed, if $g(n,k)=1$, then taking $C_{n+1}C_i=\{i,n+1\}$ for $1\le i\le k$ and $C_{n+1}C_i=\{n+1,n+1\}$ for $k+1\le i\le n$, we have $g(n+1,k+1)=1$. Thus $f(n,k)=g(n,k)=1$ for $2\le k\le n\le 3$ and $3\le k\le n$. It remains to show that for $n\ge4$, $f(n,2)=0$, so assume for the sake of contradiction that $f(n,2)=1$. WLOG, say that $C_1$ has colors $1$ and $2$, $C_2$ has colors $x\in\{1,2\}$ and $3$, and $C_3$ has colors $y\in\{1,2\}$ and $4$ ($k=2$, each color is used at least once, and all circles intersect $C_1$). Considering $C_2C_3$, we need $x=y$, so WLOG say $x=y=1$. Then for $4\le i\le n$, $C_i$ must have color $1$ by analyzing $C_1C_i,C_2C_i,C_3C_i$. But each color must be contained in at least two circles, so we need at least $2(n-1)>n$ circles, a contradiction.

iura wrote: OK, all I've said yesterday is real non-sense so let me construct the example in another way(the notations are from the first solution): Call a $n$-'free' set of cells a set of $n$ cells s.t. in every line and column lies exactly one of the set. We want to color the matrix in $k$ colors, s.t. the sets of cells colored in each of the color $2,\cdots,k$ is free. Then, observe that if $a_{i,j}, a_{j,i}$ have the same color $c>1$ then we can change their colors to any new color, so we can eventually add new colors until we reach $n$ colors. Basing upon this main, idea, let's try to construct the example. Lemma: if from a $m \times m$ subtable we deleted some $m$-free sets, the we can pick up a new $m$ free-set unless we already deleted all cells. Proof is easy from Marriage Lemma. Now using this lemma, let's construct the example: Choose the inverse diagonal $x+y=t$ where $t$ is odd (so that it doesn't intersect the main diagonal). Then we can color all elements of this diagonal in color $i$. Using the lemma, we color more cells in color $i$ to yield a $n$-free set. Now taking $t$ every time as close to $b$ as possible (to reach a more cells on the diagonal), we can ensure that we have enough monochromatic pairs $a_{i,j}, a_{j,i}$ to be changed. The other cells not on the main diagonal shall be colored $1$. This ends the proof I'm sure I didn't explain clearly the proof, so let me give an example: $n=8, k=4$. Firstly the empty matrix: $0.......$ $.0......$ $..0.....$ $...0....$ $....0...$ $.....0..$ $......0.$ $.......0$ Now add color $2$ on the diagonal $x+y=9$ (closest to $8$): $0......2$ $.0....2.$ $..0..2..$ $...02...$ $...20...$ $..2..0..$ $.2....0.$ $2......0$ Then we add color $3$ on the diagonal $x+y=7$ and complete it with $2$ cells to produce a $n$-free set. $0....3.2$ $.0..3.2.$ $..03.2..$ $..302...$ $.3.20...$ $3.2..0..$ $.2....03$ $2.....30$ Finally, we add color $4$ on the diagonal $x+y=11$ (actually, it doen't matter anymore, since we already have enough pairs) $04...3.2$ $40..3.2.$ $..03.2.4$ $..302.4.$ $.3.204..$ $3.2.40..$ $.2.4..03$ $2.4...30$ The rest we complete with $1$. $04111312$ $40113121$ $11031214$ $11302141$ $13120411$ $31214011$ $12141103$ $21411130$ Finally, to add colors $5$,$6$,$7$,$8$ we change monochromatic pairs symmetric with respect to main diagonal. $04111312$ $40113171$ $11081614$ $11805141$ $13150411$ $31614011$ $17141103$ $21411130$ We are done. Does this proof work when n and k are very close? For example if (n, k) = (8,6) you would just run out of diagonals.

Solution from Twitch Solves ISL: Rephrasing: Quote: Given the graph $G = K_n$, we wish to color its edges with two of $n$ colors (possibly the same color) such that every color is used, and every vertex $v$ has exactly $k$ colors used at it. The answer is that: when $k=2$, only $n \in \{2,3\}$ are possible. when $k=3$, any $n \ge k$ is permissible. Let's prove this. In what follows, $S(v)$ will denote the set of colors at a vertex $v$. For $k=2$, the construction of $n=2$ and $n=3$ are routine: For $n = k = 2$, let $V(G) = \{v_1,v_2\}$. Then set $S(v_1) = S(v_2) = \{A,B\}$ and paint the edge with $AB$. For $n = 3$ and $k = 2$, let $V(G) = \{v_1,v_2,v_3\}$. Then set $S(v_1) = \{A,B\}$, $S(v_2) = \{B,C\}$, $S(v_3) = \{C,A\}$ and color $v_1v_2$ with $BB$, $v_2v_3$ with $CC$, $v_3v_1$ with $AA$. Claim: For $k=2$, we have $n \le 3$. Proof. Assume $n > 3$. Each $S(v)$ is a two-element set. So we get a natural graph $\Gamma$ on the set of colors where the edges join two colors if they appear as some $S(v)$. This graph $\Gamma$ has the property any two edges intersect. This means it is either a $3$-cycle (hence $n=3$) or $K_{1,n-1}$. For $n > 3$, the latter case cannot work, since every color must appear in at least two $S(v)$'s. $\blacksquare$ Claim: For $k \ge 3$ there is a construction for all $n \ge 3$. Proof. If $n=k=3$ let $V(G) = \{v_1,v_2,v_3\}$. Then set $S(v_1) = S(v_2) = S(v_3) = \{A,B,C\}$ and color $v_1v_2$ with $AB$, $v_2v_3$ with $BC$, $v_3v_1$ with $CA$. Now suppose $n \ge 4$. Let $V(G) = \{v_1, v_2, \dots, v_n\}$ and let the $n$ colors be $C_1$, $C_2$, \dots, $C_{n-1}$, $C_{\text{special}}$ (breaking symmetry). We will create a construction with \begin{align*} S(v_1) &= \left\{ C_{\text{special}}, C_1, C_2 \right\} \\ S(v_2) &= \left\{ C_{\text{special}}, C_2, C_3 \right\} \\ &\vdotswithin{=} \\ S(v_{n-2}) &= \left\{ C_{\text{special}}, C_{n-2}, C_{n-1} \right\} \\ S(v_{n-1}) &= \left\{ C_{\text{special}}, C_{n-1}, C_1 \right\} \\ S(v_n) &= S(v_1) = \left\{ C_{\text{special}}, C_1, C_2 \right\}. \end{align*}Assign colors to the following edges: Assign $v_1v_2$ colors $C_{\text{special}} C_2$. Assign $v_2v_3$ colors $C_{\text{special}} C_3$. \dots Assign $v_{n-2}v_{n-1}$ colors $C_{\text{special}} C_{n-1}$. Assign $v_{n-1}v_{n}$ colors $C_{\text{special}} C_{1}$. Assign $v_{n}v_{1}$ colors $C_1 C_2$. Then assign $C_{\text{special}} C_{\text{special}}$ to all other edges. $\blacksquare$ Claim: Given a construction for $(n,k)$ we can get a construction for $(n+1, k+1)$. Proof. We do the following procedure. Create a new color $C_{\text{new}}$ and add it to every $S(v)$. Add a new vertex $v_{\text{new}}$. Let $C_1$, \dots, $C_k$ be any old colors and let $v_1$, \dots, $v_k$ be vertices with $C_i \in S(v_i)$. Set $S(v_{\text{new}}) = \{C_{\text{new}}, C_1, C_2, \dots, C_k\}$ The edges $v_{\text{new}}v_i$ are colored $C_iC_{\text{new}}$. Any other edges are colored $C_{\text{new}} C_{\text{new}}$. This completes the construction. $\blacksquare$ Remark: I have to say I found most of the conditions in the problem rather unnatural to work with. For example, there is no real reason why the number of colors should be equal to the number of circles, and in fact the construction has to ``work around this'' by breaking the symmetry somewhat in the first main claim.

We claim that the answers are $k=2, n=2, 3$, and $3\le k\le n$ for any $n\ge 3$. The cases $k=2, n=2,3$ are trivial to check. It is obvious that $k\le n$. First, we prove that when $n>3$, $k\le 2$ is impossible. Let the exposability of a color denote how many circles contain at least one of that color. Since each color appears at least once, the exposability of every color is at least $2$, and therefore the minimum possible overall exposibility is $2n$. For a particular $k$ to be possible, the overall exposability must be $nk$. Thus $k=1$ is impossible. $k=2$ is only possible if the exposability of every color is $2$. This would mean that each color could only appear at most twice (the two intersections of any two circles). This implies $$2n\ge 2\binom{n}{2}\Rightarrow n\ge \binom{n}{2}=\frac{n(n-1)}{2}\Rightarrow n\le 3,$$and thus $k=1,2$ is impossible for $n>3$. Next, we will prove that when $n\ge 3$, any $k$ satisfying $3\le k\le n$ works. Number the circles from $1$ to $n$ in the colors from $1$ to $n$. Claim: When $n\ge 3$, $k=3$ always works. Proof. Take color and circle numbers modulo $n$. This is trivial when $n=3$. When $n\ge 3$, the following construction works: 1. For $1\le i\le n$, color one intersection from circle $i$ to circle $i+1$ with color $i$. 2. Color one intersection between circles $2$ and $n$ with color $n$. 3. Color one intersection from circle $1$ to circle $3$ with color $3$. 4. Color all other intersections with color $1$. This ensures every circle has $3$ colors as 1. If $3\le i\le n$, the circle $i$ has colors $i-1, i, 1$. 2. Circle $1$ has colors $1,3,n$. 3. Circle $2$ has colors $1,2, n$. $\blacksquare$ Claim: If a particular pair $(k,n)$ (with $n\ge 3$) work with the configuration having the property that circle $i$ contains color $i$ for all $1\le i\le n$ ,then the pair $(k+1, n+1)$ works. Proof. Use the configuration given for $(k,n)$, and add another circle $n+1$. Then use this procedure to color in the intersections with this new circle: 1. For circle $n+1$ and circle $i$, for $1\le i\le k$, make one intersection color $n+1$ and one intersection $i$. 2. For circle $n+1$ and a circle numbered greater than $k$, make both intersections color $n+1$. All circles $1$ through $n$ now intersect exactly one new color $n+1$, and circle $n+1$ has color $n+1$ in addition to colors $1$ through $k$, so this works. $\blacksquare$ Now given an $(n,k)$ with $n\ge 3$ and $3\le k\le n$, by using the above claim repeatedly we conclude that it is sufficient to showing the pair $(n-k+3, 3)$ works, which is true by the first claim.

Answer: For $n=2$ the only such $k$ is 2; for $n=3$, $k=2, 3$ works; for $n\geq 4$ there is a construction for any $3\leq k\leq n$. The small cases $n=2, 3$ can be verified by hand and I won't do that here. Assume henceforth $n\geq 4$. Proof of impossibility of $k=1, 2$. If $k=1$ all intersections must be of the same colour, which by assumption is not true. Now, arguing indirectly, assume we have a construction for $k=2$. Construct a graph $G$ with vertex set the $n$ colours, and edges representing the circles, which we can do since any circle contains exactly two colours. It is given that i) there are $n$ edges and any two edges share a vertex and ii) every vertex is the endpoint of some edge. This is impossible for $n\geq 4$ because 1) By i) the graph is not a tree so it contains a cycle, 2) If the cycle has four or more edges we contradict ii), so the graph contains a triangle, 3) Every edge is adjacent to at least one vertex of this triangle. If we have an edge that is only adjacent to one of them, then it shares no endpoint with the opposite edge in the triangle, contradicting ii) again. Hence $n\leq 3$. $\square$ Construction for $n\geq k\geq 3$. Let the colours be $x_1, \dots, x_n$, and the circles $c_1, \dots, c_n$. Set $c_n$ aside and consider the other $n-1$ circles with indexes modulo $n-1$. Now, colour the two element set $c_i\cap c_j$ as follows: 1. For $1\leq i\leq k-1$ let $c_n\cap c_i\{x_i, x_n\}$, and for $i\geq k$ let $c_n\cap c_i=\{x_n, x_n\}$ 2. If $n\not\in \{i, j\}$, then $c_i\cap c_j=\{x_j, x_n\}$ if $i<j\leq i+k-2$ (if we cross $c_n$ between $c_i, c_j$ we add $n-1$ to the indexes when studying the inequality), and $c_i\cap c_j=\{x_n, x_n\}$ if $j$ does not lie in this interval. Circle $c_n$ contains the colours $c_1, \dots, c_{k-1}, c_n$, and for $i\neq n$ circle $c_i$ contains the colours $c_i, c_{i+1}, \dots, c_{i+k-2}$ (indexes modulo $n-1$) and $c_n$; in both cases, the circles contain exactly $k$ colours, and each colour is used at least once, so this works. $\square$.

Clearly $k=1$ fails. The $k=2$ case is easy; each color contributes to at least two circles with equality when the color appears at most twice. Hence $n(n-1)\le 2n$ and so $n\le 3$. This yields $(2,2)$ and $(3,2)$ as solutions. If $k\ge 3$ then I claim that $n\ge k$ always works. Take the natural graph interpretation; we have a $K_n$ and assign to each edge two (not necessarily) distinct colors labeled from $1$ to $n$, and we want $k$ distinct colors at each node. First we give a construction for $k=n$, then show that it extends to all $k\ge 3$. In the graph interpretation, arrange the vertices in a regular polygon. Out of each vertex there are $n-3$ diagonals. For each vertex, and for every diagonal, assign $\{1,\dots,n-3\}$ in an arbitrary order. Thus every color in that set appears in every vertex. Take a path of length $n-1$ along the edges of the polygon. To each of the edges in the path assign $\{n-2\}$. Take the single edge not hit by the path and label with $\{n-1,n\}$. Now alternate around the polygon with $n-1$ and $n$ to finish. Notice in the above example the colors $\{1,\dots,n-2\}$ fall into category 1 which follows the below principle: Try to assign these colors to create "spanning trees" of sorts; that is, each of these colors appears at each vertex. Then the colors $\{n-1,n\}$ fall into category 2 which follows the below principle: Try to assign these colors along the edges of the polygon in a singular cycle, ensuring that we (1) use all remaining colors and (2) each vertex gets two more distinct colors. For lower $3\le k<n$, we use a subset of the $k=n$ case: take the spanning trees of only $\{1,\dots,k-2\}$. Now, color along the edge of the polygon using the colors $\{k-1,\dots,n\}$ alternately. As there are at least three colors available, we can guarantee the cycle can be colored so adjacent edges are assigned different colors. To finish off, color anything which has not been touched with color $1$. $\blacksquare$

also I motivated the creation of spanning trees because symmetry fails with small $k$. you can prove this with global i think it gives something along the lines of $k\ge O(\sqrt{n})$ but I don't remember

The answer is $k=2,2\le n\le 3$ or $n\ge k\ge 3$. First, to show that this is necessary we see that $n\ge k$ is obviously necessary from the fact that there are $k$ distinct colors on each circle and $n$ colors total. If $k=1$ then necessarily $n=1$ which is a contradiction. If $k=2$ then we can double count with the number of pairs $(C,c)$ of circles and colors such that this circle $C$ has color $c$ on it. For each circle there are $k$ colors so the number of pairs is $2n$. On the other hand, for each color it appears at least on two circles, so in order for $k=2$ to work, each color appears exactly on two circles. Therefore, this color appears at most two times out of $n(n-1)$ possible places. Therefore, $2n\ge n(n-1)$ which implies $n\le 3$. Now, we prove that all claimed cases work. If $k=2,n=2$ color the two intersection points two different colors. If $k=2,n=3$ color the two intersection points between the same pair of circles the same color. Since there are three pairs of circles there can be three colors. Denote the circles $C_1,C_2,\dots,C_n$ and the colors $c_1,c_2,\dots,c_n$. If $k=3$ and $n=3$ then let $C_i$ and $C_j$ intersect at colors $i$ and $j$. Now let $k=3$ and $n=4$. Consider the circles $C_i$ and $C_{i+1}$ for $i=1,2,\dots,n-1$. Let one of their intersection points always be colored $c_i$. Let the other be colored $c_i$, except $i=1$ and $i=n$, when it is colored $c_2$ and $c_{n-2}$ instead, respectively. Color all other intersection points $c_n$. Then, $C_1$ will have $c_1,c_2,c_n$, $C_n$ will have $c_{n-2},c_{n-1},c_n$, and $C_i$ will have $c_{i-1},c_i,c_n$ for all other $i$. Suppose it is possible to color $n-1$ circles with each circle having $k-1$ distinct colors then if we add a circle $C_n$ color half of all points on $C_n$ with $c_n$ then we add exactly one distinct color to every circle. We can also use one color that is already used in each circle $C_1,C_2,\dots,C_{n-1}$ as the other intersection point to get $k$ distinct colors on $C_n$.