(a): Assume not. Let $S = \left\{ s_1 < \dots < s_n \right\}$. Consider \[ 1 > \frac{s_1}{s_2} > \frac{s_1}{s_3} > \dots > \frac{s_1}{s_n} > t. \]Note that two of the fractions above are within a factor of $t^{1/(n-1)}$ of each other; taking $n$ large enough so that $t^{1/(n-1)} \ge 1-t$ gives the conclusion.

(b): We do it greedily. Let $N$ be a large integer such that $t < 1/2-1/N$. We define $S = \left\{ s_1 < s_2 < \dots \right\}$ inductively as follows. First, let $s_1$ be any prime number exceeding $N$. Then, given $s_1$, ..., $s_k$, we let $s_{k+1}$ equal a prime number which is greater than $2s_k$, and is congruent to $\tfrac{s_i-1}{2} \pmod{s_i}$ for $i = 1, \dots, k$. This is possible by Chinese remainder theorem and Dirichlet. By construction, this works: if $i < j$ then $s_i / s_j < 1/2$ while $s_j / s_i$ has fractional part within $s_i^{-1}$ of $1/2$.

@above, The use of Dirichlet is unnecessary. All you need is that all elements of $S$ are odd and pairwise relatively prime. The proof works perfecly as well. Too easy for P6, in my opinion.

(a): $$t<\frac{s_1}{s_n}=\frac{s_1}{s_2}\frac{s_2}{s_3}...\frac{s_{n-1}}{s_n}<(1-t)^{n-1}$$ false for large n. This is a type of solution that if you see after the contest you would say "wow, how simple that was". But in fact, it is a little difficult to arrive to this.

The part (a) is easy while the part (b) is really nice. Also, I got confused at first, since taking all elements equal in $S$ trolls the problem. So I assume that no two elements in $S$ are equal for part (a). microsoft_office_word wrote: Prove that for every real number $t$ such that $0 < t < \tfrac{1}{2}$ there exists a positive integer $n$ with the following property: for every set $S$ of $n$ positive integers there exist two different elements $x$ and $y$ of $S$, and a non-negative integer $m$ (i.e. $m \ge 0 $), such that \[ |x-my|\leq ty.\] Determine whether for every real number $t$ such that $0 < t < \tfrac{1}{2} $ there exists an infinite set $S$ of positive integers such that \[|x-my| > ty\]for every pair of different elements $x$ and $y$ of $S$ and every positive integer $m$ (i.e. $m > 0$). (a) Let $S=\{a_1, \cdots ,a_n\}$ where $a_i<a_j$ when $i<j.$ Since $a_i \in \mathbb{N},$ hence $a_n \ge a_1+n-1,$ which implies that $\tfrac{a_1}{a_n}$ can get arbitrarily small for large $n.$ So take $m=0,$ and choose a sufficiently large $n$ such that $$\left | \frac{a_1}{a_n}-0 \right| < t$$which is enough to solve the first part. $\square$ (b) The answer is yes. We construct this set recursively. They key observation is that for any $x,y \in S,$ we must have $$1-t > \left \{ \frac{x}{y} \right \} >t \Leftrightarrow 1-t> \frac{x \text{ mod }y}{y} >t$$ Note that $f(x)=\tfrac{\tfrac{x-1}{2}}{x}$ get closer to $\tfrac{1}{2}$ as $x$ increases. So we act greedily and choose a prime $p_1$ such that $1-t>\tfrac{1}{2}>f(p_1)>t.$ So set $p_1$ to be the first element of $S.$ Then, by Dirichlet, we can choose a prime $p_2$ such that $p_2 \equiv \tfrac{p_1-1}{2} \pmod{p_1}$ and $p_2>2p_1.$ Next, choose a prime $p_3$ such that $$\left\{\begin{array}{l} p_3 \equiv \frac{p_1-1}{2} \pmod{p_1}\\p_3 \equiv \frac{p_2-1}{2} \pmod{p_2} \\p_3>2p_2\end{array}\right.$$Such a prime exists by Dirichlet and The Chinese Remainder Theorem. Proceed and construct the primes $p_i$ for all $i \ge 1.$ Then we claim that the infinite set $$S=\{p_1, p_2, p_3, \cdots \} \text{ works.}$$The reason is simple. Firstly, see that for $j>i,$ $0< \tfrac{p_i}{p_j} < \tfrac{1}{2}$ and since $m \ne 0,$ hence this works. Also, if $j>i,$ then $\left \{ \tfrac{p_j}{p_i} \right \}=f(p_i),$ which by assumption lies in $\left( t, \tfrac{1}{2} \right)$ . $\square$ Fun Fact: At first, I misread the problem and solved it. Oh well

Wizard_32 wrote: Also, I got confused at first, since taking all elements equal in $S$ trolls the problem. So I assume that no two elements in $S$ are equal for part (a). FYI, sets don't have multiplicity or repeated elements (what you're thinking of is a multiset). So a "set of $n$ positive integers" necessarily has $n$ distinct elements by definition. (I remember misunderstanding this on an actual contest a long time ago... learned that lesson the hard way.)

