Let $n \geq 3$ be a positive integers and $p$ be a prime number such that $p > 6^{n-1} - 2^n + 1$. Let $S$ be the set of $n$ positive integers with different residues modulo $p$. Show that there exists a positive integer $c$ such that there are exactly two ordered triples $(x,y,z) \in S^3$ with distinct elements, such that $x-y+z-c$ is divisible by $p$.
Problem
Source: Vietnam TST 2021 P6
Tags: number theory, prime numbers
05.04.2021 00:37
So when you say with distinct elements does it mean that every triplet $(x,y,z)$ cant have $x=y$?How do we distinguish different triplets, I mean since $(x,y,z)$ is ordered then it is different from $(y,z,x)$ right?
06.04.2021 01:11
The statement means: $x,y,z$ are pairwise distinct. And we notice that if $(x,y,z)$ such that $p|x-y+z-c$ then so does $(z,y,x)$. Hence, the problem can rephrase as: there exists a positive integer $c$ such that there exists unique ordered triples $(x,y,z) \in S^3$ with $x,y,z$ are pairwise distinct, $x<z$ and $p|x+z-y.$ I tried this problem with sum-free theorem, probabilistic method, ... but got nothing. Hope someone can give me some hint.
07.04.2021 09:57
Consider $n=4,m=257, $ and $\mathbb {N}=\{1,3,9,17\}$ All the possible sum $x-y+z $ are different.
07.04.2021 18:48
Physicsknight wrote: Consider $n=4,m=257, $ and $\mathbb {N}=\{1,3,9,17\}$ All the possible sum $x-y+z $ are different. 1. As @yumeidesu has mentioned, $(x,y,z)$ and $(z,y,x)$ give the same $x - y + z$. It will always be two pairs with the same modulo unless we restrict with the condition $x<z$. 2. It is obvious that you can show a set with all different $x - y + z \pmod p$ for $p$ sufficiently large (given the condition $x<z$), but that is not what this problem is asking for. It means that if you choose an arbitrary set $S$, there is always a triple $(x_0,y_0,z_0)$ with $x_0 < z_0$ such that $x_0-y_0+z_0 \pmod p$ is unique, or in other words, different from all other possible $x-y+z \pmod p$ for any other triple $(x,y,z)$ with $x < z$.
08.04.2021 03:03
Any solution? This problem is way too hard.
09.04.2021 11:30
Let $S = \{x_1,x_2,\ldots,x_n\}$. For an integer $n$, let $[n]$ be the remainder when $n$ is divided by $p$. Remark. For $[a] \neq 0$, if $aS+b := \{[ax_i + b] : 1 \le i \le n \}$ is satisfied the given condition then so is $S$. We will prove the following statement: There exists integers $a$ and $b$ such that $[a] \neq 0$ and $aS+b \subset [0,p/3]$. Take an integer $c$ that $0 \in S' := S+c$. Let $y_1,y_2,\ldots,y_{n-1}$ be $n-1$ non-zero elements of $S'$. For $k = 0, 1, ..., n$, denote $A_i = [kp/6,(k+1)p/6)$. By pigeonhole principle, there exists a subset $T \subset \{0,1,2,\ldots,p-1\}$ such that $$|T| \ge \left \lfloor \dfrac{p+6^{n-2}-1}{6^{n-2}} \right \rfloor \ge 6$$and for $1 \le i \le n-2$, there is $1 \le j = j(i) \le 6$ such that $\{[ay_i] : a \in T\} \subset A_j$. Since $|T| \ge 6$, it is easy to see that there are two distinct numbers $d,e \in T$ such that $[dy_{n-1}-ey_{n-1}] \le p/6$ or $[dy_{n-1}-ey_{n-1}] \ge 5p/6$. So, by take $a = d-e$, by above arguments, if $x \in aS'$ then $x \le p/6$ or $x \ge 5p/6$. Take this $a$ and a suitable integer $b$, we have $aS+b \subset [0,p/3]$. By the remark, the remaining part of the solution is proving $aS+b$ satisfies the given condition. Let $aS+b = \{t_1,t_2,\ldots,t_n\}$. We arrange its elements increasing order $t_1 < t_2 < \ldots < t_n$. Take $c = t_n + t_{n-1}-t_1$. So $c < 2p/3$. Then for there distinct elements $x,y,z$ in $aS+b$, we have $-p/3 <x-y+z <= t_n + t_{n-1}-t_1 = c$, so if $p ~ | ~ x-y+z-c$, then $x-y+c = c = t_n +t_{n-1}-t_1$. By the arranging, $\{t_n,t_{n-1}\} = \{x,z\}$ and $t_1 = y$. $\Box$ Remark. The boundary of $p$ can be given as $p > 5.6^{n-2}$ since in the above solution, it requires $|T| \ge 6$ only.
26.05.2022 16:38
Claim: let $S=\{r_1, \cdots, r_n\}$. There exist $a_1, a_2 \in \mathbb{Z}_p$ such that $\lfloor 6\frac{a_1r_j}{p} \rfloor=\lfloor 6\frac{a_2r_j}{p} \rfloor$ for all $j$. This solves the problem because we can replace the elements $ar_j$, and notice $\{ \frac{(a_1-a_2)r_j}{p}+\frac 16 \} \in [0, \frac p3)$ and now we can take $r_i, r_j$ minimal and $r_k$ maximal. This proves if $p> 6^n$ we win. We can do some more precise bounding. First notice if $\lfloor 6\frac{a_1r_j}{p} \rfloor - \lfloor 6\frac{a_2r_j}{p}\rfloor$ is constant mod 6 then $a_1-a_2$ makes all the transformed intervals lie in a interval of length $p/3$. Therefore, we can "discard" the first residue in $S$. I claim if $p>5\cdot 6^{n-2}$ we win. We don't need to care about the first residue in $S$. We repeatedly pick the $m$ with the highest number of solutions $\lfloor 6\frac{ar_j}{p}\rfloor=m$ Let $S_t$ be the number of residues after picking the first t elements. It follows $S_{n-2}\ge 6$ and we can take two differences from there with at most $\frac p6$. Done.
07.06.2022 08:32
Here is a more polished writeup with motivation: Okay, the condition that there are exactly two ordered tuples suggest only $(x,y,z)$ and $(y,x,z)$ satisfy the condition for $c$. If the domain is not in $\mathbb{Z}_p$ but in $\mathbb{Z}$ or $\mathbb{R}$, then the problem is easy: sort the elements of $S$ as $s_1<s_2<\cdots < s_n$, then $(s_1,s_2,s_n)$ works for size reasons, for $x+y-z\ge s_1+s_2-s_n$ with equality only holding at $(x,y,z) \in \{(s_1,s_2,s_n), (s_2,s_1,s_n)\}$ If the $s_i$'s are within some interval of length $\frac p3$, we're done by the same argument. Luckily, we are still done if $R(as_j+b,p)$ is within an interval of length $\frac p3$ We can shift $b$, so we can have $|| \frac{as_j+b}{p} || < \frac 16$ and be done. This should ring some bells on the principle used in the Dirichlet's approximation theorem. We can first settle the case where $p>6^n$ with a simple pigeonhole argument that satisfies $|| \frac{as_j}{p} || < \frac 16$: consider blocks $(x_1,x_2,\cdots,x_n)$ where $x_j\in \{0,1,2,3,4,5\}$. Define $f(a)=\left(\lfloor 6\{ \frac{as_1}{p}\} \rfloor, \lfloor 6\{ \frac{as_2}{p}\} \rfloor, \cdots, \lfloor 6\{ \frac{as_n}{p}\} \rfloor \right)$ There exists $1\le a_1,a_2\le 6^n+1$ st $f(a_1)=f(a_2)$. Then $|a_1-a_2|$ satisfies the criteria. Now, we invoke the other degree of freedom $b$ that finishes the same argument for $p>6^{n-1}$. In $(\mathbb{Z}_6)^n$, we put $(c,\cdots,x_n+c)$ in the same group for fixed $x_2,\cdots,x_n$ and $c$ varies in $\mathbb{Z}_6$. Repeat the same pigeonhole principle argument suggests there is a point in $f(a_1)=(c,x_2+c,\cdots,x_n+c)$ and $f(a_2)=(d,x_2+d,\cdots,x_n+d)$. WLOG $a_1>a_2$, then $a_1-a_2$ satisfies $f(a_1-a_2)$ has all entries in $\{d-c, d-c-1\}$ mod 6, which means $\{ \frac{(a_1-a_2)s_j}{p} \}$ is contained in $[\frac{d-c-1}{6}, \frac{d-c+1}{6})$ Finally, we optimize the argument a bit to make it work for $p>5\cdot 6^{n-2}+1$. As mentioned before, only $(x_2-x_1, x_3-x_1, \cdots, x_n-x_1)$ matters. By pigeonhole principle, there exists $j\in \{0,\cdots,5\}$ such that at least $5\cdot 6^{n-3}+1$ satisfy $x_2-x_1\equiv j(\bmod\; 6)$. Repeating the same argument, there exists $j_2,\cdots,j_{n-1}$ and at least $6$ $a$'s (call $a_1,\cdots,a_6$) such that they all have $x_t-x_1=j_t$. Define $x_{i,n}$ st $f(a_i)=(c_i,j_2+c_i,\cdots,j_{n-1}+c,x_{i,n}+c_i)$. We have $\{ \frac{(a_i-a_j)s_k}{p} \} \in [\frac{c_i-c_j-1}{6}, \frac{c_i-c_j+1}{6})$ for all $1\le k\le n-1$. Therefore, we only need to worry about $s_n$ working. For $1\le i\le 6$, let $g(i)\in [0,1)$ such that $g(i)\equiv \frac{a_is_n}{p} - \frac{c_i}{6} (\bmod\; 1)$. Suppose $g(i_1)<g(i_2)<\cdots<g(i_6)<1+g(i_1)$. Say $t$ satisfies $g(i_t)-g(i_{t-1})<\frac 16$, for the case where $1+g(i_1)-g(i_6)<\frac 16$ is similar. Then $$ \left\{ \frac{(a_{i_t}-a_{i_{t-1}})s_n}{p} - \frac{c_{i_t}-c_{i_{t-1}}}{6} \right\} = \left\{ \left(\frac{a_{i_t}s_n}{p} - \frac{c_{i_t}}{6} \right) - \left(\frac{a_{i_{t-1}}s_n}{p} - \frac{c_{i_{t-1}}}{6} \right) \right\} < \frac 16$$ Therefore, picking $a=a_{i_t}-a_{i_{t-1}}$ satisfies $$\left\{ \frac{as_j}{p} \right\} \in \left[\frac{c_{i_t}-c_{i_{t-1}}-1}{6}, \frac{c_{i_t}-c_{i_{t-1}}+1}{6} \right] (\bmod\; 1)$$ For all $1\le k\le n$. The conclusion follows.