|S|^2 harmonic quadrilaterals?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

|S|^2 harmonic quadrilaterals?

G H J

Reveal topic tags

InfinityDots MO 3

L

G H BBookmark kLocked kLocked NReply

Source: InfinityDots MO 3 P5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

276 posts

talkon

#1 h Apr 10, 2019, 1:21 AM • 7 Y

Y by SAUDITYA, starchan, Adventure10, Mango247, Mango247, Mango247, kiyoras_2001

Is there a nonempty finite set $S$ of points on the plane that form at least $|S|^2$ harmonic quadrilaterals?

Note: a quadrilateral $ABCD$ is harmonic if it is cyclic and $AB\cdot CD = BC\cdot DA$ .

Proposed by talkon

This post has been edited 1 time. Last edited by talkon, Apr 10, 2019, 1:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

250 posts

#2 h Apr 10, 2019, 1:23 AM • 1 Y

Y by Adventure10

wrong
Click to reveal hidden text

This post has been edited 3 times. Last edited by SAUDITYA, Apr 21, 2019, 12:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

894 posts

#3 h Apr 10, 2019, 1:35 AM • 2 Y

Y by Adventure10, Mango247

:whistling:

$\text{[math]}$

This post has been edited 2 times. Last edited by stroller, Apr 20, 2019, 2:26 PM
Reason: Wrong stuff was here

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1594 posts

#4 h Apr 10, 2019, 2:05 AM • 4 Y

Y by talkon, Illuzion, Adventure10, math_comb01

Here is my solution, which gets $cn^2$ for any $c>0$ .

The answer is positive. We claim that if $P_1, P_2,...,P_n$ are $n$ equally spaced points on a line $\ell$ . Then we can invert this configuration around a point $P\notin\ell$ . Then each harmonic quadrilateral corresponds to harmonic bundles among points $1,2,...,n$ . We then restrict attention into counting them.

Call a harmonic bundle primitive if and only if it's in form $(0,c;a,b)$ for some positive integers $a,b,c$ such that $0<a<c<b$ and $\gcd(a,b,c)=1$ . We label each primitive harmonic bundle by $(a,b)$ where $a<b$ . A straight forward computation shows that $(0,c;a,b)$ forms harmonic bundle if and only if $c=\tfrac{a^2+b^2}{a+b}$ .

Claim : If $p$ be an odd prime and $x$ be a positive integer in interval $(0.5p,p)$ . Then $(2x^2-px, px)$ is primitive harmonic bundle.

Proof : First, we observe that $x \in (0.5p,p)$ implies $2x^2-px \in (0, px)$ . Moreover, this implies
$c=\frac{(2x^2-px)^2 + (px)^2}{(2x^2-px)+px} = 2x^2-2px+p^2$ Thus the corresponding harmonic bundle is $(0, 2x^2-2px+p^2 ; 2x^2-px, px)$ . Now it remains to show that $\gcd$ of the components is $1$ . Suppose that there is prime $q$ dividing $2x^2-2px$ , $px$ and $2x^2-2px+p^2$ simultaneously. Clearly $q\ne p$ because then we would have $p\mid x$ , contradiction. Moreover, $q\nmid x$ as it would imply $q\mid 2x^2-2px+p^2\implies q\mid p^2$ or $q=p$ , contradiction again. This implies that $q\mid px$ , contradiction.

Now note that if $(a_1,b_1), (a_2,b_2),...$ be all primitive harmonic bundles. Then $\mathcal{B}=\{b_1,b_2,...\}$ contains all integer $n$ expressible in form $px$ where $x\in (0.5p,p)$ . Since $p > 2\sqrt{n}$ , such integers can be expressed uniquely in that form. Thus
$\begin{align*} \sum_{i=1}^{\infty}\frac{1}{b_i} &\geqslant \sum_{p \text{ odd prime}}\ \sum_{x\in (0.5p,p)}\frac{1}{px} \\ &\geqslant \sum_{p\text{ odd prime}} (0.5p)\cdot \frac{1}{p^2} \\ &= \sum_{p\text{ odd prime}} \frac{1}{2p}\\ \end{align*}$ which diverges. Hence we can pick a collection of primitive harmonic bundles $(x_1, y_1), (x_2, y_2),...,(x_k,y_k)$ such that $\sum_{i=1}^k\frac{1}{y_i} > 2019!$ .

