Given positive integer $n$. Prove that for any integers $a_1,a_2,\cdots,a_n,$ at least $\lceil \tfrac{n(n-6)}{19} \rceil$ numbers from the set $\{ 1,2, \cdots, \tfrac{n(n-1)}{2} \}$ cannot be represented as $a_i-a_j (1 \le i, j \le n)$.
Problem
Source: 2021 China TST, Test 1, Day 1 P3
Tags: number theory, Additive Number Theory
18.03.2021 06:43
The official solution (sorry for bad English and LaTex): Let $m:=\frac{n(n-1)}{2}$, $M:=\{1,\ldots,m\}$ and $D:=\{a_i-a_j: a_i>a_j, 1\leq i,j\leq n\}=\{d_1,\ldots,d_m\}$ be the multiset of differences. Then let $A:=M\cap D$, $B:=M\backslash A=\{b_1,\ldots,b_t\}$, $C:=D\backslash A=\{c_1,\ldots,c_t\}$. Here $t$ is the number wanted to be larger than $\lceil \frac{n(n-6)}{19} \rceil$. Consider the generating function $F(z):=z^{a_1}+\cdots+z^{a_n}$, $G(z):=F(z)F(\frac{1}{z})=n+\sum (z^{d_k}+z^{-d_k})$, $H(z):=z^{-m}+z^{-m+1}+\cdots+1+z+\cdots+z^m$. We have $G(z)=n-1+H(z)-\sum (z^{b_l}+z^{-b_l}) + \sum (z^{c_l}+z^{-c_l})$. Take $|z|=1$, then $G(z)=|F(z)|^2\geq 0$ and $|G(z)-(n-1)-H(z)|\leq 4t$. Write $z$ as $e^{2i\theta}$ then $H(z)=\frac{\sin(2m+1)\theta}{\sin\theta}$. Take $(2m+1)\theta=\frac{3}{2}\pi$, we have $H(z)=-\frac{1}{\sin\theta}<-\frac{n^2-n+1}{\frac{3}{2}\pi}$. Hence $|G(z)-(n-1)-H(z)|\geq \frac{2}{3\pi}(n^2-(1+\frac{3\pi}{2})n)$. So we can get $t\geq \frac{1}{6\pi}n(n-6)$.
18.03.2021 07:24
Soon wrote: The official solution (sorry for bad English and LaTex): Let $m:=\frac{n(n-1)}{2}$, $M:=\{1,\ldots,m\}$ and $D:=\{a_i-a_j: a_i>a_j, 1\leq i,j\leq n\}=\{d_1,\ldots,d_m\}$ be the multiset of differences. Then let $A:=M\cap D$, $B:=M\\ A=\{b_1,\ldots,b_t\}$, $C:=D\\ A=\{c_1,\ldots,c_t\}$. Here $t$ is the number wanted to be larger than $\lceil \frac{n(n-6)}{19} \rceil$. Consider the generating function $F(z):=z^{a_1}+\cdots+z^{a_n}$, $G(z):=F(z)F(\frac{1}{z})=n+\sum (z^{d_k}+z^{-d_k})$, $H(z):=z^{-m}+z^{-m+1}+\cdots+1+z+\cdots+z^m$. We have $G(z)=n-1+H(z)-\sum (z^{b_l}+z^{-b_l}) + \sum (z^{c_l}+z^{-c_l})$. Take $|z|=1$, then $G(z)=|F(z)|^2\geq 0$ and $|G(z)-(n-1)-H(z)|\leq 4t$. Write $z$ as $e^{2i\theta}$ then $H(z)=\frac{\sin(2m+1)\theta}{\sin\theta}$. Take $(2m+1)\theta=\frac{3}{2}\pi$, we have $H(z)=-\frac{1}{\sin\theta}<-\frac{n^2-n+1}{\frac{3}{2}\pi}$. Hence $|G(z)-(n-1)-H(z)|\geq \frac{2}{3\pi}(n^2-(1+\frac{3\pi}{2})n)$. So we can get $t\geq \frac{1}{6\pi}n(n-6)$.
22.03.2021 07:20
This is 2002 China TST It is good to see old problems coming back
25.03.2021 15:54
Let there be $k$-non representable numbers among $1,...,\frac{n(n-1)}{2}$ which means there are $2k$ non representable numbers among $-\frac{n(n-1)}{2},...,\frac{n(n-1)}{2}$ Take this : $$|p(t)|^2=p(t)p(-t)=(e^{ia_1t} +e^{ia_2t}+...+e^{ia_nt})(e^{-ia_1t}+...+e^{-ia_nt})=n+\sum_{i\neq j}e^{i(a_i-a_j)}$$And compare it to the $\frac{n(n-1)}{2}$-dirchlet kernel (plus $n-1$). $$n-1+D(t)=n-1+e^{-i\frac{n(n-1)}{2}t}+...+1+e^{it}+...+e^{i\frac{n(n-1)}{2}t}=n-1+\frac{\sin(\frac{n^2-n+1}{2}t)}{\sin(\frac{1}{2}t)}$$In $|p(t)|^2-(n-1+D(t))$ ,all terms $e^{imt}$ , $m=1,2,3,...,\frac{n(n-1)}{2},-1,-2,...,-\frac{n(n-1)}{2}$ where $m$ is representable cancel each other thus the difference contains at most $4k$ terms. Therefore $$||p(t)|^2-(n-1+D(t))|\le 4k$$If you take $t=\frac{3\pi}{n^2-n+1}$ goes to the negative end , in particular $-D(t)=\frac{1}{\sin(\frac{3\pi}{2(n^2-n+1)})}\ge\frac{2(n^2-n+1)}{3\pi} $ and $4k\ge |p(t)|^2-(n-1+D(t))\ge \frac{2(n^2-n+1)}{3\pi} -n+1$ which gives $k>\frac{n^2-6n}{6\pi}$ ^^below : I have no idea but one thing that I do know is that every approach other than gf failed
25.03.2021 17:25
@mela_20-15 Which technique or topic is this?
27.03.2021 03:39
Bump. I have never seen any technique like this. Is there somewhere I can learn about this? Additionally, is there any purely combinatorial interpretation? I am still very confused about this. Also, did anyone in China solve this in contest If so how so good
27.03.2021 05:25
Many hours of pain and suffering and screaming at my viewers later, I have the same solution as everyone else: The idea is to consider the generating function \[ f(X) = \sum_i X^{a_i}. \]Then, we may write \[ f(X)f(X^{-1}) - \sum_{-\binom n2}^{\binom n2} X^k = (n-1) + \sum_{k > 0} c_k \left( X^k + X^{-k} \right) \]for some constants $c_k$. It is easy to see that Every $c_k \ge -1$, and $c_k = -1$ exactly if $k$ is ``missed''; $\sum c_k = 0$; and hence if $t$ is the number of ``missed'' terms, then $\sum |c_k| = 2t$, and we want $t \ge \left\lceil \frac{n(n-6)}{19} \right\rceil$. We now specialize to the choice \[ X = \omega = \exp\left( \frac{3\pi i}{n^2-n+1} \right). \]On the one hand, the left-hand side is at most $(n-1) + 4t$, by the triangle inequality. On the other hand, the left-hand side equals \[ \left\lvert f(\omega) \right\rvert^2 + \sum_{-{\binom n2}}^{\binom n2} \omega^k. \]This is a real number, because the expression is self-conjugate. We drop the first term, because it is nonnegative, and evaluate the second sum exactly: \begin{align*} \sum_{-{\binom n2}}^{\binom n2} \omega^k &= - \omega^{-\binom n2} \cdot \frac{\omega^{n^2-n+1}-1}{\omega-1} = \frac{2}{\omega^{\binom n2+1} - \omega^{\binom n2}} = \frac{2}{\omega^{\binom n2+1} + \frac{1}{\omega^{\binom n2+1}}} \\ &= \sec \left( \frac{\binom n2+1}{n^2-n+1} \cdot 3\pi \right) = \frac{1}{\sin\left( \pi \cdot \frac{(n^2-n+1)-3(n(n-1)+2)}{2n^2-2n+2} \right)} \\ &= \frac{1}{\sin\left( \pi \cdot \frac{-2n^2+2n-5}{2n^2-2n+2} \right)} = \frac{1}{\sin\left( \pi \cdot \left( \frac{-3}{2n^2-2n+2} \right) - \pi \right)} \\ &= \frac{1}{\sin\left( \pi \cdot \frac{3}{2n^2-2n+2} \right)} \ge \frac{2n^2-2n+2}{3\pi} \ge \frac{2n^2-2n+2}{19/2} \\ &= \frac{4n^2-4n+4}{19}. \end{align*}Hence, it follows that \[ 4t \ge \frac{4n^2-4n+4}{19} - (n-1) \ge \frac{4n^2-23n+23}{19} \ge \frac{4n^2-24n}{19}. \]The problem is solved. Remark: $6\pi < 19$.
17.04.2021 10:23
Solution is similar to many above but posting for storage. Groupsolved with p_square, biomathematics. Let $f(x)=\sum_{i=1}^{n} x^{a_i}$. Now, $f(x)f(1/x)=n+\sum_{1\le i,j \le n} x^{a_i-a_j}$ Let $g(x)=\sum_{i=1}^{\binom{n}{2}} x^{i}+x^{-i}$. Now, observe that $f(x)f(1/x)-g(x)-n$ has term $x^k+x^{-k}$ with coefficient $-1$ if k is not representable as $a_i-a_j$. Now, if $|f(x)f(1/x)-g(x)-n|> 4\lceil \tfrac{n(n-6)}{19} \rceil$, we will be done if $|x|=1$. Now, let $x=e^{i\theta}$. Observe that \[-g(x)-1=-(2(\sum_{i=1}^{\binom{n}{2}} cos(i\theta)+1)=-\frac{sin(\frac{(n^2-n+1)\theta}{2})}{sin(\frac{\theta}{2})}\]. Also, we have $f(x)f(1/x)=|f(x)|^2$ but it is very hard to say more about $f$ so we just take $\theta$ so that $-g(x)-1-(n-1)$ is positive and thus, we can directly just use $f(x)f(1/x)\ge0$ so let $\frac{(n^2-n+1)\theta}{2}=\frac{3\pi}{2}$. Now, we have $-g(x)-1\ge \frac{1}{\sin(\frac{3\pi}{2(n^2-n+1)})}\ge \frac{2(n^2-n+1)}{3\pi}$. Now, $|f(x)f(1/x)-g(x)-n|>\frac{2(n^2-n+1)}{3\pi}-n+1=\frac{2n^2-(2+3\pi)(n-1)}{3\pi}\ge 4\lceil \tfrac{n(n-6)}{19} \rceil$ and we are done! Amazing problem!!
23.04.2021 16:52
pandadude wrote: Bump. I have never seen any technique like this. Is there somewhere I can learn about this? Additionally, is there any purely combinatorial interpretation? I am still very confused about this. Also, did anyone in China solve this in contest If so how so good First,there is a combinatorial solution.But it only prove lower bound (n^2)/48+O(n) which can get 5 points. Actually,no one get 7 points in the test If you have never seen this technique before,then you read too little,because it just as same as "Perfect Ruler Problem":
Attachments:



16.09.2021 06:59
Mr.Trick wrote: pandadude wrote: Bump. I have never seen any technique like this. Is there somewhere I can learn about this? Additionally, is there any purely combinatorial interpretation? I am still very confused about this. Also, did anyone in China solve this in contest If so how so good First,there is a combinatorial solution.But it only prove lower bound (n^2)/48+O(n) which can get 5 points. Actually,no one get 7 points in the test If you have never seen this technique before,then you read too little,because it just as same as "Perfect Ruler Problem": So how to prove the lower bound in a combinatorial way
07.01.2022 11:38
Which book
20.01.2022 20:41
Can anyone suggest some books for number theory and where to learn these topics
27.01.2022 19:24
Can anyone give me the link of official solutions
06.05.2023 15:39
Donald J. Newman, Analytic Number Theory (Graduate Texts in Mathematics, 177).
28.05.2023 07:52
Almost the exact same as other solutions, but I'll post this anyway because I've never seen this idea before. Consider the function $$f(x) = (x^{a_1} + x^{a_2} + \cdots + x^{a_n})(x^{-a_1} + x^{-a_2} + \cdots + x^{-a_n}) - \sum_{i = -n(n-1)/2}^{n(n-1)/2}x^i - n + 1$$ If $k \neq a_i - a_j$ for any $(i,j)$, is between $1$ and $\frac{n(n-1)}{2})$ then the coefficient of $x^k$ will be exactly $-1$. Otherwise, the coefficient is nonnegative. Next, note that $f(1) = 0$ so the sum of coefficients is exactly zero. Consider $f(\omega)$ for some $\omega$ on the unit circle. Then if the first term is $g(x)$, then the first term of the expression is $|g(\omega)|^2$, and so is nonnegative and real. The $-n+1$ is fixed, so I'll figure out what the middle term is. Its modulus is the modulus of $1 + \omega + \omega^2 + \cdots + \omega^{n^2 - n} = \frac{\omega^{n^2 - n + 1} - 1}{\omega - 1}$ Let $\omega = \cos(z) + i \cdot \sin(z)$ for some $z \in [0,2\pi]$. Note that $|\omega - 1|$ $= \sqrt{(\cos(z) - 1)^2 + \sin(z)^2}$ $= \sqrt{2 - 2 \cos(z)} = 2 \sin(\frac{z}{2})$. So we actually get that the modulus of the expression is C = $\frac{\sin(\frac{z(n^2 - n + 1)}{2})}{\sin(\frac{z}{2})}$. Pick $z(n^2 - n + 1) = 3 \pi$ so the numerator becomes $-1$ and the denominator is $\sin(\frac{z}{2}) < \frac{z}{2} = \frac{3 \pi}{2(n^2 - n + 1))}$. So overall, it becomes $C < \frac{-2(n^2 - n +1)}{3 \pi}$ for some value of $z$. So overall, we get $f(\omega) > \frac{2(n^2 - n + 1)}{3 \pi} - n + 1$. But then again, if there were exactly $2m$ terms with coefficient $-1$ (the $2m$ is because $k$ has coefficient $-1$ if and only if $-k$ does), the sum of the remaining coefficients is also $2m$. So $f(\omega)$ on the other hand is at most $4m$ as $|\omega| = 1$. So we get that numbers that cannot be represented in the form, which equals $m$, is at least $\frac{n^2 - n + 1}{6 \pi} - \frac{n}{4} + \frac{1}{4}$. Using the stunning observation that $6 \pi < 19$, we get that $m > \frac{n^2 - n + 1}{19} - \frac{n-1}{4} > \frac{n(n-6)}{19}$, so there are at least $\lceil \frac{n(n-6)}{19}\rceil$ numbers that cannot be represented, as desired. $\blacksquare$
28.05.2023 08:57
dikugrjfvufytdktfjymtd wrote: Can anyone suggest some books for number theory and where to learn these topics bump?
28.12.2023 07:36
Remark: Why are China TST gen func problems so terrible? Consider the generating function for the sequence given by \[ f(x) = \sum x^{a_i}. \]Define the generating function \[ g(x) = \sum_{-\tbinom{n}{2}}^{\tbinom{n}{2}} x^i. \]Note that the coefficient of $x^i$ in \[ h(x) := f(x)f(x^{-1})-g(x)-(n-1) \]is $-1$ if $i$ has the desired property and nonnegative otherwise. Also, the sum of the coefficients of $h(x)$ is $0$ by plugging in $x=1$. Now select \[ x = \omega = e^{3\pi i/(n^2-n+1)}. \]Realize that under this selection, $g(x)$ vanishes, and $f(x)f(x^{-1})$ is replaced with $|f(\omega)|^2$. Let $d$ denote the number of desired integers. Then we have $|f(\omega)|^2+g(\omega) = h(\omega) \le 4d$. Using some computation and the fact that $\sin(\varepsilon) \le \varepsilon$ for all $\varepsilon>0$, we have that \[ |f(\omega)|^2+g(\omega) \ge \frac{4}{6\pi} \cdot (n^2-n+1) \ge \frac{4}{19} \cdot (n^2-n+1). \]Thus \[ d \ge \frac{n^2-n+1}{19} \ge \left\lceil\frac{n(n-6)}{19}\right\rceil, \]as desired.
25.09.2024 13:15
Here are some interesting Remarks: 1 A very related problem is CTST 2002 which is also posted here by me. Even earlier, GTM 177, Analytic Number Theory by D.J.Newman collected this problem on Chapter 1, which can be found in attached file. Apparently, the GF solution for 2002 TST here(or also found in the book) immediately solves this problem. 2 The proposer of this problem is 王彬, GF is probably not so well-known that time, but in the same year, even same round of examination, he created problem, also GF exercise. After that, nearly all Chinese student are familiar with these skills.
Attachments:
Perfect Ruler.pdf (115kb)