Miklos Schweitzer 1980_1

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

Miklos Schweitzer 1980_1

G H J

Reveal topic tags

college contests

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

2238 posts

#1 h Jan 28, 2009, 4:40 PM • 4 Y

Y by khoa123, Adventure10, Mango247, cubres

For a real number $x$ , let $\|x \|$ denote the distance between $x$ and the closest integer. Let $0 \leq x_n <1 \; (n=1,2,\ldots)\ ,$ and let $\varepsilon >0$ . Show that there exist infinitely many pairs $(n,m)$ of indices such that $n \not= m$ and $\|x_n-x_m \|< \min \left( \varepsilon , \frac{1}{2|n-m|} \right).$

V. T. Sos

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#2 h May 26, 2015, 9:37 AM • 4 Y

Y by oty, adityaguharoy, Adventure10, Mango247

It's enough to prove there exists at least one pair $(n,m)$ and then use the same arguments for $(x_i)\,, j>\max(n,m).$
Fix some $n$ and consider $x_j, j=1,2,\dots, n$ . Let's order them in increasing order $0\leq x_{j_1}<x_{j_2}<\dots <x_{j_n}<1$ .

Now, suppose on the contrary the statement is not true. In particular it implies:
$\|x_{j_s}-x_{j_{s+1}}\| \geq \min \left( \varepsilon , \frac{1}{2|j_s-j_{s+1}|} \right)\,,\,s=1,2,\dots,n \,\,\,\,\,\,\,(1)$
where by $x_{j_{n+1}}$ we mean $x_{j_1}$ .

Clearly $\sum_{s=1}^n \|x_{j_s}-x_{j_{s+1}}\| \leq 1$ and summing up (1) we get:
$1 \geq \sum_{s=1}^n \min \left( \varepsilon , \frac{1}{2|j_s-j_{s+1}|} \right) \,\,\,\,\,\,\, (2)$

The idea is to find an upper bound of $\sum_{s=1}^n |j_s-j_{s+1}|$ , then use $AM-HM$ inequality and get a contradiction.
Fix some interval $[k,k+1]\,,\, k \in \{1,2,\dots,n \}$ and let's see how many intervals $[j_s, j_{s+1}]$ can contain $[k, k+1]$ as a subinterval. Since every point among $1,2,\dots,k$ and $k+1,\dots,n$ can be an end of at most two intervals $[j_s, j_{s+1}]\,,\,s=1,\dots,n$ , it implies $[k,k+1]$ is contained in at most $2\cdot \min(k,n-k)$ such intervals. Therefore:
$\sum_{s=1}^n |j_s-j_{s+1}|\leq 2 \sum_{k=1}^n \min(k,n-k)\leq \frac{n^2}{2} \,\,\,\,\,\,\, (3)$
Consider at first the case when $\frac{1}{2|j_s-j_{s+1}|} \leq \varepsilon\,,\, s=1,2,\dots,n$ . Using (2), (3) and AM-HM yields:
$1 \geq \frac{1}{2}\sum_{s=1}^n \frac{1}{|j_s-j_{s+1}|} \geq 1$
Note that the equality above is only attained when all $|j_s-j_{s+1}|$ are equal. Since it's not possible, we get a contradiction.
Suppose now, $\frac{1}{2 |j_s-j_{s+1}|} > \varepsilon$ for $s\in I$ , where $I$ is some not empty set of indices. Denote $k=|I|$ . Clearly $1\leq k\leq 1/\varepsilon$ . This time we have:
$1 \geq \varepsilon + \frac{1}{2}\cdot \frac{(n-k)^2} {(n^2/2 - k)}$
But $k$ is bounded from above with $1/\varepsilon$ , not depending on $n$ , thus choosing big enough $n$ leads to a contradiction.

This post has been edited 2 times. Last edited by dgrozev, May 26, 2015, 5:01 PM
Reason: typos fixed.

Z K Y

The post below has been deleted. Click to close.

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

VerkhovtsevaKatya

9 posts

VerkhovtsevaKatya

#3 h Jan 17, 2021, 10:36 AM

Y by

dgrozev, you say $[k,k+1]\subseteq [j_s,j_{s+1}]$ , which implies $j_{s+1}\ge k+1$ . Then, how can it be $[k,k+1]\subseteq [j_{s+1},j_{s+2}]$ ? Because