For each $i$ , if $z_i$ is harmonic conjugate of $0$ w.r.t. $x_i, y_i$ . Then tuple $(a, a+bz_i ; a+bx_i, a+by_i)$ forms disjoint harmonic bundles. (Primitive condition ensures us to get the bundles disjoint by scaling.) There are total of
$\sum_{b\leqslant n/y_i} (n-by_i) = \frac{n^2}{y_i} + O(n)$ bundles formed by $(x_i, y_i)$ . Hence by summing the counts for each $i=1,2,...,k$ gives $n^2\left(\tfrac{1}{y_1}+\tfrac{1}{y_2}+...+\tfrac{1}{y_n}\right) + O(n) > 2019!\times n^2 + O(n)$ . Hence the result follows by picking very large $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

894 posts

#5 h Mar 24, 2020, 3:07 PM

Y by

revenge for the fakesolve last year
:cleaning:

:cleaning:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#6 h Apr 7, 2020, 6:26 AM • 1 Y

Y by Illuzion

Yes --- in fact we describe $S$ a subset of the unit circle. By perspectivity from $(0,1)$ to the $x$ -axis, it suffices to find a set $T$ of points on the number line that forms at least $|T|^2$ harmonic bundles.

I claim $T=\{0,1,2,\ldots,n\}$ works for sufficiently large $n$ . It is not hard to check that if $\nu_p(r)=1$ , where $p$ is prime, then $\left(x,x+2ri;x+\left(r+p^2\right)i,x+\left(r+\frac{r^2}{p^2}\right)i\right)=-1.$ Each of these harmonic bundles is uniquely characterized by $(x,r,i)$ , since $\gcd\left(r+p^2,r+r^2/p^2\right)=1$ .

For each $r$ , as $x$ , $i$ vary we have exhibited $\sum_{k\ge1}\max\left(0,n-k\left(r+\frac{r^2}{p^2}\right)\right)\ge\frac n2\left(\frac n{r+\frac{r^2}{p^2}}-1\right)=\frac{n^2}{2\left(r+\frac{r^2}{p^2}\right)}-\frac n2$ harmonic bundles. Let $X(p)=\frac{n^2}2\sum_{\nu_p(r)=1}\max\left(0,\frac1{r+\frac{r^2}{p^2}}-\frac1n\right).$ We have exhibited at least $X(p)$ harmonic bundles for each $p$ .

As $r=ps$ varies, with $s>p$ and $p\nmid s$ , we have
$\begin{align*} \lim_{n\to\infty}\frac{X(p)}{n^2}&=\lim_{n\to\infty}\frac12\sum_{p\nmid s}\max\left(0,\frac1{ps+s^2}-\frac1n\right)\\ &\ge\lim_{n\to\infty}\left[\frac1{2p}\sum_{\substack{p\nmid s\\ s^2\le n}}\left(\frac1s-\frac1{s+p}\right)-\frac{\sqrt n}n\right]\\ &=\frac1{2p}\left(\frac1{p+1}+\cdots+\frac1{2p}\right)\\ &\ge\frac1{2p}\cdot\frac p{2p}=\frac1{4p}. \end{align*}$ There are at least $X(2)+X(3)+X(5)+\cdots$ harmonic bundles in $T$ , but $\lim_{n\to\infty}\frac{X(2)+X(3)+X(5)+\cdots}{n^2}\ge\frac14\left(\frac12+\frac13+\frac15+\cdots\right),$ which diverges. (Note that the $n^{-1/2}$ term in the computation of $\textstyle\lim_{n\to\infty}X(p)/n^2$ may be ignored since there are $O(\ln n)$ of them.) Hence for sufficiently large $n$ , we have $X(2)+X(3)+X(5)+\cdots>n^2$ , and we are done.

This post has been edited 2 times. Last edited by TheUltimate123, Apr 9, 2020, 2:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

206 posts

#7 h May 19, 2020, 11:47 AM • 2 Y

Y by Nathanisme, Mango247

The answer is yes. We pick the set of points $S = \{ (1,0), (2,0), \dots, (n,0)\}$ in Descartes coordinates, and then project these points through $(0,1)$ onto the unit circle. Then it suffices to prove that there are at least $n^2$ harmonic bundles among points in $S$ for sufficiently large $n$ .

