Prove that there exists a positive real number $C$ with the following property: for any integer $n\ge 2$ and any subset $X$ of the set $\{1,2,\ldots,n\}$ such that $|X|\ge 2$, there exist $x,y,z,w \in X$(not necessarily distinct) such that \[0<|xy-zw|<C\alpha ^{-4}\] where $\alpha =\frac{|X|}{n}$.
Problem
Source: 2012 China TST Test 2 p2
Tags: pigeonhole principle, floor function, ceiling function, inequalities, function, algebra, difference of squares
19.03.2012 20:14
Seems there has sth to be changed: $\alpha^{-1} = \frac{n}{2} \ge 1$ and $|xy-zw| \in \mathbb{N}$ so at least one and so eahc $C > 1 $ works. Sure $|x|=2$ is correct?
20.03.2012 09:40
There is a typo in problem, $|X|\geq 2$.
10.04.2012 00:41
Nice problem! I think we can strengthen the bound to $\alpha^{-3}=n^3/k^3$ (stronger since $n/k\ge1$)... does the following work? Let $k=|X|$, and go by contradiction (suppose that for every $C$, we can find a counterexample with some $n$ and $X$). First, since $|X\cdot X|\ge k$, we have $n^2/k\ge n^2/|X\cdot X|\ge Cn^3/k^3$ by pigeonhole (since $\max{X\cdot X}\le n^2$), so $k^2\ge Cn$. Now note that if some difference $d>0$ occurs twice, say for $a,a+d$ and $b,b+d$ with $a\ne b$, then $a(b+d)-b(a+d)=d(a-b)$. (This is the key to the nontrivial part of the solution, motivated by extending the difference of squares factorization.) Let $D=\lfloor{5n/k}\rfloor\ge 5n/k-1\ge 4n/k$; if $P$ denotes the number of pairs $\{x,x+d\}$ with $1\le d\le D$ and $x,x+d\in X$ and $t_i=|X\cap (D(i-1),Di]|$ for $1\le i\le \lceil{n/D}\rceil$ (take $C\ge8$ so that $k^2\ge Cn= 8n\ge16\implies k\ge4$, whence $\lceil{n/D}\rceil\le n/D+1\le k/4+1\le k/2$), then by Jensen on $f(x)=x(x-1)/2$ (convex for $x\ge0$), \begin{align*} t_1+\cdots+t_{\lceil{n/D}\rceil} = k\implies P\ge \binom{t_1}{2}+\cdots+\binom{t_{\lceil{n/D}\rceil}}{2} &\ge \lceil{n/D}\rceil\binom{k/\lceil{n/D}\rceil}{2} \\ &= \frac{k}{2}\left(\frac{k}{\lceil{n/D}\rceil}-1\right) \\ &\ge \frac{k}{2}\left(\frac{k}{k/2}-1\right) = \frac{k}{2}. \end{align*}But then $P/D\ge (k/2)/(5n/k)=k^2/(10n)$, so by pigeonhole, there exists $1\le d\le D$ such that there exist $\ell\ge k^2/(10n)$ elements $a_1<\cdots<a_\ell$ with $a_i,a_i+d\in X$ for $1\le i\le \ell$. We can take $C\ge20$ so that $k^2\ge Cn= 20n\implies \ell\ge k^2/(10n)\ge k^2/(20n)+1$. By pigeonhole, there exists $1\le j\le\ell-1$ such that $0<a_{j+1}-a_j\le n/(\ell-1)\le 20n^2/k^2$. But then \[0\ne |a_j(a_{j+1}+d)-a_{j+1}(a_j+d)|=d(a_{j+1}-a_j)\le D\frac{20n^2}{k^2}\le \frac{100n^3}{k^3},\]a contradiction for sufficiently large $C$. Comment: Originally I set $D=\lfloor{5n^2/k^2}\rfloor$ to get the $\alpha^{-4}$ case (we cannot simply set $D=n$; this is too weak due to the scarcity of large differences), but later found this improvement while looking for optimal $X$ (intuitively, it seems like $X=\{d,2d,\ldots,\lfloor{n/d}\rfloor d\}$, which gets $\alpha^{-2}$, should be close to the best). The current method loses a factor of $\alpha$ because for this construction, the only possible differences are multiples of $d$. Any ideas (for either direction)? I think the size of $|X\cdot X|$ may be an important consideration as well, although geometric progressions make the pigeonhole application $n^2/|X\cdot X|$ very weak.
12.04.2012 11:44
My solution is with a similar idea, maybe a little bit easier, though the estimation is $O(\alpha^{-4})$ Let denote $\Delta = C_1 \frac{n^2}{|X|^2}$, where $C_1$ will be determined later. Cover the interval $[0,n]$ with disjoint intervals with length $\Delta$, where the last may be with length $< \Delta$. All of them are at most $\frac{n}{\Delta}+1= \frac{|X|^2}{C_1.n}+1 < \frac{2.|X|^2}{C_1.n}$. There are $|X|$ of our points in them, so by pigeonhole, one of these interval, denote it by $I$, contains at least $\frac{C_1n}{2.|X|}$ points of the set $X$. Consider all midpoints of the segments, which endpoins are in $X \cap I$, i.e. let $M=\{x\,|\, x=\frac{x_1+x_2}{2},\,x_1,x_2\in X \cap I \}.$ We have: $ |M| \geq \frac{C_1n}{2|X|}.(\frac{C_1n}{2|X|}-1)/2 > \frac{C_1^2n^2}{8|X|^2}$. These midpoints are half integers and are in $I$, thus there are at most $2|I|+1<4|I|=4C_1\frac{n^2}{|X|^2}$ different of them. Now it is time to choose $C_1$ big enough so that $\frac{C_1^2}{8} > 4C_1$. Then, by pigeonhole, there will be $x_1,y_1,x_2,y_2 \in X \cap I$ such that $\frac{x_1+y_1}{2}=\frac{x_2+y_2}{2}$. Let now estimate $|x_1y_1-x_2y_2|$. $|x_1y_1-x_2y_2|=|\frac{(x_1-y_1)^2}{4}-\frac{(x_2-y_2)^2}{4} |< 2|I|^2= 2C_1^2.\frac{n^4}{|X|^4}$. Comment. One more natural approach is to estimate how many different elements $X.X$ can have. If all $xy,\, x,y\in X$ are different, then there will be $|X|^2$ different elements in the interval $[0,n^2]$, so in this ideal case the estimation will be $\frac{n^2}{|X|^2}$. But it is too good. I lost a lot of time trying to estimate $|X.X|$ involving some asymptotic properties of the function $\tau(.)$, but without success. In the end I recognised that the wished estimation of $|X.X|$ so that this approach to work, just is not true. Although $|X.X|$ could be too small, this problem points out that there will be different elements of $X.X$, which are close enough.
18.02.2016 18:57
Can someone check this solution? Notice that for a constant $t$, if $|X| < t \sqrt{n}$, then $|xy-zw| < n^2 < n^2 \cdot \left( \frac{n}{|X|^2} \right)^2 \cdot t^4 = t^4 \alpha^{-4}$. Also, if $|X| > \frac{2}{3}(n+1)$, there will be three consecutive numbers in $|X|$, so we can choose $x=y=z+1=w-1$ to get $0<|xy-zw|=1 < 2 \alpha^{-4}$, since $\alpha \le 1$ for any $|X|$. Now let us choose $t=3$ and consider the case $3\sqrt{n} \le |X| \le \frac{2}{3}(n+1)$. Divide $(0, n]$ into $k$ intervals with equal length, i.e. $\left(\frac{nl}{k}, \frac{n(l+1)}{k}\right]$. $k$ will be chosen later. By Pigeonhole Principle, there must be an interval $I$ that has at least $\left\lceil \frac{|X|}{k} \right\rceil$ numbers in it. Let this interval have $s$ positive integers in it. Clearly, $s \le \left\lceil \frac{n}{k} \right\rceil$. Now, what we want to do is find four integers $a,b,c,d \in I \cap X$, we want to have $a+b=c+d$, while $\{a,b\} \not= \{c,d\}$. To do so, we need Pigeonhole Principle again. We basically need $\left\lceil \frac{|X|}{k} \right\rceil^2 \ge 2s$, since there are $2s-1$ possible values for the sum of two integers in $I$. It suffices to have $\left\lceil \frac{|X|}{k} \right\rceil^2 \ge 2\left\lceil \frac{n}{k} \right\rceil$, which motivates us to choose $k = \left\lfloor \frac{|X|^2}{3n} \right\rfloor -1$ (very loose bound) It is clear that $k \ge \frac{|X^2|}{10n}$. (Again, a very loose bound) Now by Pigeonhole Principle, there exists $a,b,c,d \in I \cap X$ such that $a+b=c+d$ and $\{a,b\}\not=\{c,d\}$ It is clear by Vieta's that $ab \not= cd$, which gives $0<|ab-cd|$. We have $$|ab-cd|=|a(c+d-a)-cd|=|(a-c)(a-d)| \le (s-1)^2 < \frac{n^2}{k^2} < \frac{100n^4}{|X|^4} = 100 \alpha^{-4}$$which finishes the problem $\blacksquare$
10.11.2017 05:51
I think this problem is similar to CHN TST 2014 D1P1, but here I can't solve it by the geometric view. Can anyone give me some guidance?
21.08.2020 18:46
Caught my mistake; redacted