I was pretty surprised this was problem 6, since I did not find the problem bad at all.

Same as above, but sunflowers (or sun graphs) are amazing so I'll post it here. In the following, garden = digraph and sunflower = connected component of the digraph.

Quote: Then as $p$ gets big, we must at least pick all of the nonzero residues modulo $p$ which are not $d$th powers, hence at least $(p-1) * \frac{d-1}{d} > \frac{2c-1}{2c+1} p$ for big enough $p.$ could you tell me why？ My brain was stuck，I spend a lot of time trying to understand it

Seswn wrote: Quote: Then as $p$ gets big, we must at least pick all of the nonzero residues modulo $p$ which are not $d$th powers, hence at least $(p-1) * \frac{d-1}{d} > \frac{2c-1}{2c+1} p$ for big enough $p.$ could you tell me why？ My brain was stuck，I spend a lot of time trying to understand it If $p \equiv 1 \pmod{d}$, $A=\{x^d| x$ is integer$\}$ has exactly $1+(p-1)/d$ residue in $Z_p$. So we shoult select at least $(p-1)\frac {d-1}{d}$ elements in $Z_p$.

Consider a pair $(c,d)$ of integers greater than $1$. Ana and Banana are playing the following game: Ana announces a degree $d$ monic polynomial $P$ with integral coeffcients and a prime $p > c(2c + 1)$. Banana then writes at most $p(2c - 1)/(2c + 1)$ integers on a board and is then allowed to perform a finite sequence of operations of the following kind: Choose an integer $x$ written on the board and write $P(x)$ on the board. She wins if she reaches a stage where the numbers form a complete residue system modulo $p$; otherwise Ana wins. Determine all pairs $(c, d)$ for which Banana can win regardless of how Ana plays. Adrian Beker, Croatia PS. This above is the problem's wording as 2019 RMM Shortlist N2

Similar to other solutions, but posting for storage. Very interesting graph theory problem !

This wasn't especially fun to write up . The answer is all $c\ge d$. First, take $Q(x)=x^d$ and $p\equiv1\pmod{d}$ to see that all non-powers of $d$ have to be covered with separate $s$, so $\frac{2c-1}{2c+1}> \frac{d-1}{d}\implies c\ge d$. Now, we prove all such $c$ work. Lemma: [Graph Theory] Let $G=(V,E)$ be a finite directed graph on $n$ vertices (possibly with self-loops) such that every outdegree is $1$. There exists a subset $S\subseteq V$ such that ``for every $w\not\in S$, there is a directed path starting in $S$ and ending at $w$'' which satisfies \[|S|\le\ell+\frac{\delta-1}{\delta}(n-\ell)\]where $\ell$ is the number of self-loops and no indegree of a vertex is greater than $\delta$ and $\delta\ge2$. Solution: First, throw out the self-loops and note it suffices to prove the result for no self-loops. Now, use the following stupid approach; first, for each vertex with $0$ indegree, delete it and all vertices that can be reached by a directed path from it. We claim that at least $\frac{1}{\delta}$ of the vertices deleted in this step are not vertices with $0$ indegree. This is immediate because no vertex has indegree greater than $\delta$, so if $k$ vertices with $0$ indegree are deleted in that step, then at least $\frac{k}{\delta}$ other vertices are deleted because every vertex with $0$ indegree has nonzero outdegree. Note that this deletion leaves a graph in which it suffices to show the lemma holds. Now, consider the remaining graph. No remaining vertex can have $0$ indegree, otherwise it would have been deleted. Hence, every vertex has nonzero indegree, and every vertex has outdegree at most $1$. Now, for each vertex $u$, let $V(u)$ denote the set of vertices that can be reached by a directed path from $u$, including $u$ itself. It is clear that for each vertex $u$, we can choose a vertex $v$ with a directed edge $v\to u$ to see that $V(u)\subseteq V(v)$. Say that a set $V(u)$ is \emph{maximal} when any such choice of $v$ yields $V(v)=V(u)$ and note that each maximal $V(u)$ is $V(v)$ for at least two $v$, and there are at most $|V|$ such maximal $V(u)$, so the set of all maximal $V(u)$ can be generated with at most $\frac{1}{2}|V|$ vertices, implying the claim because $\frac{1}{2}\le\frac{\delta-1}{\delta}$. $\fbox{}$ We take the obvious graph theoretic interpretation of $Q$. Now, we have $\delta=d$ and note $\ell\le d$ because $Q(x)-x$ has at most $d$ roots, so we can find a set $S$ with \[|S| \le d+\frac{d-1}{d}(p-d) = \frac{d-1}{d}p + 1\]satisfying the desired criteria. It remains to show that \[\frac{2d-1}{2d+1}p\ge \frac{d-1}{d}p+1,\]since $\frac{2c-1}{2c+1}$ is an increasing function as $c\to\infty$. Rearranging, we see it suffices to show \[\left(\frac{2d-1}{2d+1}-\frac{d-1}{d}\right)p = \frac{2d^2-d-(2d^2-d-1)}{d(2d+1)}p > \frac{1}{d(2d+1)}\cdot c(2c+1)\ge 1.\]

