Nice problem! If $d\ge p-1$ the problem is clear (we have $\frac{p-1}{d}\le 1\le k-1\le p-2\le (p-1)\left(1-\frac{1}{d}\right)$ ) , so from now on suppose that $d\le p-2.$ Let $e=\lfloor\frac{p-2}{d}\rfloor.$ Throughout the solution we will use the following well known fact: Fact: $\sum_{x=1}^{p}x^n\equiv 0(\text{mod}~p)$ for any $0\le n\le p-2.$ Step 1. $e\le k-2$ Proof: By Fact we know that $\sum_{x=1}^{p} f(x)^n\equiv 0(\text{mod}~p)$ for any $0\le n\le e.$ (Expand everything: the highest degree will be at most $de\le p-2.$) Let $f(1),f(2),...,f(p)$ take values $a_1,...,a_k$ modulo $p$ with multiplicities $b_1,...,b_k.$ If $e\ge k-1$ then $\sum_{i=1}^{k}b_1\cdot a_i^{n}\equiv 0(\text{mod}~p)$ for any $n\le k-1.$ Therefore, in $\Bbb{F}_p$ we have that $$\begin{pmatrix} a_1^{k-1} & a_2^{k-1} & \cdots & a_k^{k-1} \\ a_1^{k-2} & a_2^{k-2} & \cdots & a_k^{k-2} \\ \vdots & \vdots & \cdots & \vdots \\ a_1^{2} & a_2^{2} & \cdots & a_k^{2} \\ a_1 & a_2 & \cdots & a_k \\ 1 & 1 & \cdots & 1 \end{pmatrix} \cdot \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_k \end{pmatrix} = \bold{0}.$$ But the Vandermonde matrix has non-zero determinant $\prod_{i<j}(a_i-a_j)$, so multiplying with its inverse we obtain $ \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_k \end{pmatrix}= \bold{0}$, which is easily seen to be impossible by $1<k<p.$ Step 2. $e\le p-k-1$ Proof: Let $c_1,...,c_{p-k}$ be the residues not taken by $f$. From Step 1 we know that $\sum_{i=1}^{k} b_i\cdot a_i^n\equiv 0 (\text{mod}~p)$ for $0\le n\le e$, so using Fact we can say that $$\sum_{i=1}^{k}(b_i-1)\cdot a_i^n\equiv \sum_{j=1}^{p-k}c_j^n(\text{mod}~p)$$for $0\le n\le e.$ If $e\ge p-k$, then using the above congruences for $n\le p-k$ and noting that $\sum_{i=1}^{k}(b_i-1)=p-k$, we easily obtain, using the theory of symmetric polynomials, that $\prod_{i=1}^{k}(x-a_i)^{b_i-1}=\prod_{j=1}^{p-k}(x-c_j)$ as polynomials in $\Bbb{F}_p[x].$ But $\Bbb{F}_p[x]$ is an UFD, so the linear factors must coincide, which is clearly impossible. (Step 1 can be proved in a similar way, but I liked the linear algebra idea ) In conclusion, by Step 1 we know that $k-1\ge e+1\ge\frac{p-1}{d}$, and by Step 2 that $p-k\ge e+1\ge\frac{p-1}{d}$, which can be rewritten as $k-1\le (p-1)\left(1-\frac{1}{d}\right).$

huricane wrote: Nice problem! If $d\ge p-1$ the problem is clear,$ Can you explain more plz??

huricane wrote: Nice problem! If $d\ge p-1$ the problem is clear (we have $\frac{p-1}{d}\le 1\le k-1\le p-2\le (p-1)\left(1-\frac{1}{d}\right)$ ) , so from now on suppose that $d\le p-2.$ Let $e=\lfloor\frac{p-2}{d}\rfloor.$ Throughout the solution we will use the following well known fact: Fact: $\sum_{x=1}^{p}x^n\equiv 0(\text{mod}~p)$ for any $0\le n\le p-2.$ Step 1. $e\le k-2$ Proof: By Fact we know that $\sum_{x=1}^{p} f(x)^n\equiv 0(\text{mod}~p)$ for any $0\le n\le e.$ (Expand everything: the highest degree will be at most $de\le p-2.$) Let $f(1),f(2),...,f(p)$ take values $a_1,...,a_k$ modulo $p$ with multiplicities $b_1,...,b_k.$ If $e\ge k-1$ then $\sum_{i=1}^{k}b_i\cdot a_i^{n}\equiv 0(\text{mod}~p)$ for any $n\le k-1.$ Therefore, in $\Bbb{F}_p$ we have that $$\begin{pmatrix} a_1^{k-1} & a_2^{k-1} & \cdots & a_k^{k-1} \\ a_1^{k-2} & a_2^{k-2} & \cdots & a_k^{k-2} \\ \vdots & \vdots & \cdots & \vdots \\ a_1^{2} & a_2^{2} & \cdots & a_k^{2} \\ a_1 & a_2 & \cdots & a_k \\ 1 & 1 & \cdots & 1 \end{pmatrix} \cdot \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_k \end{pmatrix} = \bold{0}.$$ But the Vandermonde matrix has non-zero determinant $\prod_{i<j}(a_i-a_j)$, so multiplying with its inverse we obtain $ \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_k \end{pmatrix}= \bold{0}$, which is easily seen to be impossible by $1<k<p.$ Step 2. $e\le p-k-1$ Proof: Let $c_1,...,c_{p-k}$ be the residues not taken by $f$. From Step 1 we know that $\sum_{i=1}^{k} b_i\cdot a_i^n\equiv 0 (\text{mod}~p)$ for $0\le n\le e$, so using Fact we can say that $$\sum_{i=1}^{k}(b_i-1)\cdot a_i^n\equiv \sum_{j=1}^{p-k}c_j^n(\text{mod}~p)$$for $0\le n\le e.$ If $e\ge p-k$, then using the above congruences for $n\le p-k$ and noting that $\sum_{i=1}^{k}(b_i-1)=p-k$, we easily obtain, using the theory of symmetric polynomials, that $\prod_{i=1}^{k}(x-a_i)^{b_i-1}=\prod_{j=1}^{p-k}(x-c_j)$ as polynomials in $\Bbb{F}_p[x].$ But $\Bbb{F}_p[x]$ is an UFD, so the linear factors must coincide, which is clearly impossible. (Step 1 can be proved in a similar way, but I liked the linear algebra idea ) In conclusion, by Step 1 we know that $k-1\ge e+1\ge\frac{p-1}{d}$, and by Step 2 that $p-k\ge e+1\ge\frac{p-1}{d}$, which can be rewritten as $k-1\le (p-1)\left(1-\frac{1}{d}\right).$ Nice solution，I just think about Langrange，and no use at all

