For $p=3$ $x_1$ can take any value. Suppose now that $p\ge 5.$ We prove that $\left(x_1,x_2,\dots,x_{\frac{p-1}2}\right)\in\{0,1\}^{\frac{p-1}{2}}$, clearly anything of this form works. Denote by $M$ the common value mod p of $\sum_{i=1}^{\frac{p-1}{2}}x_i^j$ for $1\le j\le\frac{p-1}{2}.$ Note that $$\sum_{i=1}^{\frac{p-1}{2}}(1-ax_i)^{\frac{p-1}{2}}\equiv \frac{p-1}{2}+M\left(\sum_{i=1}^{\frac{p-1}{2}}(-a)^i\binom{\frac{p-1}{2}}{i}\right)\equiv\frac{p-1}{2}+M[(1-a)^{\frac{p-1}{2}}-1](\text{mod}~p).$$ For $\left(\frac{1-a}{p}\right)=1$ we get that $\left(\frac{1-ax_i}{p}\right)=1.$ If $P$ denotes the set of nonzero square residues mod $p$, we know that $x_iP+(1-x_i)\subseteq P.$ Suppose that $x_i\neq 0$, then $x\to x_ix+(1-x_i)$ is injective, so in fact $x_iP+(1-x_i)=P$. Taking the sum of the elements of the two sets we obtain(the sum of elements of $P$ is 0) $\frac{p-1}{2}(1-x_i)=0$, i.e. $x_i=1.$

Great proof above!!

above. This problem was the big hint.

Edited: Sorry for missing the definition of $a_n$. It is as same as the definition in the link.

Terrific problem. Here's a solution with goodbear and Th3Numb3rThr33. For $p=3$, $x_1$ can be anything. In what follows, $p\ge5$, and the answer is $x_i\in\{0,1\}$ for all $i$; these clearly work, so we show they are the only solutions. Denote by $R$ the set of quadratic residues modulo $p$, and let $a$ be the common value of the $\tfrac{p-1}2$ expressions. Lemma: If for all $q\in R$, we have \[\left(\frac{(q-1)x+1}p\right)=1,\]then $x\in\{0,1\}\pmod p$. Proof. If $g$ is a primitive root modulo $p$, note that \[\sum_{q\in R}q\equiv\sum_{k=0}^{\frac{p-1}2}g^{2k}\equiv\frac{g^{p-1}-1}{g^2-1}\equiv0\pmod p.\]Assume that $x\not\equiv0\pmod p$. Then the linear map $q\mapsto(q-1)x+1$ is surjective, and thus it bijects $R$ to $R$. Thus \[0\equiv\sum_{q\in R}q\equiv\sum_{q\in R}\big((q-1)x+1\big)\equiv(1-x)\left(\frac{p-1}2\right)\pmod p,\]whence $x\equiv1\pmod p$, as desired. $\blacksquare$ For $q\in R$, consider the polynomial $P(x):=\big( (q-1)x+1\big)^{(p-1)/2}$. Note that the sum of the nonconstant coefficients is $P(1)-P(0)\equiv0\pmod p$ by quadratic reciprocity, so \[\sum_{i=1}^{\frac{p-1}2}P(x_i)\equiv a\big(P(1)-P(0)\big)+\frac{p-1}2\equiv\frac{p-1}2\pmod p.\]But $P(x)\in\{0,1,-1\}\pmod p$, so $P(x_i)=1$ for all $i$. It follows that for each $i$, \[\left(\frac{(q-1)x_i+1}p\right)=1\quad\text{for all }n\ne0.\]By the lemma, $x_i\in\{0,1\}\pmod p$ for each $i$, and we are done.