$[j_s,j_{s+1}]\cap[j_{s+1},j_{s+2}]=j_{s+1}$ , not $[k,k+1]$ . If $[k,k+1]\notin\left([j_s,j_{s+1}]\cap[j_{s+1},j_{s+2}]\right),$ how do those intervals contain it?

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#4 h Jan 17, 2021, 11:49 AM

Y by

Sorry, maybe I should have made it clearer. By $[j_s, j_{s+1}]$ I meant the interval which end points are $j_s$ and $j_{s+1}$ . Since $j_1,j_2,\dots,j_n$ is a permutation of $1,2,\dots,n$ of course it may happen $j_{s+1}<j_s.$ So, we want to know how many intervals with endpoints $j_s,j_{s+1}$ contain $[k,k+1]$ as a subinterval.

Z K Y

The post below has been deleted. Click to close.

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

VerkhovtsevaKatya

9 posts

VerkhovtsevaKatya

#5 h Jan 17, 2021, 7:25 PM

Y by

dgrozev, thank you very much for the feedback! May I ask how you came up with the exact expression $1\ge\varepsilon+\dfrac12\cdot\dfrac{(n-k)^2}{\left(\frac{n^2}2-k\right)}$ ?

I see that:

$\lim\limits_{n\to\infty}\dfrac{(n-k)^2}{n^2-2k}=\lim\limits_{n\to\infty}\dfrac{1-\frac{2k}n+\frac{k^2}{n^2}}{1-\frac{2k}{n^2}}=1$ and

$\begin{aligned}\dfrac{(n-k)^2}{n^2-2k}&<0&\forall n<\sqrt{2k}\\0\le\dfrac{(n-k)^2}{n^2-2k}&<1&\forall n\ge k\end{aligned}$

and that we should get $1-\varepsilon<\dfrac{(n-k)^2}{n^2-2k}$ for sufficiently large $n$ , but I couldn't figure out how you came up with that expression.

This post has been edited 2 times. Last edited by VerkhovtsevaKatya, Jan 18, 2021, 9:31 AM
Reason: question clarified

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#6 h Jan 18, 2021, 10:12 AM

Y by

Using $(2)$ we get
$1 \geq \sum_{s=1}^n \min \left( \varepsilon , \frac{1}{2|j_s-j_{s+1}|} \right) = \sum_{s\in I} \varepsilon+\frac{1}{2}\sum_{s\notin I} \frac{1}{|j_s-j_{s+1}|}$ The first term of the RHS is at least $\varepsilon.$ The number of the summands of the second sum is $n-k.$ Further
$\sum_{s\notin I} |j_s-j_{s+1}|\le \frac{n^2}{2}-k$ since $\sum_{s\in I} |j_s-j_{s+1}|\ge \sum_{s\in I} 1 =k.$ Thus applying AM-HM, we get
$\sum_{s\notin I} \frac{1}{|j_s-j_{s+1}|} \ge \frac{(n-k)^2} {(n^2/2 - k)}$ which yields
$\frac{1}{2}\sum_{s=1}^n \frac{1}{|j_s-j_{s+1}|} \ge \frac{1}{2}\cdot \frac{(n-k)^2} {(n^2/2 - k)}.$

This post has been edited 4 times. Last edited by dgrozev, Jan 18, 2021, 6:55 PM
Reason: typos

Z K Y

The post below has been deleted. Click to close.

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

VerkhovtsevaKatya

9 posts

VerkhovtsevaKatya

#7 h Jan 18, 2021, 4:45 PM

Y by

Did you mean 'applying AM-HM' instead of 'GM-HM'?

Thank you for the explanation!

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#8 h Jan 18, 2021, 6:57 PM • 2 Y

Y by Mango247, Mango247

Yes, thanks, edited.

Z K Y

The post below has been deleted. Click to close.

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

1536 posts

#9 h May 8, 2024, 7:07 PM

Y by

Solution. Let us fix $\varepsilon>0$ . We show that if $n$ is large enough, $0 \leq x_i<$ $1(i=1, \ldots, n)$ , then there exists a pair $(i, j)$ of indices such that $\| x_i-$ $x_j \|<\min (\varepsilon, 1 /$ over $2|i-j|)$ . It suffices since it implies that by subdividing the infinite sequence $x_1, x_2, \ldots$ into blocks of $n$ terms, we can find a desired pair of indices in each block and the difference $|i-j|$ does not change if the indices in the block are replaced by the indices in the whole sequence.

