## Section46.3Ramsey Property

Let $k,r \geq 1$ be given. Then there is an $n_0(k,r)$ such that if $n\geq n_0(k,r)$ and $\{1,\ldots,n\}$ is $k$–coloured, then we can find natural numbers $a,d_1,\dots,d_r$ such that all sums

\begin{equation*} a+d_{i_1}+\cdots+d_{i_v} \hspace{0.5cm} (1\leq i_1\lt \ldots\lt i_v\leq r, ~0\leq v\leq r) \end{equation*}

have the same coluor (and, of course, $a+d_1+\cdots+d_r\leq n$).

Solution

Proof by induction. The base case is $n_0(k, 1)=k+1\text{.}$ Next, suppose that $r\geq 2$ is such that $n_0(k, r-1)$ exists. We prove that that we can take

\begin{equation*} n_0(k, r)=k^{n_0(k, r-1)}+n_0(k, r-1) . \end{equation*}

Suppose that $n \geq n_0(k, r)\text{.}$ Let $c$ be a $k$–colouring of the set $\{1, \ldots, n\}\text{.}$ For each $1 \leq p \leq k^{n_0(k, r-1)}+1\text{,}$ let $c_p$ be the $k$-colouring of the set $\{0,1,\ldots, n_0(k, r-1)-1\}$ defined by, for $j\in \{0,1,\ldots, n_0(k, r-1)-1\}\text{,}$ $c_p(j)=c(p+j)\text{.}$

Since there are $k^{n_0(k, r-1)}$ different $k$–colourings of the set $\{0,1,\ldots, n_0(k, r-1)-1\}\text{,}$ by the Pigeonhole Principle there are $1\leq p_1\lt p_2\leq k^{n_0(k, r-1)}+1$ such that, for each $0 \leq j \leq n_0(k, r-1)-1\text{,}$ $c(p_1+j)=c_{p_1}(j)=c_{p_2}(j)=c(p_2+j)\text{.}$

By induction, there is a natural number $a\text{,}$ $p_1 \leq a \leq p_1+n_0(k, r-1)-1\text{,}$ and integers $d_1, \ldots, d_{r-1}$ such that the set $\{a+d_{i_1}+\ldots+d_{i_\nu}: 1 \leq i_1\lt \ldots\lt i_\nu \leq r-1\}$ is $c$–monochromatic. Set $d_r=p_2-p_1\text{,}$ then, by the choice of $p_1$ and $p_j\text{,}$ the set

\begin{equation*} \{a+d_{i_1}+\ldots+d_{i_\nu}: 1 \leq i_1\lt \ldots\lt i_\nu \leq r\} \end{equation*}

is $c$–monochromatic, which completes the induction step.

Let us $k$–color all non–empty subsets of an $n$–element set. Prove that if $n$ is large enough, there are two disjoint non–empty subsets $X$ and $Y$ such that $X,Y\text{,}$ and $X \cup Y$ have the same colour.

Solution

Let $n=R(k;3,3)$ be the Ramsey number, i.e., the smallest positive integer that guaranties that any edge $k$–colouring of the complete graph with the vertex set $\{1,2,\ldots,n\}$ yields a monochromatic triangle.