Solution with Aahan Chatterjee, Aatman Supkar, Aditya Khurmi, Andrew, Anushka Aggarwal, Dhrubajyoti Ghosh, Ethan Liu, Maximus Lu, Nishant Dhankhar, Paul Hamrick, R Correaa, Rohan Goyal, Valentio Iverson, William Hu, Will Yue, yuanfeng, and others (and I think the same as #5 and #8 above): Let $n = \tfrac12(p-1)$. For $p=3$, we have $n=1$ and any tuple works. We claim that for $p \ge 5$ there are $2^n$ solutions, namely those for which $x_i \in \{0,1\}$ for all $i$. It is obviously they all work. Claim: For any $x$ in the tuple, the following property holds: whenever $t \ne 0,1$ is a quadratic residue, the number $(t-1)x+1$ is a nonzero quadratic residue. Proof. Let $s$ be the common power sum in the problem statement. Then \begin{align*} \sum_i \left( \frac{x_i+r}{p} \right) &= \sum_i (x_i+r)^n \\ &= s + \binom n1 s r^1 + \dots + \binom{n}{n-1} s r^{n-1} + \binom nn \cdot n \cdot r^n \\ &= s \cdot \left[ \left( \frac{1+r}{p} \right) - \left( \frac rp \right) \right] + n \cdot \left( \frac{r}{p} \right) \\ \implies \sum_i \left( \frac{r^{-1} x_i+1}{p} \right) &= s \cdot \left[ \left( \frac{1+r^{-1}}{p} \right) - 1 \right] + n. \end{align*}By choosing $r = (t-1)^{-1}$, we derive that \[ \sum_i \left( \frac{(t-1)x_i+1}{p} \right) \equiv n \pmod p. \]However, since there are $n$ Legendre symbols, each of which is in $\{-1,0,+1\}$, and $p > 2n$, the only way this can happen is if every Legendre symbol equals $+1$! The conclusion follows. $\blacksquare$ Claim: $x_i \in \{0,1\}$ for each $i$. Proof. Let $Q = \left\{ a^2 \mod p \right\} \setminus \{0,1\}$ be the set of quadratic residues modulo $p$ other than $0$ and $1$. Then, we find that \[ Q \mapsto Q \qquad\text{by}\qquad t \mapsto (t-1)x+1 \]is a bijection (note the RHS never equals $1$). However, from \[ \sum_{t \in Q} t \equiv -1 \pmod p \]for all $p > 3$, summing everything gives \[ -1 \equiv (-1) \cdot x - n \cdot x + n \cdot 1 \pmod p \]which implies $x \equiv 1 \pmod p$ (since $n+1 \not\equiv 0 \pmod p$), as needed. $\blacksquare$ Remark: [Polynomial approach] By Newton sums one can show that \[ \sum_i x_i = s, \quad \sum_{i<j} x_i x_j = \binom s2, \quad \sum_{i<j<k} x_i x_j x_k = \binom s3, \quad \text{etc.} \]One can then define \[ P(X) = \prod_i (X-x_i) = X^s - s X^{s-1} + \binom s2 X^{s-2} \dots. \]If $s \le n$, this will solve the problem outright, since $P(X) = X^{n-s}(X-1)^s$ in that case. For $s > n$, the problem amounts to showing $P(X)$ does not split completely into linear factors. Unfortunately, I was not able to progress further along this route.

v_Enhance wrote: [Polynomial approach] By Newton sums one can show that \[ \sum_i x_i = s, \quad \sum_{i<j} x_i x_j = \binom s2, \quad \sum_{i<j<k} x_i x_j x_k = \binom s3, \quad \text{etc.} \]One can then define \[ P(X) = \prod_i (X-x_i) = X^s - s X^{s-1} + \binom s2 X^{s-2} \dots. \]If $s \le n$, this will solve the problem outright, since $P(X) = X^{n-s}(X-1)^s$ in that case. For $s > n$, the problem amounts to showing $P(X)$ does not split completely into linear factors. Unfortunately, I was not able to progress further along this route. For this see #7. I hope there is a clean proof but I’m sure that the contradiction will be appear on $a_{p-1}$ as I proved in #7. Remarks) Proving $\sum_{cyc} x_1 x_2...x_k = {s \choose k}$ 1. Since it is symmetric, it can be represent as the polynomial of $s$ with degree at most $k$. 2. Since we know $x_i =0$ or $1$ are actually solution, for $s=0,1,...,(p-1)/2$, the value agree to $s \choose k$ modulo $p$. (See #2 for more explanation.) 3. Similar to Lagrange interpolation, the representation passing with those values are unique on degree less than $(p+1)/2$. And therefore, it is precisely $s$ choose $k$.

Fun problem! Write $p = 2k + 1.$ If $k = 1$, it's clear that any singleton will do. Suppose otherwise that $p > 3.$ Otherwise, the answer is all $(x_1, x_2, \cdots, x_k) \in \{0, 1\}^k$. These $k-$tuples evidently work; we'll now show that they are the only solutions. Notice that for any polynomial $P$ which has degree $\le \frac{p-1}{2}$ and has sum of coefficients congruent to $0$ (mod $p$), we have that: $$\sum P(x_i) \equiv P(0) \cdot \left(k - t \right),$$ where $t = \sum x_i.$ Therefore, if we consider the polynomial $P(x) = (b - x)^k - (b-1)^k.$ As this polynomial is divisible by $x-1$, the sum of its coefficients is $0$ and therefore: $$\left(\sum (b - x_i)^k \right) - k (b-1)^k \equiv \left(b^k - (b-1)^k \right) \cdot (k - t),$$ for all integers $b.$ Noticing that $a^k \equiv \left( \frac{a}{p} \right)$ for all integers $a,$ we therefore find from the above that whenever $\left( \frac{b}{p} \right) = \left( \frac{b-1}{p} \right),$ the following holds for all $b$: $$\left(\sum \left(\frac{b-x_i}{p} \right) \right) \equiv k \cdot \left( \frac{b-1}{p} \right).$$ From the fact that $\left( \frac{b-x_i}{p} \right) \in \{-1, 0, 1\}$, simple bounding yields: $$\left( \frac{b - x_i}{p} \right) = \left( \frac{b-1}{p} \right),$$ for all $1 \le i \le k.$ The above implies that for every $1 \le i \le k$ and integer $a$, $\left( \frac{a(a-1)}{p} \right) = 1 \Rightarrow \left( \frac{a(a-x_i)}{p} \right) = 1.$ $\qquad (1)$ We claim that the above implies that $x_i \in \{0, 1\}$, which clearly solves the problem. Suppose that $x_i \notin \{0, 1\},$ for contradiction. It's well-known that whenever a quadratic $f(x) = \alpha x^2 + \beta x + \gamma$ is not a multiple of a perfect square in $\mathbb{Z}_p[x]$, $$\sum_{i = 0}^{p-1} \left( \frac{f(i)}{p} \right) = -1.$$ The above therefore implies that for the functions $f_1(x) = x^2-x$ and $f_2(x) = x^2 - kx,$ there are precisely two roots for each, $\frac{p-3}{2}$ residues for which they evaluate to a nonzero square modulo $p$, and $\frac{p-1}{2}$ for which they evaluate to a non-quadratic residue. From $(1)$, we therefore know that the $\frac{p-1}{2}$ values of $a$ for which $\left( \frac{a(a-1)}{p} \right) = 1$ are precisely those for which $\left( \frac{a(a-k)}{p} \right) = 1.$ Furthermore, for all $a \notin \{0, 1, k\}$, it becomes apparent that: $$\left( \frac{a(a-1)}{p} \right) = \left( \frac{a(a-k)}{p} \right) \Rightarrow \left( \frac{(a-1)(a-k)}{p} \right) = 1.$$ Summing the above over all residue classes and applying our result from above gives a clear contradiction. Hence, our assumption that $x_i \notin \{0, 1\}$ was incorrect and so $(x_1, x_2, \cdots, x_k) \in \{0, 1\}^k$ are our only solutions, as desired. $\square$

Brutal. Let \[t\equiv \sum_{i=1}^n x_i\pmod{p}.\]Let $S_k$ and $P_k$ denote the $k$-th symmetric sum and sum of $k$-th powers for the $x_i$ respectively, so $t\equiv P_i$ for $1\le i\le n$. By induction on $k$, we claim that $S_k \equiv \binom tk \pmod p$. The base case is clear. For the induction step, use Newton's Sums to write \[S_k \equiv \frac 1k \cdot \left[S_{k-1}P_1 - S_{k-2}P_2 + \cdots - (-1)^k P_k\right] = \frac tk \cdot [S_{k-1} - S_{k-2} + \cdots - (-1)^k].\]At this point, remark that it suffices to show $S_{k-1} - S_{k-2}+\cdots - (-1)^k \equiv \binom{t-1}{k-1}\pmod{p}$, so we add this constraint to the induction hypothesis. Again, this result is clear at $k = 1$. Then we have $S_{k-1}-S_{k-2}+\cdots - (-1)^k \equiv \binom t{k-1} - \binom{t-1}{k-2} \equiv \binom{t-1}{k-1}$ as desired. Hence the $x_i$ are the set of roots with multiplicity, arranged in some order, of the $n$-degree polynomial \[P(x)\equiv x^n - \binom t1 x^{n-1} + \binom t2 x^{n-2} - \cdots + (-1)^n \binom tn \pmod p.\]Observe that we can set $0\le t\le p-1$. If $0\le t\le n$, we get that $P(x)\equiv (1-\frac 1x)^tx^n\pmod p$. Hence for $0\le t\le n$, we generate the $n$-tuples $(x_1,x_2,\cdots,x_n)$ such that each $x_i\in \{0,1\}$, all of which trivially work. So suppose $n<t\le p-1$. Note that no $x_i$ may be zero because $p\nmid \binom tn$, hence $P_{p-1} \equiv n\pmod p$. Claim: For all nonnegative integers $k$ and $t$, we have \[\sum_{r=0}^k (-1)^r\binom{t}{r+1}\binom{t+k-r}{k-r} + 1 = \binom{t+k+1}{k+1}.\] Solution: Let the result for a choice of $k$ and $t$ be denoted $Q(k,t)$. We have \[\sum_{r=0}^k (-1)^r\binom{t}{r+1}\binom{t+k-r}{k-r} + 1 = 1+\sum_{r=0}^k (-1)^r\left[\binom{t-1}r + \binom{t-1}{r+1}\right]\binom{t+k-r}{k-r}=\]\[1+\binom{t-1}{0}\binom{t+k}{k} + \sum_{r=0}^{k-1} (-1)^r\binom{t-1}{r+1}\cdot \left[\binom{t+k-r}{k-r} - \binom{t+k-r-1}{k-r-1}\right] + (-1)^k\cdot \binom{t-1}{k+1}\binom t0=\]\[1+\binom{t+k}{k} + \sum_{r=0}^{k-1} (-1)^r\binom{t-1}{r+1}\binom{t+k-r-1}{k-r} + (-1)^k\cdot \binom{t-1}{k+1} =\]\[1+\binom{t+k}{k}+\sum_{r=0}^k (-1)^r\binom{t-1}{r+1}\binom{t+k-r-1}{k-r}.\]Thus $Q(k,t-1)$ implies $Q(k,t)$, so it suffices to demonstrate $Q(k,0)$ for any $k$. But at $t=0$ the result is trivial, so we are done. $\fbox{}$ For $p-1\ge z>n$, note that we have \[P_z \equiv P_{z-1}S_1 - P_{z-2}S_2+\cdots - (-1)^n P_{z-n}S_n\pmod p\]by Newton's Sums. Claim: For all $n-1\ge k\ge 0$, we have \[P_{n+k+1} \equiv t\left[(-1)^n\binom{t+k}k\binom{t-1}{n} - 1\right].\] Solution: We prove this result by induction. At $k=0$, we observe that \[P_{n+1} \equiv \sum_{i=0}^{n-1} (-1)^iP_{n-i}S_{i+1} \equiv t\sum_{i=0}^{n-1} (-1)^i\binom{t}{i+1} \equiv (-1)^nt\left[\binom{t-1}{n} - (-1)^n\right]\pmod p\]by the results on alternating sums. For the induction step, write \[P_{n+k+2} \equiv\]\[t\left[\sum_{r=0}^k (-1)^r \binom t{r+1}\left((-1)^n\binom{t+k-r}{k-r}\binom{t-1}{n} - 1\right) + (-1)^n\left(\binom{t-1}{n} + (-1)^k \cdot (-1)^n\binom{t-1}{k+1}\right)\right]\pmod p.\]It is clear from prior arguments that \[-\sum_{r=0}^k (-1)^r \binom{t}{r+1} \equiv (-1)^{k+1}\cdot \left[\binom t{k+1} - \binom t{k-1}+\cdots (-1)^k\cdot \binom t1 + (-1)^{k+1}\cdot \binom t0 - (-1)^{k+1}\binom t0\right]\equiv \]\[(-1)^{k+1}\cdot \left[\binom{t-1}{k+1} - (-1)^{k+1}\right]\pmod p,\]so it suffices to deal with the multiples of $(-1)^n\binom{t-1}{n}$. But dealing with these multiples is immediate by the first claim, so we are done. $\fbox{}$ Let $k=n-1$ to yield that $n\equiv P_{p-1} \equiv P_{2n} \equiv t\left[(-1)^n\binom{t+n}{n}\binom{t-1}{n} - 1\right] \equiv - t\pmod p$, hence $t$ is $n+1$. Then all roots of the polynomial $P(x)$ are roots of the polynomial $(x-1)^{n+1} \equiv xP(x)-(-1)^n \equiv -(-1)^n\pmod p$. That is, every $x_i$ is a solution to satisfies $(x-1)^2 \equiv (x-1)^{2n+2} \equiv 1\pmod p$, so $x_i$ is either $-1+1 \equiv 0\pmod p$ or $1+1\equiv 2\pmod p$. The former is absurd, as any given $x_i$ may not be $0$. Thus if $p\ge 5$, we get a contradiction because we must have $2n\equiv \sum_i x_i\equiv t\equiv n+1\pmod p$, so $n=1$. At $n=1$, we have $p=3$ and get the additional solution of $x_1=2$.

Here's another solution: The answer is any choices of $0,1$ in $\mathbb{Z}_p$ for $p \geq 5$ where we have at least two equations and $0,1,2$ for $p=3$ We'll prove a stronger statement that the number of variables can be anything less than $\frac{p-1}{2}$.We'll use induction.the base is trivial. Subtract consecutive equations and you'll get:(equations are in $\mathbb{Z}_p$) $$\sum_i (x_i^k - x_i^{k-1}) \equiv 0$$for all $k$.now consider this as a system of equations. The system has a non-trivial solution so the following matrix has determinant $0$:assume that $\frac{p-1}{2} = s$ $$\begin{pmatrix} (x_1^s - x_1^{s-1}) & (x_2^s - x_2^{s-1}) & \cdots & (x_s^s - x_s^{s-1}) \\ (x_1^{s-1} - x_1^{s-2}) & (x_2^{s-1} - x_2^{s-2}) & \cdots & (x_s^{s-1} - x_s^{s-2}) \\ \vdots & \vdots & \cdots & \vdots \\ (x_1^2-x_1) & (x_2^2-x_2) & \cdots & (x_s^2-x_s) \end{pmatrix}$$ The determinant of this , is $0$ . Also if there's an element st $x_i=1$ we can easily apply induction.otherwise , we can cancel the terms $x_i-1$ out of the determinant and the remaining matrix is Vandermonde matrix which has determinant $\prod (x_i - x_j) = 0$ . So at least two of $x_i$'s are equal. Now in the equations that two variables become one with coefficient $2$. Now , both the induction condition and the way we formed the matrix , still works. So we're done by the induction statement(or we can keep doing this and reaching one variable...in any case it cannot be the case that all coefficients are $0$ since they are at most $\frac{p-1}{2}$)

Really neat Vandermonde determinant problem (my solution is the same as above)! I should probably try solving it in the intended way though. Work over $\mathbb{F}_p$. We rephrase the condition as $\det A=0$, where $A$ is the $\tfrac{p-1}{2} \times \tfrac{p-1}{2}$ matrix with entries $(A)_{ij} = x_j^{i+1}-x_j^i$. We can write \[ \det A = \left(\prod (x_i - 1)\right) \cdot \det V, \]where $V$ is the Vandermonde matrix on $x_1, \dots, x_{\tfrac{p-1}{2}}$. Thus, \[ 0 = \det A = \left(\prod (x_i - 1)\right)\left(\prod_{i>j} (x_i - x_j) \right), \]so either one of the $x_i$ is $1$, or there are two $x_i$ equal (or both). Call this fact Claim 0. Claim: Let $p \ge 5$. In general, for $2 \le w \le \tfrac{p-1}{2}$, if \[ \sum_{i = 1}^{w} x_{i} = \sum_{i = 1}^{w} x_{i}^{2} = \cdots = \sum_{i = 1}^{w} x_{i}^{\frac{p-1}{2}}, \]then each of the $x_i$ are either $0$ or $1$, and all such solutions work. (This is assuming Claim 0.) Proof. It is obvious that all binary strings work. For the other direction, we induct on $w \ge 2$, with the base case $w=2$ trivial. Suppose that the claim holds for $w=k$. I contend that if $(x_1, \dots, x_{k+1})$ works, then $x_{k+1} \in \{0, 1\}$, which would complete the inductive step. Assume for contradiction that $x_{k+1} \not\in \{0, 1\}$. Then \[ (x_{k+1}-1)\left(\prod (x_{k+1}-x_i)\right) \]is nonzero, which means that \[ \left(\prod_{i < k+1} (x_i - 1)\right)\left(\prod_{k+1>i>j} (x_i - x_j) \right)=0. \]Thus by Claim 0 and inductive hypothesis, $(x_1, \dots, x_k)$ works. Subtracting the equations for $(x_1, \dots, x_{k+1})$ and $(x_1, \dots x_k)$, we have \[ x_{k+1} = x_{k+1}^2 = \dots = x_{k+1}^{\frac{p-1}{2}}, \]which holds if and only if $x_{k+1} \in \{0, 1\}$. Therefore, the inductive step holds. Claim: When $p=3$, all tuples work. Proof. Trivial as $\tfrac{p-1}{2} = 1$. By the previous two claims, the only solutions are $\{(0), (1), (2)\}$ for $p=3$ and $\{0, 1\}^{\frac{p-1}{2}}$ for $p \ge 5$. End proof.

for $p=3$ problem is trivial consider $p \geq 5$. We claim the solution are those which are $x_i \equiv 1,0(mod p)$ always. Easy to see these works, say we have a solution other than these. Easy to see these works, say we have a solution other than these. Claim: For any integer $a$ thats not $0,1(mod p)$ There exists a integer $x$ such that $(\frac{x}{p})=(\frac{x+1}{p}) \neq (\frac{x+a}{p}) $ and this none of the terms involved are $0$. Assume the contrary no of solutions of $(\frac{x}{p})=(\frac{x+t}{p})$ for non zero $t$ are all equal. So its easy to see $(\frac{x+a}{p})=(\frac{x+1}{p})$ would also imply that its equal to $(\frac{x}{p})$ and similarly for the other pair. But for any $x$ such that all the 3 terms are non zero atleast two must be equal But then it quickyl gives contradiction Now consider the polynomial $p(x)=\sum (x+x_i)^{\frac{p-1}{2}}$ in $\mathbb{F}_{p}[X]$. Its easy to see if $S=\sum_{i=1}^{\frac{p-1}{2}} x_i$ expand We have $p(x) \equiv \frac{p-1}{2}x^{\frac{p-1}{2}}+S((X+1)^{\frac{p-1}{2}}-X^{\frac{p-1}{2}})$ Now say we have $x_1 \neq 0,1(mod p)$ Choose some $x$ such that $(\frac{x}{p})=(\frac{x+1}{p}) \neq (\frac{x+a_1}{p}) $ U will quickly get contradiction and get for the $mod p$ relation to hold it has to be equal. Now consider the polynomial $p(x)=\sum (x+x_i)^{\frac{p-1}{2}}$ in $\mathbb{F}_{p}[X]$. Its easy to see if $S=\sum_{i=1}^{\frac{p-1}{2}} x_i$ expand We have $p(x) \equiv \frac{p-1}{2}x^{\frac{p-1}{2}}+S((X+1)^{\frac{p-1}{2}}-X^{\frac{p-1}{2}})$ Now say we have $x_1 \neq 0,1(mod p)$ Choose some $x$ such that $(\frac{x}{p})=(\frac{x+1}{p}) \neq (\frac{x+a_1}{p}) $ U will quickly get contradiction and get for the $mod p$ relation to hold it has to be equal.