Let $f:\{1, \ldots, n\} \rightarrow\{1, \ldots, n\}$ be a permutation such that
$0 \leq x_{f(1)} \leq \cdots \leq x_{f(n)}<1$
We may assume that
$\left\|x_{f(i)}-x_{f(i+1)}\right\|<\min \left(\varepsilon, \frac{1}{2|f(i)-f(i+1)|}\right)$ for $i=1, \ldots, n$ since if it is not the case then we are done. Let $A$ denote the set of the indices $1 \leq i \leq n$ such that $\left\|x_{f(i)}-x_{f(i+1)}\right\| \geq \varepsilon$ . Since the

cyclically taken intervals $\left[x_{f(1)}, x_{f(2)}\right),\left[x_{f(2)}, x_{f(3)}\right), \ldots,\left[x_{f(n)}, x_{f(1)}\right)$ cover the cyclic interval $[0,1)$
$1 \geq \sum_{i=1}^n\left\|x_{f(i)}-x_{f(i+1)}\right\| \geq \sum_{i \in A} \varepsilon+\sum_{i \notin A} \frac{1}{2|f(i)-f(i+1)|},$ and $|A| \leq 1 / \varepsilon$ . That is,
$1-|A| \varepsilon \geq \frac{1}{2} \sum_{i \notin A} \frac{1}{|f(i)-f(i+1)|} .$
Applying the inequality between the arithmetic and harmonic means, we get the inequality
$\sum_{i \notin A}|f(i)-f(i+1)| \geq \frac{(n-|A|)^2}{2(1-|A| \varepsilon)} .$
In the sum $\sum_{i=1}^n|f(i)-f(i+1)|$ , every integer $j \in\{1, \ldots, n\}$ appears exactly twice with positive or negative signs, so that the total sum of the signs is 0 . Obviously, the sum is maximum when the large numbers have coefficient +2 and the small numbers have coefficient -2 . Thus,
$\sum_{i=1}^n|f(i)-f(i+1)| \leq \frac{n^2}{2}$ when $n$ is even, and
$\sum_{i=1}^n|f(i)-f(i+1)| \leq \frac{n^2-1}{2}$ when $n$ is odd. Combining this fact with the preceding inequality, we obtain $1-|A| \varepsilon \geq(1-|A| / n)^2$ , which is a contradiction if $|A| \geq 1$ and $n$ is sufficienly large. If $A=\emptyset$ , then we get $1=1$ , which means that $n$ is even and the numbers $|f(i)-f(i+1)|$ are equal (mean inequality). However, if $f(i)>n / 2$ , then $f(i)$ appears twice with positive sign, that is, $f(i)>f(i-1), \quad f(i)>f(i+1)$ , implying that $f(i-1)=f(i+1)$ , which is possible only if $n \leq 2$ . But it is easy to see that equality cannot hold in this case either, and we got the desired contradiction in all cases.

This post has been edited 4 times. Last edited by Martin.s, Jul 12, 2024, 7:17 AM

Z K Y

The post below has been deleted. Click to close.

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

856 posts

#10 h Oct 29, 2024, 10:54 AM

Y by

Actually $\frac{1}{2|n-m|}$ is easy to achieve. Indeed $\frac{1}{\sqrt 5|n-m|}$ is still correct, but I don't know the proof. A construction taking $x_n=\{\phi^n\}$ where $\phi =\frac{\sqrt 5+1}2$ can show $\sqrt 5$ is the best.

Z K Y

The post below has been deleted. Click to close.

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

2314 posts

oty

#11 h Oct 29, 2024, 1:05 PM

Y by

Any reference for the $\sqrt{5}$ bound.

Z K Y

The post below has been deleted. Click to close.

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

1536 posts

#12 h Nov 14, 2024, 6:47 PM

Y by

Bump this

Z K Y

The post below has been deleted. Click to close.

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

6 posts

Ailyta

#13 h Apr 14, 2025, 4:26 PM

Y by

EthanWYX2009 wrote:

Actually $\frac{1}{2|n-m|}$ is easy to achieve. Indeed $\frac{1}{\sqrt 5|n-m|}$ is still correct, but I don't know the proof. A construction taking $x_n=\{\phi^n\}$ where $\phi =\frac{\sqrt 5+1}2$ can show $\sqrt 5$ is the best.

why $x_n=\{\phi^n\}$ where $\phi =\frac{\sqrt 5+1}2$ can show $\sqrt 5$ is the best? I think $||x_{2k}-x_{2k+2}||=(\frac{\sqrt 5-1}2)^{2k+1}$ .Am I wrong?

This post has been edited 2 times. Last edited by Ailyta, Apr 14, 2025, 4:27 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a