A nice and hard colouring problem

Solution 1:

Assume $2\leq A<B$. Then $B=qA+r$ with $q\geq1$, $\>1\leq r\leq A-1$, and $r$ prime to $A$.

Imagine an "abstract" regular $A$-gon with vertex set $V\sim{\mathbb Z}/A$. If we draw the $A$ chords $\{k,k+r\}$ we obtain a cyclic graph $\Gamma$. Omitting an edge from $\Gamma$ leaves a connected graph $\Gamma'$, but if we omit $\geq2$ edges from $\Gamma$ the resulting graph on $V$ is no longer connected.

The set $[n]:=\{1,2,\ldots, n\}$ splits into $A$ remainder classes modulo $A$. All members of the same class are colored with the same color; hence each class has its color. Some of these classes are related by a $B$-jump and therefore are assigned the same color. The possible $B$-jumps are $$1\to1+B, \quad 2\to 2+B, \quad \ldots, \quad n-B\to n\ .$$ The first $A$ of these jumps lead to different edges of $\Gamma$.

If $n-B\leq A-2$, or $n\leq A+B-2$, then not all classes modulo $A$ are connected by $B$-jumps, hence a nonconstant coloring of $[n]$ of the desired kind is possible. If, however, $n-B\geq A-1$, or $n\geq A+B-1$, then $\geq A-1$ different chords in $\Gamma$ are realized, which then implies that all remainder classes modulo $A$ will get the same color.

Solution 2:

Just some thoughts to address further answers.

Let we say that a colouring is maximal if $n$ is maximal. As stated in the question, in a maximal colouring $c$, $A$ and $B$ cannot have the same colour: otherwise we may define $c'$ on $\{1,\ldots,n+1\}$ such that $c'(1)=c(A)=c(B)$ and $c'(m)=c(m-1)$ for any $m\geq 1$, leading to a valid colouring and contradicting the maximality of $n$. So, up to switching colours, we may assume that any maximal colouring fulfills $c(A)=1$ and $c(B)=0$, so $n<A+B$ as already stated. We may also assume $A<B$ without loss of generality. $c(A)=1$ actually gives the whole colouring: $1=c(2A)=c(3A)=\ldots$ must hold, and by assuming $k=\left\lceil\frac{B}{A}\right\rceil$, $1=c(kA-B)$ must hold too, so $1=c((k+1)A-B)=c((k+2)A-B)=\ldots$. By assuming that $j$ is the least integer such that $(k+j)A-B>B$, i.e. $(k+j)A>2B$, we must have $c((k+j)A-2B)=1$ and so on. We may continue until there is an element in the interval $[1,A]$ that still has colour $0$. After that, the procedure gives colour $1$ to both $B$ and $B-A\in[1,A]$, leading to a constant colouring. So $n$ is given by the maximum length allowing us not to give colour $1$ to $B$ or $B-A$.

Here it is what happens with $A=11,B=16$: $$\begin{array}{l}A=11\mapsto 22 \\ 6\mapsto 17\\ 1\mapsto 12\mapsto 23\\ 7\mapsto 18\\ 2\mapsto 13\mapsto 24\\ 8\mapsto 19\\ 3\mapsto 14\mapsto 25\\ 9\mapsto 20\\ 4\mapsto 15\mapsto \color{red}{26}\\ \color{red}{10\mapsto 21}\\ \color{red}{5\mapsto 16=B}\end{array}$$ if we allow $26=A+B-1$ to have colour $1$, then any number in the interval $[1,A]$ has colour $1$, and $B$ has colour $1$ too. So we have that the maximal length for $A=11,B=16$ is $\color{red}{n=25}$, and the following is a maximal colouring: $$ c^{-1}(1) = \{1,2,3,4,6,7,8,9,11,12,13,14,15,17,18,19,20,22,23,24,25\}, $$ $$ c^{-1}(0) = \{5,10,16,21\}. $$