v_Enhance wrote: FYI, sets don't have multiplicity or repeated elements (what you're thinking of is a multiset). So a "set of $n$ positive integers" necessarily has $n$ distinct elements by definition. (I remember misunderstanding this on an actual contest a long time ago... learned that lesson the hard way.) Ohh thanks for telling me!

(b) Assume such an infinite set S exists. Consider smallest 2 elements of $S$. Substitute larger as $x$ and smaller as $y$. Now, let $r$ be the remainder when $x$ divided by $y$ i.e $x=ky+r$. Now let $m=k$ gives $r>\tfrac{1}{2}y$. Then, letting $m=k+1$ gives $|r-y|=y-r>\tfrac{1}{2}y$. Together, they imply $r=\frac{1}{2}y$. So $x=ky+\tfrac{1}{2}y$. So $v_2(x)<v_2(y)$. Now take the next largest element of $S$ and let that as $x_2$. Again, it gives $v_2(x_2)<v_2(x)$. This gives $v_2(y)>v_2(x)>v_2(x_2)>...$ eventually it must reach $0$ and cannot reduce any further. So $S$ must be finite.

green_leaf wrote: (b) Assume such an infinite set S exists. Consider smallest 2 elements of $S$. Substitute larger as $x$ and smaller as $y$. Now, let $r$ be the remainder when $x$ divided by $y$ i.e $x=ky+r$. Now let $m=k$ gives $r>\tfrac{1}{2}y$. Then, letting $m=k+1$ gives $|r-y|=y-r>\tfrac{1}{2}y$. Together, they imply $r=\frac{1}{2}y$. So $x=ky+\tfrac{1}{2}y$. So $v_2(x)<v_2(y)$. Now take the next largest element of $S$ and let that as $x_2$. Again, it gives $v_2(x_2)<v_2(x)$. This gives $v_2(y)>v_2(x)>v_2(x_2)>...$ eventually it must reach $0$ and cannot reduce any further. So $S$ must be finite. Except it exists, as showed above...

v_Enhance wrote: (a): Assume not. Let $S = \left\{ s_1 < \dots < s_n \right\}$. Consider \[ 1 > \frac{s_1}{s_2} > \frac{s_1}{s_3} > \dots > \frac{s_1}{s_n} > t. \]Note that two of the fractions above are within a factor of $t^{1/(n-1)}$ of each other; taking $n$ large enough so that $t^{1/(n-1)} \ge 1-t$ gives the conclusion. Wow easy. Motivated from SORY Solution. We assume for the sake of contradiction that there doesn't exist such a natural number $n$ for some $t \in \left ( 0, \frac{1}{2} \right )$. Let $S = \{ a_1, a_2 \dots a_n \}$ such that $a_i > a_j$ if $i > j$. Choose $n$ such that $(1+t)^{n-1} \overset{\text{Bernoulli}}{\geq} 1 + t(n-1) \geq \dfrac{1}{t}$. We see that $a_{j+1} > (1+t)a_j$ must always hold true or else choose $x = a_{j+1}, y = a_j, m = 1$ and get $\lvert a_{j+1} - a_j \rvert \leq ta_j$ as desired. But also see that $\dfrac{a_1}{a_n} > t$ or else choose $x = a_n, m = 0, y = a_1$ for contradiction. But, we see that $a_n \geq (1+t)^{n-1}a_1$ and so choosing $x = a_1, y = a_n, m = 0$ gives that $\lvert a_1 \rvert = a_1 < \dfrac{1}{(1+t)^{n-1}}a_n \leq ta_n$ due to our definition of $n$ in terms of $t$ and this satisfies the given condition. Now for the last part, choose $n$ such that $n > \dfrac{1}{\frac{1}{2} - t}$. Choose $p > n$ such that $p$ is a prime. Suppose we have chosen numbers $a_1 = p, a_2, a_3 \dots a_j$, let $a_{j+1}$ be a prime number exceeding $2a_j$ and is congruent to $\dfrac{a_r-1}{2} \pmod{a_r}$ for $r = 1, 2, 3 \dots j$ and this is consequence of Dirichlet's theorem of infinite primes in AP and CRT. We see that this works due to size issues. (Same as v_enhance solution but posting for storage)