Let $c$ be a $k$–colouring of the set of all non–empty subsets of the set $\{1,2,\ldots,n\}\text{.}$ Let $c^\prime$ be an edge $k$–colouring of the complete graph with the vertex set $\{1,2,\ldots,n\}$ defined by, for $1\leq i\lt j\leq n\text{,}$ $c^\prime(\{i,j\}=c(\{i,\ldots,j-1\})\text{.}$

Let $p,q,r\in \{1,2,\ldots,n$ be such that $p\lt q\lt r$ and $c^\prime(\{p,q\})=c^\prime(\{p,r\})=c^\prime(\{q,r\})\text{.}$

It follows that for $X=\{p,\ldots, q-1\}\text{,}$ $Y=\{q,\ldots, r-1\}\text{,}$ and $X\cup Y=\{p,\ldots, q,\ldots, r-1\}\text{,}$

\begin{equation*} c(X)=c(Y)=c(X\cup Y). \end{equation*}

Suppose that the set of all subsets of an $n$–element set $S$ is $k$–coloured, where $n \geq N(k,t)\text{.}$ Find disjoint sets $A_{1},B_{1},\ldots,A_{t},B_{t}$ such that for any fixed sequence $1 \leq i_{1} \lt\ldots \lt i_{v} \leq t\text{,}$ all unions of the form

\begin{equation*} C_{i_{1}} \cup \dots \cup C_{i_{v}}\text{, with }C_{i} = A_{i}\text{ or }\text{ or }B_{i} \text{ o r}A_{i} \cup B_{i} \end{equation*}

have the same colour.

Solution

By Problem 46.3.2, the number $n \geq N(k,1)$ exists for all $k\in \mathbb{N}\text{,}$ which establishes the base case of induction.

Let $t\geq 1$ be such that the number $N(k,t)$ exists for all $k\in \mathbb{N}\text{.}$

Let $a=N(k^2,t)$ and $N=N(k^{2^a},1)+a\text{.}$ Let $c$ be a $k$–colouring of the set of all subsets of $N$–element set $S\text{.}$

Let $T\subset S$ be such that $|T|=a\text{.}$ Let $\{T_1,T_2,\ldots,T_{2^a}\}$ be the set of all subset ot the set $T\text{.}$ We define $c^\prime\text{,}$ a $k^{2^a}$– colouring of the set of all subsets $S\backslash T\text{,}$ by

\begin{equation*} c^\prime(X)=(c(X\cup T_1),c(X\cup T_2), \ldots,c(X\cup T_{2^a})\text{.} \end{equation*}

Since $|S\backslash T|=N-=N(k^{2^a},1)\text{,}$ by Problem 46.3.2, there exist two disjoint sets $A_1,B_1\subseteq S\backslash T$ such that $c^\prime(A_1)=c^\prime(B_1)=c^\prime(A_1\cup B_1)\text{,}$ and by definition of the colouring $c^\prime\text{,}$ we have

\begin{equation*} \alpha(A_1\cup X)=\alpha(B_1\cup X)=\alpha(A_1\cup B_1\cup X) \end{equation*}

for each $X\subseteq T\text{.}$

Next we define $c^{\prime\prime}\text{,}$ a $k^2$–colouring of the set of all subsets of $T\text{,}$ by

\begin{equation*} c^{\prime\prime}(Y)=(c(Y),c(Y\cup A_1)). \end{equation*}

By definition of $a\text{,}$ there are $2t$ disjoint sets $A_2,B_2,\dots,A_{t+1},B_{t+1}$ such that for each sequence $1\leq i_1\lt \cdots\lt i_{\nu}\text{,}$ $c^{\prime\prime}(C_{i_1}\cup \cdots \cup C_{i_\nu})$ is same for any choice of $C_j=A_j,B_j$ or $A_j\cup B_j\text{.}$

Thus, for $A_1,B_1,\dots,A_{t+1},B_{t+1}$ and any sequence $1\leq i_1\lt \cdots\lt i_{\nu}\text{,}$ $c(C_{i_1}\cup \cdots \cup C_{i_\nu})$ is same for any choice of $C_j=A_j,B_j$ or $A_j\cup B_j\text{.}$

Hence, we may take $N(k,t+1)=N\text{,}$ which completes the induction step.

Prove that for any given $k$ and $r$ there is an $n = n(k,r)$ with the following property: whenever the set of all subsets of an $n$–element set $S$ is $k$–coloured, then there exist non–empty disjoint subsets $X_{1},\ldots,X_{r} \subseteq S$ such that all non–empty unions of any of them have the same colour.

Solution

We induct on $r\text{.}$ The base case $r=2$ is established by Problem 46.3.3.

Let $r\geq 2$ be such that $t=n(k,r)$ exists for any $n\in \mathbb{N}\text{.}$ Let $N=N(k,n(k,r))=N(k,t)\text{,}$ where $N=N(k,t)$ is the number established in Problem 46.3.3.

Let $c$ be a $k$–colouring of the set of all subsets of a $N$– element set $S\text{.}$ By Problem 46.3.3, there exists disjoint sets $A_1,B_1,\ldots,A_t,B_t$ such that for each sequence $1\leq i_1\lt \cdots\lt i_v\leq t\text{,}$ all sets of the form $C_{i_1}\cup\cdots\cup C_{i_v}$ have the same colour, where $C_j=A_j,B_j \text{ or }A_j\cup B_j\text{.}$

Let a $k$–colouring $c^\prime$ of the set of the subsets of the set $\{1,\dots,t\}$ be defined by

\begin{equation*} c^\prime(\{i_1,\cdots,i_v\})=c(A_{i_1}\cup\cdots\cup A_{i_v}). \end{equation*}

By our choice of $t\text{,}$ there are disjoint subsets $I_1,\cdots,I_r\subseteq \{1,\cdots,t\}$ such that the colouring $c$ colours any non–empty union of them, say, red. Let

\begin{equation*} X_j=\bigcup_{i\in I_j}A_i\text{ and }Y_j=\bigcup_{i\in I_j}B_i\text{.} \end{equation*}

Then, $X_1,\cdots,X_r$ and $Y_1,\cdots,Y_r$ are disjoint sets, and any of their non–empty union is also coloured red.

Let $V,W\subseteq \{1,\cdots,r\}$ and let

\begin{equation*} I=\bigcup_{j\in V\cap W}I_j,I'=\bigcup_{j\in V\backslash W}I_j,I''=\bigcup_{j\in W\backslash V}I_j\text{.} \end{equation*}

It follows

\begin{equation*} c\left( \left(\bigcup_{j\in V}X_j\right) \cup \left(\bigcup_{j\in W}Y_j\right) \right) = c\left( \left\{\bigcup_{i\in I}\left(A_i\cup B_i\right)\right\} \cup \left\{\bigcup_{i\in I'}A_i\right\} \cup \left\{\bigcup_{i\in I''}B_i\right\} \right). \end{equation*}

By our choice of $A_i,B_i\text{,}$

\begin{equation*} c \left( \bigcup_{i\in I\cup I'\cup I''}A_i \right) = c^\primeleft( I\cup I'\cup I'' \right) \end{equation*}

is also coloured red.

Since the number of sets $X_1,\ldots,X_r$ and $Y_1,\cdots,Y_r$ is $2r\geq r+1\text{,}$ we can take $n(k,r+1)=N$, which completes the induction step.

Strengthen Problem 46.3.3 as follows: For any $k$ and $r$ there exists a natural number $n$ such that, if $\{1,\ldots,n\}$ is $k$–coloured, then there always exist natural numbers $d_{1},\ldots,d_{r}$ such that $d_{1}+\dots+d_{r}\leq n$ and all sums $d_{i_{1}}+\dots+d_{i_{v}} (1 \leq i_{1} \lt \dots \lt i_{v} \leq r, v \geq 1)$ have the same colour.

Solution

Let $n=n(k,r)\text{,}$ where $n(k,r)$ is a function established in Problem 46.3.4. Suppose that $c$ is a $k$–colouring of the set $\{1,\dots ,n\}\text{.}$ Let $c^\prime$ be a $k$–colouring of the set of all subsets subsets of $S=\{1,\dots,n\}\text{,}$ defined by

\begin{equation*} c^\prime(X) = c(|X|)\text{, for }X \subseteq S\text{.} \end{equation*}

By Problem 46.3.4, there are disjoint sets $X_1,\dots,X_r \in S$ such that the set $\{ X_{i_1}\cup\cdots\cup X_{i_\mu}:\emptyset\not= \{i_1\lt \ldots \lt i_\mu\}\subset \{1,\ldots,r\}\}$ is $c^\prime$–monochromatic. By definition of the colouring $c^\prime\text{,}$ numbers $d_{1}=|X_1|,\ldots,d_{r}=|X_r|$ are such that the set $\{ d_{i_1}+\cdots + d_{i_\mu}:\emptyset\not= \{i_1\lt \ldots \lt i_\mu\}\subset \{1,\ldots,r\}\}$ is $c$–monochromatic.

Let $P$ be any property of $k$–coloured finite sets of natural numbers (for example, a set has property $P$ if it is monochromatic and forms an arithmetic progression). Suppose that, $k$–colouring all natural numbers in any way, some finite subset will have property $P\text{.}$ Then there exists a natural number $N$ such that $k$–colouring the set $\{ 1,\dots,N \}$ arbitrarily, some subset of it will have property $P\text{.}$

Note: This statement is a very special case of a general principle called compactness.

Solution

Suppose that such $N$ does not exist, i.e., suppose that for every $N\in \mathbb{N}$ there is a $k$–colouring $c_N$ of $\{1,\dots,N\}$ for which no subset has property $P\text{.}$ For each $\ell \in \mathbb{N}$ consider the colours $c_N(\ell)\text{,}$ for all $N\geq \ell\text{.}$ Since we use $k\text{,}$ a finite number of colours, there will be a sequence of natural numbers $S_1=\{N_i^{(1)}\}_{i\in \mathbf{N}}$ such that

\begin{equation*} c_{N_1^{(1)}} (1) =c_{N_2^{(1)}} (1) = \dots \end{equation*}

Denote this common colour by $c(1)\text{.}$

Now consider the colours $\alpha _{N_i^1}(2)\text{,}$ $i\in \mathbb{N}\text{.}$ There is a sequence of natural numbers $S_2=\{N_i^{(2)}\}_{i\in \mathbf{N}}\text{,}$ a subsequence of the sequence $S_1\text{,}$ such that

\begin{equation*} c_{N_1^{(2)}} (2) =c_{N_2^{(2)}} (2) = \dots \end{equation*}

Denote this common colour by $c(2)\text{.}$

In general, if the sequence $S_n=\{N_i^{(n)}\}_{i\in \mathbf{N}}\text{,}$ a subsequence of each of $S_\ell\text{,}$ $1\leq \ell\leq n-1\text{,}$ then $S_{n+1}=\{N_i^{(n+1)}\}_{i\in \mathbf{N}}$ a subsequence of the sequence $S_n\text{,}$ is such that

\begin{equation*} c_{N_1^{(n+1)}} (n+1) =c_{N_2^{(n+1)}} (n+1) = \dots \end{equation*}

We denote this common colour by $c(n+1)\text{.}$

By continuing this process, we define $c\text{,}$ a $k$–colouring of the set of natural numbers. Observe that for each $m\in \mathbb{N}$ and each $\ell\in \{1,\ldots, m\}\text{,}$ by the fact that each sequence is a subsequence of the sequence obtained in the previous step, we have $c(\ell)=c_{N_1^{(m)}} (\ell)\text{.}$

We claim that the colouring $c$ is such that no finite subset has the property $P\text{.}$

Assume that this is not true, i.e., assume that a finite set $T$ has the property $P\text{.}$ Let the natural number $m\in\mathbb{N}$ be such that $S \subseteq \{1,\ldots, m\}\text{.}$ Then, for any $\ell\in T\text{,}$

\begin{equation*} c_{N_1^{(m)}} (\ell) = c(\ell)\text{,} \end{equation*}

which implies that $T$ has property $P$ in the colouring $c_{N_1^{(m)}}$ too. This contradicts our choice of the colouring $c_{N_1^{(m)}}\text{.}$ Hence the colouring $c$ is such that there is no finite subset with the propert $P\text{,}$ which contradicts the assumption about the property $P\text{,}$ which completes the proof of the claim.

Decide whether the following assertion is true: If the set of all natural numbers is $k$–coloured, one of the classes contains $x, y, z$ with

1. $x + y = 3z\text{,}$

2. $x + 2y = z\text{.}$

Solution

1. We represent each natural number $m$ in base $5\text{,}$ i.e., we write $m = 5^{A_m} (5{B_m} + Y_m)\text{,}$ $1 \leq Y_m \leq 4\text{.}$ Let $c\text{,}$ a $4$–colouring of the set of natural numbers be defined by $c(m)=Y_m\text{.}$

Suppose that there is a $c$–monochromatic solution of the equation, i.e., suppose that for for some $Y\in\{1,2,3,4\}\text{,}$ there are $A_x,B_x,A_y,B_y,A_z,B_z$ such that

\begin{equation*} 5^{A_x}(5B_x + Y) + 5^{A_y}(5B_y + Y) = 3* 5^{A_z}(5B_z + Y)\text{.} \end{equation*}

We divide the equality above by $5^A\text{,}$ where $A = \min\{A_x, A_y, A_z\}\text{,}$ and consider the identity modulo $5\text{.}$ It follows, for some $E_x,E_y,E_z\in \{0,1,2,3,4\}\text{,}$

\begin{equation*} E_xY + E_yY = 3E_zY \pmod{5}, \end{equation*}
.

Notice that $E_x = 1\text{,}$ if $A = A_x\text{,}$ or $E_x = 0\text{,}$ if $A \lt A_x\text{.}$ The same is true for $E_y$ and $E_z\text{.}$ By dividing the identity by $Y\text{,}$ we obtain

\begin{equation*} E_x + E_y = 3E_z \pmod{5}\text{,} \end{equation*}

which, since $E_x, E_y, E_z \in \{0,1\}$ implies $E_X = E_y = E_z = 0\text{,}$ and therefore $A \lt \min\{A_x,A_y,A_z\}\text{.}$ This contradicts the definition of $A$ and proves our claim tha the equation has no a $c$– monochromatic solution.

2. Let $k\in \mathbb{N}$ and let $c$ be a $k$–colouring of the natural numbers. We prove by induction on $k$ that $x+2y = z$ has a $c$–monochromatic solution.

For $k=1\text{,}$ this is obvious. Suppose that the claim holds for all $k - 1$–colourings of $\mathbf{N}\text{,}$ where $k\geq 2$ is a fixed integer.

It follows that there is a natural number $N$ with the property that if we $(k -1)$–colour the numbers $\{1,\ldots, N\}\text{,}$ then one of the colour classes will contain a solution of $x + 2y= z\text{.}$

By van der Warden's theorem, there is $c$–monochromatic (say red) arithmetic progression

\begin{equation*} \{a, a + d, a + 2d,\ldots, a + 2Nd\}\text{.} \end{equation*}

If there is $p\in \{1,\ldots,N\}$ such that $pd$ is red then for $x = a\text{,}$ $y = pd\text{,}$ $z = a + 2pd$ we have $x+2y=z$ and $c(x)=c(y)=c(z)=\text{ red}\text{,}$ i,.e, we have a $c$–monochromatic solution of the equation.

If there is no a red $pd\text{,}$ we define $c^\prime\text{,}$ a $(k -1)$–colouring of the set $\{1,\ldots,N\}\text{,}$ by $c^\prime(p)=c(pd)\text{.}$

By the definition of $N$ there is a $c^\prime$– monochromatic solution of the equation $x_1, y_1, z_1\text{,}$ i.e., $x_1 + 2y_1 = z_1$ and $c^\prime(x_1)=c^\prime(y_1)=c^\prime(z_1)\text{.}$ But this implies that $(dx_1) + 2(dy_1) = (dz_1)$ and $c(dx_1)=c(dy_1)=c(dz_1)\text{,}$ i.e., $x=dx_1,y=y_1, z=dz_1$ is a $c$–monochromatic solution of the equation.

By the Principle of Mathematical Induction, the claim is true.

Prove that there exists a function $f(k)$ with the property that, if $S$ is any set of integers with $|S| \geq f(k)\text{,}$ then the set of all integers can be $k$–coloured so that $S+j= \{s+j : s \in S\}$ meets all the colours for every integer $j\text{.}$ The $k$–colouring can even be required to be periodic.

###### Remark46.3.9.

The solution uses the following fact established in Problem 2.18 in Lovas'z book “Combinatorial Problems and Exercises:”

Let $G$ be a simple graph on $V(G)=\{1,\ldots,n\}$ with all degrees at most $d$ and $A_i$ be associated with each point $i\text{.}$ Suppose that

1. $\mathbf{P}(A_i)\leq \frac{1}{4d}\text{,}$ and

2. every $A_i$ is independent of the set of all $A_j$'s for which $j$ is not adjacent to $i\text{.}$

Then $\mathbf{P}(\overline{A}_1\cdots\overline{A}_n)>0\text{.}$

Solution

Supposed that a function $f(k)$ with the required property exists and that a set $S$ is such that $|S|\gt f(k)\text{.}$

We $k$–colour the set of integers randomly, i.e., integers are coloured independently of each other with the probability of giving an integer a particular colour $\frac{1}{k}\text{.}$ If $A_j$ is an event that $S+j$ does not meet one of the colours, then

\begin{equation*} \mathbf{P}(A_j)\leq \sum_{i=1}^{k}\mathbf{P}(S+j\text{ does not meet color }i)=k\left(1-\frac{1}{k}\right)^{f(k)}\text{.} \end{equation*}

We form a graph $G$ on the set of integers by connecting $j_1$ to $j_2$ such that $(S+j_1)\cap (S+j_2)\neq \emptyset\text{,}$ then $A_j$ is independent of $\{A_\ell:(j,\ell)\not\in E(G)\}\text{.}$ Observe that the degree of each vertex is \

\begin{equation*} d=|\{\ell:(0,\ell)\in E(G)\}|=|\{\ell:(S+\ell)\cap S\neq 0\}|=|\{s-s^\prime:s,s^\prime\in S\}|\leq {f(k)}^2\text{.} \end{equation*}

If $k(1-\frac{1}{k})^{f(k)}\leq \frac{1}{4f(k)^2}\text{,}$ we have $P(A_j)\leq \frac{1}{4d}\text{.}$ By Remark 46.3.9, $\mathbf{P}(\bar{A_0}\dots\bar{A}_N)\gt 0$ for any positive integer $N\text{.}$

Observe that we have established that for any positive integer $N$ and any $j\in\{0,\ldots, N\}\text{,}$ in a random $k$–colouring of integers, the set $S+j$ meets all colours.

Here is the construction of a $k$–colouring with the property that $\mathbf{P}(\sum_{-\infty}^{\infty}\bar{A_j})\gt 0\text{.}$

Let $r$ be the diameter of $S\text{,}$ with $r=\max(S)-\min(S)\text{.}$ Let $N\gt k^{r+1}$ be an even integer such that $S\subseteq \left\{-\frac{N}{2},-\frac{N}{2}+1,\ldots, \frac{N}{2}-1,\frac{N}{2}\right\}\text{.}$ Observe that each translate of $S$ contained in $\left\{\frac{N}{2}+1,\ldots,\frac{3N}{2}\right\}$ is of the form $j+S\text{,}$ for some $j\in \{r,\ldots,2N-r\}\text{.}$

Let $c$ be a $k$–colouring of integers for which $\bar{A_0}\cdots\bar{A}_{2N}\not=\emptyset$ holds.

Since $N\gt k^{r+1}\text{,}$ by the Pigeonhole Principle, the set $\left\{\frac{N}{2}+1,\ldots,\frac{3N}{2}\right\}$ contains two segments $\{u,u+1,\ldots,u+r\}$ and $\{v,v+1,\ldots,v+r\}\text{,}$ with $u\lt v\text{,}$ that are coloured identically, i.e., for all $\ell\in\{0,1\ldots,r\}\text{,}$ $c(u+\ell)=c(v+\ell)\text{.}$

We define a new $k$–colouring $c^\prime$ of integers in the following way:

• The colouring $c^\prime$ is periodic with a period $T=v-u\text{.}$

• For each $\ell \in \{u,u+1,\ldots,v-1\}\text{,}$ $c^\prime(\ell)=c(\ell)\text{.}$

• For an integer $n$ let $m$ be the unique integer such that $n+mT \in \{u,u+1,\ldots,v-1\}\text{.}$ Then, by definition, $c^\prime(n)=c(n+mT)\text{.}$

Observe that for each $\ell\in\{0,1\ldots,r\}\text{,}$ $u+\ell+T=v+\ell\text{.}$ Moreover, for any $n\in \{u, u+1,\ldots, v, v+r\}\text{,}$ $c^\prime(n)=c(n)\text{.}$ Finally, observe that for each $m\in \{u, u+1,\ldots, v-1\}$ and each $\ell\in\{0,1\ldots,r\}\text{,}$ $m+\ell \in \{u, u+1,\ldots, v, v+r\}\text{,}$ i.e., $c^\prime(m+\ell)=c(m+\ell)\text{.}$

Let $s_m=\min S$ and $s_M=\max S\text{.}$ For $j\in\mathbb{Z}\text{,}$ let $m\in \mathbb{Z}$ be such that $j+mT+s_m\in \{u,u+1,\ldots,v-1\}\text{.}$ But then $j+mT+s_M\lt v+r\text{,}$ which implies that $j+mT+S\subset m+\ell \in \{u, u+1,\ldots, v, v+r\}\text{.}$ Hence, for all $s\in S\text{,}$ $c^\prime(j+s)=c(j+mT+s)\text{.}$

Since there is $i\in \{1,\ldots,2N\}$ such that $i+S=j+mT+S\text{,}$ it follows that $c^\prime$ is a $k$–colouring such that $S+j= \{s+j : s \in S\}$ meets all the colours for every integer $j\text{.}$

It turns out that, for a large enough $c\text{,}$ $f(k)=\lfloor ck\log k\rfloor$ is the appropriate function. Indeed,

\begin{equation*} (1-\frac{1}{k})^{f(k)}\approx (1-\frac{1}{k})^{ck\log k}\lt e^{-c\log k}=\frac{1}{e^{c\log k}}=\frac{1}{k^c}\text{,} \end{equation*}

together with

\begin{equation*} \frac{1}{4f(k)^2}=\frac{1}{4c^2k^2\log^{2}k}\gt \frac{1}{k^{c-1}}\text{,} \end{equation*}

is all what is needed.