Solution. Those pairs are all pairs $(c, d)$ of positive integers greater than 1 such that $d \leq c$.

Assume first that $d \geq c+1$. Choose a large prime $p$ (we need $p>2 c^{2}+c$ ) congruent to 1 modulo $d$ (such a prime exists, by a particular case of Dirichlet's theorem; this particular case is easier to prove by using the cyclotomic polynomial $\left.\Phi_{d}\right)$. Let $Q(X)=X^{d}$. Since $d \mid p-1$, exactly $1+(p-1) / d$ residues modulo $p$ are $d$-th powers; all other $(d-1)(p-1) / d$ residue classes contain no values of $P$. Hence, if a set $S$ satisfies the requirements, it should contain representatives of all those classes. But this is more than $S$ is allowed to contain, since

$$\begin{aligned} \frac{d-1}{d}(p-1)>\frac{2 c-1}{2 c+1} p & \Longleftarrow \frac{c}{c+1}(p-1)>\frac{2 c-1}{2 c+1} p \\ & \Longleftarrow \frac{p}{(c+1)(2 c+1)}>\frac{c}{c+1} \Longleftarrow p>c(2 c+1) . \end{aligned}$$

We now show that such set $S$ exists, whenever $d \leq c$. To this end, usage is made of the lemma below.

Lemma. Fix an integer $d \geq 2$. Let $G=(V, E)$ be a directed graph, each vertex of which has exactly one outgoing edge and at most $d$ incoming edges. Assume further that there are at most $d$ loops in this graph. Then there exists a subset $V^{\prime}$ of $V$ of cardinality $\left|V^{\prime}\right| \leq 1+\frac{d-1}{d}|V|$ such that every vertex in $V \backslash V^{\prime}$ is the terminus of a directed path emanating from $V^{\prime}$.

Proof. Consider any (weak) connected component $G_{1}=\left(V_{1}, E_{1}\right)$ in $G$ - i.e., a component of the corresponding undirected graph. Since from each vertex emanates exactly one edge, the component contains a directed cycle (possibly a loop); and since the numbers of vertices and edges in $G_{1}$ are equal, even an undirected cycle is unique. Hence, the component is a cycle with some trees rooting out of its vertices. With reference again to uniqueness of outgoing edges, the edges of these trees are all directed towards the cycle.

!

Now, let $V^{\prime}$ choose exactly one vertex from each component that is just a cycle; for any other component, let $V^{\prime}$ choose all its in-degree 0 vertices, i.e., the leaves of all trees rooting out of the vertices of the core-cycle - any vertex of such a tree can be reached from some leaf, and hence so can any vertex of the core-cycle.

To bound $\left|V^{\prime}\right|$ from above, let $t$ be the number of single-vertex components in $G$, and notice that $t \leq d$, since there are at most $d$ loops in the graph. From each other component that is a cycle, $V^{\prime}$ chooses at most half of its vertices, so at most $\frac{d-1}{d}$-th part of them. Finally, consider a component containing some trees. Since each in-degree is at most $d$, at least $\frac{1}{d}$-th part of the vertices have incoming edges, hence $V^{\prime}$ chooses at most $\frac{d-1}{d}$-th part of the vertices. Consequently,

$$\left|V^{\prime}\right| \leq t+\frac{d-1}{d}(|V|-t)=\frac{t}{d}+\frac{d-1}{d}|V| \leq 1+\frac{d-1}{d}|V|$$

as desired. This establishes the lemma.

Now let $p$ and $Q$ be chosen as in the problem statement. Consider a graph with vertex set $\mathbb{Z}_{p}$. Regard $Q$ as a polynomial over $\mathbb{Z}_{p}$, and draw an edge $a \rightarrow Q(a)$ for every $a$ in $\mathbb{Z}_{p}$. Since $\operatorname{deg} Q=d$, each $b$ in $\mathbb{Z}_{p}$ has at most $d$ preimages, so the in-degree of each vertex is at most $d$. Since $Q$ is monic and $d>1$, the equation $Q(x)=x$ has at most $d$ roots in $\mathbb{Z}_{p}$, hence the graph has at most $d$ loops. Thus, implementation of the lemma provides a set $V^{\prime}$ which is suitable as the required set $S$. Indeed, the lemma statement shows that each residue is a repetitive image of some element of $S$; and the implications below show that the cardinality of $V^{\prime}$ lies within the required range:

$$\begin{aligned} \left|V^{\prime}\right| \leq \frac{d-1}{d} p+1 \leq \frac{2 c-1}{2 c+1} p & \Longleftarrow \frac{c-1}{c} p+1 \leq \frac{2 c-1}{2 c+1} p \\ & \Longleftarrow \frac{p}{c(2 c+1)} \geq 1 \Longleftarrow p \geq c(2 c+1) \end{aligned}$$