This problem reminds me of this...

lminsl wrote: This problem reminds me of this... A lot of the participants thought of this problem during the competition. However, any approach used there fails.

ngree wrote: huricane wrote: Nice problem! If $d\ge p-1$ the problem is clear,$ Can you explain more plz?? Use Euler's Thm ......

Does anyone have the official solution? The website of the olympiad seems to be down...

See https://imogeometry.blogspot.com/p/international-olympiad-of-metropolises.html?m=1 There is this Google Drive link https://drive.google.com/file/d/0B2qYu535vGeQa0pRaUZYVzV1dU0/view?usp=sharing, apart from the geometry problems (the link is under the title "International Olympiad of Metropolises all 2016-21 in pdf with solutions").

a_507_bc wrote: See https://imogeometry.blogspot.com/p/international-olympiad-of-metropolises.html?m=1 This seems to contain only geometry problems. Anyway, I think I reached it in another way and will put it here perhaps.

We shall repeatedly use the following well known lemma (follows by using a primitive root): $\sum_{i=1}^p i^k \equiv 0 \pmod p$ if $p-1$ does not divide $k$ (in particular this holds for all $k \leq p-2$). We firstly prove $\frac{p-1}{d} \leq k-1$. Let $u_1,u_2,\ldots,u_k$ be the different remainders of $f(1),\ldots,f(p)$ mod $p$. The problem statement requires $k\geq 2$, so the polynomial $g(x) = (f(x) - u_1)(f(x) - u_2) \cdots (f(x) - u_{k-1})$ attains exactly two values mod $p$, namely $0$ and $(u_k - u_1)(u_k - u_2)\cdots (u_k - u_{k-1})$. In particular, $\sum_{i=1}^p g(i)$ is some non-zero multiple of $(u_k - u_1)(u_k - u_2)\cdots (u_k - u_{k-1})$. On the other hand, if we assume for contradiction that $\deg g \leq p-2$, then $\sum_{i=1}^p g(i) \equiv 0 \pmod p$ by the lemma, contradiction. Therefore $d(k-1) = \deg g \geq p-1$ and the desired inequality follows. Now we move on to proving $k-1 \leq (p-1)\left(1-\frac{1}{d}\right)$. Recall from the theory of symmetric polynomials that if $w_1,\ldots,w_s$, $s\leq p-1$ are (not necessarily distinct) residues mod $p$, then the values of the power sums $r_j = w_1^j + \cdots w_s^j$ uniquely determine these of $w_1,\ldots,w_s$. We shall use this with $s = p-k$ (note that $s>0$ since the problem condition requires $k<p$) where $w_1,\ldots,w_s$ are the residues not attained by $f$ -- we wish to prove $ds \geq p-1$. Suppose the contrary, i.e. $ds < p-1$. Let $u_1,\ldots,u_s$ be the residues which appear more than once (repetitions included). The assumption $ds < p-1$ implies that $f(x), f(x)^2, \ldots, f(x)^s$ have degrees less than $p-1$, so by the lemma we obtain that for $j=1,\ldots,s$ the sum of the $j$-th powers of all residues is $0$ mod $p$. On the other hand, this sum is $\sum_{i=1}^p i^j + \sum_{i=1}^s w_i^j - \sum_{i=1}^s u_i^j \equiv \sum_{i=1}^s w_i^j - \sum_{i=1}^s u_i^j$ for $j\leq s \leq p-2$ by the lemma (note that $d\geq 1$, since $d=0$ would imply $k=1$). Therefore $\sum_{i=1}^s w_i^j \equiv \sum_{i=1}^s u_i^j$ for $1 \leq j\leq s$ and hence the collections of $w$-s and $u$-s in the same by the above fact from the theory of symmetric polynomials, contradiction.