We claim that all pairs $(c,d)$ with $c \geq d >1$ work. To show that $c \geq d$, we pick a prime number $p$ large enough such that $d|p-1$ (it exists by Dirichlet's Theorem). Then, choose $Q(X)=X^d$. Notice that there exactly $\frac{p-1}{d}$ $d$-adic residues in $\mathbb{F}_{p} \implies Q(s)$ achieves at most $\frac{p-1}{d}$ values $\pmod{p}$. Thus, $p=|\bigcup_{s \in S} \{s,\; Q(s),\; Q(Q(s)),\; Q(Q(Q(s))),\; \dots\}| \leq |S|+\frac{p-1}{d} \leq \frac{2c-1}{2c+1}p +\frac{p-1}{d}$ $\implies p(1-\frac{2c-1}{2c+1}) \leq \frac{p-1}{d} \implies \frac{2p}{2c+1} \leq \frac{p-1}{d} < \frac{p}{d} \implies 2d< 2c+1 \implies c \geq d$. $\quad \square$ Now, we show that any pair $(c,d)$ satisfying $c \geq d >1$ works. Consider any monic polynomial $Q \in \mathbb{Z}[X]$ with degree $d$. Let $G$ be the directed graph with vertices in $\mathbb{F}_{p}$ where we connect $i \mapsto Q(i) \pmod{p}$. Observe that all connected components in $G$ have a directed cycle and possibly some directed trees connecting to the main cycle. Hence, it is enough to pick $|S|$ containing all the vertices with in-degree equals to $0$. We are going to show that there are at most $\frac{2c-1}{2c+1}p$ such vertices. Assume for the sake of the contradiction that there are more than $\frac{2c-1}{2c+1}p$ vertices with in-degree $0$ in $G$. Notice that by Lagrange's Theorem, $Q(X)$ reaches at least $\frac{p}{d}$ values $\pmod{p} \implies$ there are at most $p-\frac{p}{d}$ with in-degree $0$ in $G \implies p-\frac{p}{d}> \frac{2c-1}{2c+1}p \implies 1-\frac{1}{c}\geq 1-\frac{1}{d}> \frac{2c-1}{2c+1} \implies 2c+1-\frac{2c+1}{c}>2c-1 \implies 2c-1+\frac{1}{c}>2c-1 \implies 0>\frac{1}{c}$, contradiction. $\blacksquare$

rcorreaa wrote: We claim that all pairs $(c,d)$ with $c \geq d >1$ work. To show that $c \geq d$, we pick a prime number $p$ large enough such that $d|p-1$ (it exists by Dirichlet's Theorem). Then, choose $Q(X)=X^d$. Notice that there exactly $\frac{p-1}{d}$ $d$-adic residues in $\mathbb{F}_{p} \implies Q(s)$ achieves at most $\frac{p-1}{d}$ values $\pmod{p}$. Thus, $p=|\bigcup_{s \in S} \{s,\; Q(s),\; Q(Q(s)),\; Q(Q(Q(s))),\; \dots\}| \leq |S|+\frac{p-1}{d} \leq \frac{2c-1}{2c+1}p +\frac{p-1}{d}$ $\implies p(1-\frac{2c-1}{2c+1}) \leq \frac{p-1}{d} \implies \frac{2p}{2c+1} \leq \frac{p-1}{d} < \frac{p}{d} \implies 2d< 2c+1 \implies c \geq d$. $\quad \square$ Now, we show that any pair $(c,d)$ satisfying $c \geq d >1$ works. Consider any monic polynomial $Q \in \mathbb{Z}[X]$ with degree $d$. Let $G$ be the directed graph with vertices in $\mathbb{F}_{p}$ where we connect $i \mapsto Q(i) \pmod{p}$. Observe that all connected components in $G$ have a directed cycle and possibly some directed trees connecting to the main cycle. Hence, it is enough to pick $|S|$ containing all the vertices with in-degree equals to $0$. We are going to show that there are at most $\frac{2c-1}{2c+1}p$ such vertices. Assume for the sake of the contradiction that there are more than $\frac{2c-1}{2c+1}p$ vertices with in-degree $0$ in $G$. Notice that by Lagrange's Theorem, $Q(X)$ reaches at least $\frac{p}{d}$ values $\pmod{p} \implies$ there are at most $p-\frac{p}{d}$ with in-degree $0$ in $G \implies p-\frac{p}{d}> \frac{2c-1}{2c+1}p \implies 1-\frac{1}{c}\geq 1-\frac{1}{d}> \frac{2c-1}{2c+1} \implies 2c+1-\frac{2c+1}{c}>2c-1 \implies 2c-1+\frac{1}{c}>2c-1 \implies 0>\frac{1}{c}$, contradiction. $\blacksquare$ This proof doesn't work. For example if it were to happen that $G$ was just a bunch of directed cycles with no trees hanging out of any cycle, there would be no vertices with indegree $0$ and the above proof would fail, as all vertices are not covered. What one needs to do to fix this issue, apparently is to consider self cycles separately and bound carefully how many of those there can be.

The answer is $c \ge d$. Proof of necessity: Consider $Q(x)=x^d$ and sufficiently large $p \equiv 1 \pmod{d}$. Then $S$ must have size at least $p-|\{s^d: s \in \mathbb{F}_p\}| = \tfrac{d-1}{d} \cdot (p-1)$, implying that \[ \frac{d-1}{d} \cdot (p-1) \le \frac{2c-1}{2c+1} \cdot p, \]whence we can eliminate $p$ and obtain \[ \frac{d-1}{d} > \frac{2c-1}{2c+1} \]as $p$ is large. After rearranging we have $c \ge d$, as needed. Proof of sufficiency: Assume $c \ge d$. Construct the ``arrows" graph $G$ of $Q$ on $\mathbb{F}_p$ (that is, the directed graph determined by $x \rightarrow Q(x)$). Note that each vertex of $G$ has outdegree of $1$ and indegree at most $d$. Furthermore, Lagrange's theorem on $Q(x)-x$ implies that there are at most $d$ self-loops. Let $a_k$ denote the number of cycles of length $k$ in $G$. Note that the number of vertices not contained in any cycle is $p - \sum_{k} ka_k$; then, at least $\tfrac{1}{d}$ of them are have indegree of at least $1$. This induces the bound \[ |S| \le \left( \sum_{k} a_k \right) + \frac{d-1}{d} \cdot \left(p - \sum_{k} ka_k\right) \le \frac{d-1}{d} \cdot p + \frac{1}{d} \cdot a_1 \le \frac{d-1}{d} \cdot p +1 \le \frac{2c-1}{2c+1} \cdot p, \]as desired.

The answer is $c \geq d$. Clearly if $c$ works for some $d$ then so does $d+1$. To show that $c<d$ fails, let $Q(x)=x^d$ and pick some large prime $p \equiv 1 \pmod{d}$, of which there exist infinitely many by Dirichlet. The range of $Q$ contains only $d$-th powers, so $S$ needs to contain every residue that's not a power of $d$, of which there are $\tfrac{d-1}{d}(p-1)$. Since $\tfrac{d-1}{d}>\tfrac{2c-1}{2c+1}$, this is a contradiction for large enough $p$. It now suffices to show $c=d$ works. Consider the functional digraph on $\mathbb{F}_p$ formed by $Q$. Call a number caged if it's not in the range of $Q$, and say a connected component $\mathcal{C}$ is covered by some set $S$ of vertices in it if every vertex in $\mathcal{C}$ can be reached from some vertex in $S$. The following two claims are the pith of the problem. Claim 1: A connected component $\mathcal{C}$ is either a single cycle, or covered by the caged vertices in $\mathcal{C}$. Proof: Note that by infinite pigeonhole, starting from a vertex and "walking" along the digraph implies the existence of some cycle. On the other hand, if we undirect the edges we find that there is at most $1$ cycle, otherwise $E \geq V+1$. Now take an arbitrary non-cycle, find a caged vertex $v$, and delete it; suppose $v$ points towards $w$. If the result is a single cycle then $v$ clearly covers $\mathcal{C}$. Otherwise, by downwards induction the resulting component $\mathcal{C}'$ is coverable by all the caged vertices in it. Adding back $v$ can only possibly remove $w$ as a caged vertex, but every vertex reachable from $w$ is also reachable from $v$, finishing the induction. Note the base case occurs when the result is a single cycle. $\blacksquare$ Claim 2: A connected component $\mathcal{C}$ is either a single cycle of length $1$, or is coverable by at most $\tfrac{d-1}{d}|\mathcal{C}|$ vertices. Proof: If $\mathcal{C}$ is a cycle of length at least $2$ it is coverable by a single element. Otherwise, suppose it has $a$ caged vertices and $b$ noncaged vertices. By Lagrange, each noncaged vertex has indegree at most $d$, so by double-counting edges we require $$a+b \leq db \implies a \leq (d-1)b \implies a \leq \frac{d-1}{d}(a+b)=\frac{d-1}{d}|\mathcal{C}|,$$so taking the caged vertices is satisfactory. $\blacksquare$ Since $d>1$, $Q(x)-x$ has at most $d$ roots in $\mathbb{F}_p$ by Lagrange again. Hence there are at most $d$ cycles of length $1$, and the union of the cover sets generated by claim 2 thus has size at most $$d+\frac{d-1}{d}(p-d)=\frac{d-1}{d}p+1.$$We have $$\frac{d-1}{d}p+1 \leq \frac{2d-1}{2d+1}p \iff d(2d+1) \leq (d(2d-1)-(d-1)(2d+1))p=p,$$which is true, so we're done. $\blacksquare$

Oops I am lazy so here is a sketch: The answer is $c\geq d$. Construction for $c<d$ is $x^d$ which can be shown to work by bounding (and taking $p\equiv 1 \pmod d$ by dirichlet) For $c\geq d$ consider the arrows graph of $Q$. In our set, we need a representative from each "unconnected cycle" which is just a cycle disconnected from the rest of the graph. We also need representatives of each of the at most $\frac{(p-\text{number of vertices in unconnected cycle})(d-1)}{d}$ elements that have indegree $0$. Moreover, these vertices will cover the whole graph in $x, Q(x), \dots$. We can then bound the number of representatives to be at most $\frac{2c-1}{2c+1}p$ as desired