Pick a prime number $p$ , and $k>p$ be a positive integer such that $\gcd(p,k)=1$ . Then the bundle $(0,2pk;p(p+k),k(p+k))$ is harmonic, and $\gcd(2pk,p(p+k),k(p+k))=1$ . By scaling and translating we get bundles of the form $(a,a+2pkl; a+p(p+k)l, a+k(p+k)l).$ Notice that we can uniquely recover $a,p,k,l$ from the bundle by the coprime property. First fix $k$ and vary $a$ and $l$ ; we have at least $\sum_{l=1}^{\lfloor n/(kp+k^2)\rfloor} (n-k(p+k)l) > \frac{n}{2}\left(\frac{n}{k(p+k)}-1\right)$ harmonic bundles; summing this over $k$ , we get at least
$H_p = \sum_{k=p+1}^{\lfloor(\sqrt{p^2+4n}-p)/2\rfloor} \left( \frac{n^2}{2k(p+k)}-\frac{n}{2} \right)$ harmonic bundles associated with prime $p$ . We have that when $n\to\infty$ ,
$\frac{H_p}{n^2} = \sum_{k=p+1}^{\lfloor(\sqrt{p^2+4n}-p)/2\rfloor} \left( \frac{1}{2k(p+k)}-\frac{1}{2n} \right) = \frac{1}{2p}\left(\frac{1}{p+1} + \frac{1}{p+2} + \dots + \frac{1}{2p}\right) > \frac{1}{4p}$ So summing this over all primes, the sum diverges. This means $\sum_p H_p > cn^2$ for any $c$ when $n$ is large enough.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

110 posts

#8 h Nov 15, 2020, 1:50 PM

Y by

Firstly we proceed as all the above solutions by considering the axis in which the points $(0,0), (1,0), \ldots, (n,0)$ lies. If we can find some $n$ so that there are $2n^2$ harmonic bundles, inverting on an arbitrary point yields the desired configuration.
Now we identify each harmonic bundle $(A,C;B,D)$ by its distances $(B-A, C-B, D-C)$ . For simplicity we call those triples $(a,b,c)$ . So, a quadruplet of naturals $(A,C;B,D)$ is harmonic if and only if $\dfrac{a}{b} = \dfrac{a+b+c}{c}$ .

