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)$.

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)$.

This is 2002 China TST It is good to see old problems coming back

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

@mela_20-15 Which technique or topic is this?

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

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$.

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!!

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:

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

Which book

Can anyone suggest some books for number theory and where to learn these topics

Can anyone give me the link of official solutions

Donald J. Newman, Analytic Number Theory (Graduate Texts in Mathematics, 177).

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$

dikugrjfvufytdktfjymtd wrote: Can anyone suggest some books for number theory and where to learn these topics bump?

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.

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)