Though this problem is in the Lovász Local Lemma chapter, this particular result doesn't use it; it's meant to be an asymptotically tight lower bound to the result proven in Theorem 5.2.2, which does crucially use it. The proof is a bit of a handful, so do let me know if something seems wrong/isn't clear!
To get the result, for now, let $c$ be undetermined, and randomly select a subset $S$ by independently including each element in $[2ck \ln k]$ with probability $1/2$ (this is slightly different than the hint, but avoids the slight negative dependencies between which elements are included in $S$). Now fix any subset $U$ of size at most $4c\ln k$. We will first show that with extremely high probability, $U$ does not intersect every translate of $S$. For any translate $x+S$, where $x$ is an arbitrary element of $[2ck\ln k]$, it is easy to see that
$$
\Pr(U\cap x+S= \emptyset)\geq \bigg(\frac{1}{2}\bigg)^{4c\ln k}=\frac{1}{k^{4c\ln 2}}\geq \frac{1}{k^{2.8c}}.
$$
So the probability $U$ intersects an arbitrary translate is fairly close to $1$, but bounded away from $1$. To drive the probability it intersects all translates of $U$ down to $0$, notice that
$$
U\cap x+S\neq \emptyset \iff U-x\cap S\neq 0,
$$
and because of how $S$ was generated, if $x,x'$ are such that $U-x\cap U-x'=\emptyset$, then the events that $S\cap U-x=\emptyset$ and $S\cap U-x'=\emptyset$ are independent. Obviously, this will not hold for many pairs of $x,x'$, but we can find a fairly large family where these translates are mutually disjoint. Indeed, we claim there is such a family of such $x$ of size $\geq \frac{k}{8c\ln k}$. In fact, any maximal family of such $x$ will have at least this cardinality.
To get this, take any maximal family $X\subseteq [2ck\ln k]$ of such $x$ i.e. for all $x, x'\in X$ distinct,
$$
U-x\cap U-x'=\emptyset,
$$
and for any other $x''\in [2ck\ln k]\setminus X$, there exists some $x\in X$ such that
$$
U-x''\cap U-x\neq \emptyset.
$$
Suppose it has smaller size than what we claimed. By pairwise disjointness, we must have
$$
\vert \cup_{x\in X} U-x\vert=\vert U\vert\vert X\vert< k/2.
$$
Notice that every element in this union can belong to at most $\vert U\vert$ translates of $U$. It follows that $\cup_{x\in X} U-x$ can only intersect strictly less than $(k/2)\vert U\vert=2ck\ln k$ translates of $U$, giving a contradiction. We conclude that any maximal family $X\subseteq [2ck\ln k]$ such that the $U-x$ for $x\in X$ are all disjoint has size $\geq \frac{k}{8c\ln k}$.
For the fixed $U$, take such a maximal family $X$. Now, we can finally continue to say that
\begin{align}
\Pr(U\cap x+S\neq \emptyset, \forall x\in [2ck\ln k])&\leq \Pr(U\cap x+S\neq \emptyset, \forall x\in X)\\
&\leq \bigg(1-\frac{1}{k^{2.8c}}\bigg)^{k/8c\ln k}\\
&\leq \exp\bigg(\frac{-k^{1-2.8c}}{8c\ln k}\bigg),
\end{align}
where we use independence, the estimate above, and the usual $1-x\leq e^{-x}$ estimate.
To use a union bound for all subsets of $[4ck\ln k]$ of size at most $4c\ln k$, we estimate
$$
\sum_{i=0}^{4c\ln k} {4ck\ln k\choose i}\leq 2^{H(1/k)4ck\ln k},
$$
using a standard upper bound on partial sums of binomial coefficients, where $H(x)$ is the binary entropy function. Observe that
\begin{align}
2^{H(1/k)4ck\ln k}&=2^{((1/k)\log_2(k)-(1-1/k)\log_2(1-1/k))4ck\ln k}\\
&\leq 2^{(\log_2(k)+1)4c\ln k}\\
&\leq \exp\bigg(c'\ln^2 k\bigg),
\end{align}
where $c'$ is some other constant that is at most some absolute scalar multiple of $c$ after changing bases of logs. We also use the fact $-(k-1)\log_2(1-1/k)\leq 1$ for all $k\geq 2$. The union bound then gives
\begin{align}
\Pr\bigg(\exists U\subseteq [4ck\ln k]: \vert U\vert\leq 4c\ln k,\leq U\cap S+x\quad\forall x\in [2ck\ln k]\bigg)&\leq \exp\bigg(c'\ln^2 k\bigg)\exp\bigg(-k^{1-2.8c}/8c\ln k\bigg)\\
&<<1,
\end{align}
where we can make $c$ sufficiently small so that this holds for all $k$ with very high probability. The last thing to note is that by usual Chernoff bounds, with very high probability, $\vert S\vert\geq f(c)k\ln k$ for all $k$, where $f<1$ is just some function of $c$, so with high probability $S$ will be large and satisfy the event above. This shows the existence of a large subset $S$ such that for any $k$-coloring of the integers, some translate of $S$ will avoid the least represented color among the first $[4ck\ln k]$ integers.
To generalize the problem, consider an arithmetic progression in which the first term is a positive fraction, every alternate term is an integer, and the sum of the first $11$ terms is $S$.
If we take the convention that the general term of the progression is
$a_k = a + kd,$ where $a_0 = a$ is the first term in the progression,
then the conditions of the problem imply that $a_1$ and $a_3$ are integers.
Therefore $a_3 - a_1 = 2d$ is also an integer,
and therefore $d$ is a multiple of $\frac12.$
Depending on what we mean by "positive fraction,"
for a large enough $S$ the problem no longer has a unique solution.
If "positive fraction" merely means a positive number that is not an integer,
then if $S = 88$ then two possible solutions for the progression
$a_k = a+kd$ starting at $a_0 = a$ are
$$a = \frac12, \ d = \frac32;$$
$$a = \frac{11}2, \ d = \frac12.$$
In general (under this interpretation) we will always have $a_5 = \frac S{11},$ and the only requirement for a solution for a given $S$ is that
$\frac S{11} - 5d > 0$, which (given that $d$ is a multiple of $\frac12$)
implies that $\frac S{11} - 5d \geq \frac12$ or
$S - 55d \geq \frac{11}2$;
if we let $d = m + \frac12$ for integer $m \geq 0$
(that is, $d$ is a multiple of $\frac12$ but not an integer),
then $S - 55\left(m + \frac12\right) \geq \frac{11}2$,
which is equivalent to $S \geq 33 + 55m.$
Clearly there is no solution if $S < 33,$
and if $S < 88$ there can be only one solution (in which $d = \frac12$).
Note that since $a_5$ is an integer, since $a = a_0 = a_5 - 5d,$ and since $d$ is a multiple of $\frac12,$ it follows that $a$ also is a multiple of $\frac12.$
If "positive fraction" means a number strictly between $0$ and $1,$ then the only possible value of $a$ is $a = \frac12$ and there is at most one solution.
Note that under either of the interpretations given above,
if there is a solution at all, there is a solution in which $d = \frac12.$
Also, since $S = 11a_5,$ and $a_5$ is an integer, $S$ is a multiple of $11.$
And if $S \geq 33 + 55m$ for a non-negative integer $m,$
then there also are solutions in which $d$ can be any odd multiple of $\frac12$ from $\frac12$ itself up to $m + \frac12.$
That is, there are two solutions if $S = 88$ (shown above),
three solutions if $S = 143$, and so forth.
Best Answer
First of all, to get a result about colorings of $\mathbb Z$ using the probabilistic method, we need to get there in two steps. First, we prove that an arbitrarily large interval $[-M,M] \cap \mathbb Z$ can be colored. Second, we use a compactness argument to pass to $\mathbb Z$. Assuming that the course notes cover the second step, I'll focus on the first.
As our bad events for the local lemma, we take all individual arithmetic progressions (of length $n \ge N$ and common difference less than $1.99^n$) contained in this interval. If $A$ is a bad event corresponding to an arithmetic progression of length $n$, we'll take $x(A) = 1.995^{-n}$; note that $\Pr[A] = 2^{1-n}$, so this allows $x(A)$ to be exponentially larger than $\Pr[A]$.
An arithmetic progression of length $n$ intersects at most $nk \cdot 1.99^{k}$ arithmetic progressions of length $k$: we choose in $nk$ ways which terms of the two progressions overlap, and in $1.99^{k}$ ways the common difference of the other progression. So we have \begin{align} x(A) \prod_{B \in \Gamma(A)} (1 - x(B)) &\ge 1.995^{-n} \prod_{k=N}^\infty (1 - 1.995^{-k})^{nk \cdot 1.99^k} \\ &= \left(\frac1{1.995} \prod_{k=N}^\infty (1 - 1.995^{-k})^{k \cdot 1.99^k}\right)^n \\ &\ge \left(\frac1{1.995} \left(1 - \sum_{k=N}^\infty k \left(\frac{1.99}{1.995}\right)^k\right)\right)^{n}. \end{align} In the last step, we turn the product into a sum by repeated use of the inequality $(1-x)(1-y) \ge 1 - x - y$ when $x,y \ge 0$.
The sum as $k$ goes from $N$ to $\infty$ is convergent, so by choosing $N$ sufficiently large, we can make it as small as we like. Let's choose $N$ to be large enough that it is less than $0.001$ (we'll have another condition on $N$ later). Then $$ x(A) \prod_{B \in \Gamma(A)} (1 - x(B)) \ge \left(\frac1{1.995}(1 - 0.001)\right)^n = \left(\frac{999}{1995}\right)^n. $$ Our second condition on $N$ is that it must be large enough that $(\frac{999}{1995})^N \ge 2 \cdot (\frac12)^N$; then the same inequality holds for all $n \ge N$, and tells us that $$ x(A) \prod_{B \in \Gamma(A)} (1 - x(B)) \ge 2^{1-n} = \Pr[A]. $$ Now we know that the condition in the local lemma holds, so we can avoid all these arithmetic progressions.