Solving for $a$ , we get
$a = \dfrac{b^2+bc}{c-b},\ \text{and}\ a+b+c = \dfrac{b^2+bc}{c-b} + b + c = \dfrac{c(b+c)}{c-b}$ Therefore a harmonic bundle is valid (i.e. $a,b,c \in \mathbb{N}$ ) if and only if given $b,c \in \mathbb{N}$ , $a+b+c = \dfrac{c(b+c)}{c-b} \in \mathbb{N}$ . For each such triplet, we still have one degree of freedom left; we can still slide the value of $A$ across $n - (a+b+c)$ values, yielding that many different quadruplets.
Our next job is to find such pairs of $(b,c)$ . Letting $gcd(b,c) = g$ , and $\dfrac{b}{g} = b'$ . $\dfrac{c}{g} = c'$ , we get
$c'-b' \mid c' \cdot g \cdot (b'+c')$ Since we know that $gcd(b',c') = 1$ , we can infer that the $RHS$ is pretty much "dead" except for $g$ , and that $c'-b' \mid 2g$ . To that we can ignore the $2$ and say that $g = g' \cdot (c-b) = g' \cdot k$ .
Here, we have formulated (to a "constant" where we throw out the $2$ above) all possible solutions, which is $(b,c) = (gb', gc') = (g'kb', g'k(b'+k))$ , with
$a+b+c = \dfrac{c(b+c)}{c-b} = \dfrac{[g'k(b'+k)][g'k(2b'+k)]}{g'k(k)} = g'(b'+k)(2b'+k)$ with $gcd(b',c') = gcd(b',b'+k) = gcd(b',k) = 1$ .
${\color{green}\rule{25cm}{1pt}}$
Now. We. Bash! We intend to calculate the intimidating sum
$\sum_{(b',k) = 1} \text{max}(n - g'(b'+k)(2b'+k),0)$ since we would not like the values $a+b+c$ which exceed $n$ to bother our calculations.
To simplify matters, we let $b'+k = X$ and $2b'+k = Y$ . The gcd condition transforms into $(X,Y) = 1$ and $Y < 2X < 2Y$ . We first count in one variable $t \approx XY$ , then count in $Y$ , before ultimately finishing the problem.
$\textbf{Claim 1.}$ Fix $t$ . When $n > 2t$ ,
$\sum \text{max}(n-g't,0) \geq \dfrac{n^2}{8t}.$ Moreover, the function $f(t) = LHS$ is decreasing.
$\textbf{Proof 1.}$ By direct calculation on $f(t)$ ,
$\begin{align*} f(t) &= (n-t)+(n-2t)+\ldots+(n- \left\lfloor\dfrac{n}{t} \right\rfloor t) \\ &= n \cdot \left\lfloor\dfrac{n}{t} \right\rfloor - t \cdot \dfrac{\left\lfloor\dfrac{n}{t} \right\rfloor \left(\left\lfloor\dfrac{n}{t}+1 \right\rfloor\right)}{2} \\ &= \left\lfloor\dfrac{n}{t} \right\rfloor \left(n - \dfrac{t \cdot \left\lfloor\dfrac{n}{t} \right\rfloor + t}{2}\right)\\ &\geq \left(\dfrac{n}{t} -1 \right) \left( \dfrac{n}{2} - \dfrac{t}{2} \right)\\ &\geq \dfrac{n}{2t} \cdot \dfrac{n}{4} = \dfrac{n^2}{8t} \end{align*}$ as $n - t\left\lfloor\dfrac{n}{t} \right\rfloor \geq 0$ . Also, from the first line we can be sure that $f(t) \geq f(t+1)$ , as the number of terms in $f(t)$ , $\left\lfloor\dfrac{n}{t} \right\rfloor$ , is at least $\left\lfloor\dfrac{n}{t+1} \right\rfloor$ , the number of terms in $f(t+1)$ . Each term $n-t,n-2t,\dots$ in $f(t)$ is also easily seen more than $n-(t+1),n-2(t+1),\dots$ in $f(t+1)$ . Then, the $\textbf{Claim}$ is proven. $\blacksquare$ .
$\textbf{Claim 2.}$ Fix $Y$ . When $n > 2Y^2$ ,
$\sum_{\substack{X\\(X,Y) = 1, Y<2X<2Y}} \text{max}(n-g'XY,0) \geq \dfrac{n^2}{16Y^2} \phi(Y)$ $\textbf{Proof 2.}$ We note that there exists $\dfrac{\phi(Y)}{2}$ possible $X$ . Because $XY < Y^2$ , the expression on the $LHS$ must consist of $\dfrac{\phi(Y)}{2}$ pieces of $f(\text{something lower than} \ Y^2)$ , so it is at least $f(Y^2) \cdot \dfrac{\phi(Y)}{2}$ . $\blacksquare$
${\color{green}\rule{25cm}{3pt}}$
$\textcolor{red}{\textbf{\text{Finishing.}}}$ The initial assertion we're trying to proof is now in the form
$\sum_{i, 2i^2 \leq n} \dfrac{n^2}{16i^2}\phi(i) \geq n^2$ So, if we have proven that $\sum_{i \rightarrow +\infty} \dfrac{\phi(i)}{i^2}$ is unbounded, then we win, by setting a cutoff $c$ so that $\sum_{i=1}^{c} \dfrac{\phi(i)}{i^2} \geq 32$ , and letting $n > 2c^2$ . However, by considering only $i$ primes we get that
$\sum_{i \rightarrow +\infty} \dfrac{\phi(i)}{i^2} \geq \sum_{p \ prime} \dfrac{p-1}{p^2} \geq \sum_{p \ prime}\dfrac{1}{2p} = \dfrac{1}{2} \cdot +\infty$ Then we are done.
Motivation: decide from where (categorizing all bundles) and to where (pesky Claim 1 + Claim 2) to count.
For the sake of completion, here's the (sketch) of proving sum of prime reciprocals is infinite

This post has been edited 8 times. Last edited by alexiaslexia, Nov 15, 2020, 2:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1500 posts

#10 h Apr 4, 2024, 12:30 AM

Y by

Take $N$ points on a circle such that when projected through some point on the circle, they project as $1, 2, \dots, N$ onto a number line.

Claim: $(d, a; b, c) = -1$ has at least $kN^2$ solutions where $a, b, c, d \le N$ and sufficiently large, for any $k$ .
Proof. We first solve when $d = 0$ and $a, b, c$ are relatively prime. This is equivalent to $a = \frac{2bc}{b+c}$ We then must have that $x \mid b, x \mid c$ , and $x^2 \mid b + c$ .
As such, we take $b = x^2 - kx, c = x^2 + kx$ , which gives $a = 2(x-k)(x+k)$ .
We need that $\gcd(x - k, x) = \gcd(x - k, x + k) = 1$ additionally.
By shifting $d$ and scaling, for a fixed $x$ , this gives us at least for some fixed $C$ , $\sum_{(k, x) = 1} \sum_{t \le \frac{N}{Cx^2}} (N - t \cdot Cx^2) = \sum_{(k, x) = 1} N \cdot \frac{N}{Cx^2} = N^2 \cdot \frac{\varphi(x)}{Cx^2} + O(N).$ It remains to show that $\sum \frac{\varphi(x)}{x^2}$ diverges. This follows because for sufficiently large $N$ , we have that $\sum_{x \le N} \frac{\varphi(x)}{x^2} \ge \sum_{x \le N} \frac{1}{(e^{\gamma} + o(1)) x \ln \ln x} \ge \int_{1}^{N} \frac{1}{x\log(x)} dx = \log\log N$ $\blacksquare$
Anyways, we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a