For part (a), let order the elements of $S$ as $a_1 < a_2 < \cdots < a_n$. The problem asks us to find two elements $x,y \in S$ such that $\left\{\frac{x}{y}\right\} \le t$ Suppose the problem is false, and let $k = t + \frac{1}{t}$ then we have $a_{i+1} > ka_i$, so we have $a_n > k^{n-1}a_1$ by iterating this. But now $\frac{a_1}{a_n} < \frac{1}{k^{n-1}} < t$ by taking $n$ sufficiently large. For part (b), start with a big integer $N$ and inductively add elements. Suppose the elements in $S$ so far are $a_1, a_2, \cdots, a_k$. We pick $a_{k+1}$ such that $a_{k+1} \equiv \left \lfloor \frac{a_i}{2} \right \rfloor \pmod{a_i}$ for all $i \in \{1,2,\cdots,k\}$. Further, pick $a_{k+1}$ to be prime by Dirichlet so that the CRT always has solutions. This can easily be seen to work. Done. $\blacksquare$

(a): Write $S = \{s_1 < s_2 < \cdots < s_n \}$ and Assume on the contrary contrary that $$ |x - my| > ty ~~ \forall ~ \text{distinct } x,y \in S $$$m=0,x=s_1,y=s_n$ gives $$ s_1 > ts_n \implies s_n < s_1 \cdot \frac{1}{t} $$But also for any $1 \le k \le n-1$ we have $$ s_{k+1} - s_k = |s_{k+1} - s_k| > ts_k >ts_1 $$Summing all the inequalities gives $$ s_n - s_1 > ts_1 (n-1) \implies s_n >s_1(t(n-1) + 1) $$So we obtain $$ s_1 \cdot \frac{1}{t} > s_n > s_1(t(n-1) + 1) \implies \frac{1}{t} > t(n-1) + 1 $$but this clearly cannot hold for large $n$ (given $t$ fixed), which yields our desired contradiction. $\blacksquare$

a. Let $S=\{a_1< \cdots <a_n \}$. We have \[ t<\frac{s_1}{s_n}= \prod_{k=1}^{n-1}\frac{s_k}{s_{k+1}}<(1-t)^{n-1} \]which fails for $n$ sufficiently large. b. We claim that this is possible. We will construct such a sequence inductively. Indeed, suppose $a_1,a_2, \ldots ,a_N$ all pairwise work. Now, take $a_{N+1}>a_i$ for every $i \leq N$. So, we do not have to care about $\frac{a_i}{a_N}$, we only care about $\frac{a_N}{a_i}$. Notice that $m-t<\frac{a_N}{a_i}<m+t$ iff \[ ta_i < a_{N+1} \text{ mod } a_i<(1-t)a_i \]But we can clearly choose such an $a_{N+1}$ by CRT.

(a) Let $S=\{s_1< \dots <s_n\}.$ Assume the condition is never satisfied. Then choosing $m=0$ we get $$a_1>a_nt\implies a_n<\frac{a_1}{t}.$$Now partition integers from $1$ to $\lfloor \frac{a_1}{t} \rfloor $ in more than $\lceil t^2 \rceil$ subsets, such that each of them has at most $a_1t$ integers. Now choosing $n>>t^2$ we have that two $a_i,a_{i+1}$ fall in the same subset by $PHP$, implying that $a_{i+1}-a_i\leq a_1t,$ a contradiction. (b) We construct $S$ inductively. Assume $S_n=\{s_1< \dots <s_n\}$ works, where $gcd(a_i,a_j)=1$ for any $i,j$. We now choose $s_{n+1}=ka_1\dots a_n +l$ for sufficiently large $k$. We wish to find $l$ such that $l$ does not fall in $[0,\lfloor a_it \rfloor] \cup [\lfloor -a_it \rfloor, a_i-1],$ so just choose $l\equiv \lfloor\frac{a_i}{2}\rfloor$ for all $a_i$ and combine them with CRT. We can do this because all $a_i's$ are coprime by $IH$, and this new $a_{n+1}$ will obvioulsy be coprime.

a) Assume the opposite. Rewrite $|x-my| \leq ty$ as $|\frac{x}{y}-m|<t$. Now let the elements of the set be $s_1<s_2<\ldots<s_n$. We will only consider $\frac{s_i}{s_j}$ with $i<j$. For two consecutives, $\frac{x_i}{x_{i+1}}<1-t$, so $x_{i+1}>x_i*\frac{1}{1-t}$, from which $x_n>x_1*(\frac{1}{1-t})^{n-1}$, so $t<\frac{x_1}{x_n}<(1-t)^{n-1}$, so $n<log_{1-t}(t)+1=A$. Taking $n$ larger than $A$, we get a contradiction, which is the desired b) I claim the answer is yes. Pick any large enough odd number $s_1$. Now we will add numbers to the set inductively. We want following conditions to hold: for any $i \neq j$ $(s_i,s_j)=1$, all terms are odd, for any $i$ $s_{i+1}>\frac{s_i}{1-t}$ and if $j>i$, then $s_j \equiv \frac{s_i-1}{2}$ (mod $s_i$). It is easy to see Let's say we have already added $s_1,s_2,\ldots,s_k$. Then by Chinese Remainder Theorem we can find suitable $s_{k+1}$. Done