Mathematica competitions in Croatia

For a given positive integer $n$ let $S_n$ denote the set of all possible values that $x_n$ can obtain for different choices of numbers $a_i$, $1\le i\le n$. For example: $$S_1=\{\frac{1}{2},2\},S_2=\{\frac{1}{3},\frac{2}{3},\frac{3}{2},3\},S_3=\{\frac{1}{4},\frac{2}{5},\frac{3}{5},\frac{3}{4},\frac{4}{3},\frac{5}{3},\frac{5}{2},4\},\dots$$ Note that, for every $x\in S_n$ both $x+1$ and $\frac{1}{x+1}$ belong to $S_{n+1}$. Furthermore, one of those two numbers is smaller than 1 and the other is greater than 1. Thus, each $S_n$ consists of even number of numbers. For a given positive integer $n$ let $$S_n=\{a_1,a_2,\dots ,a_{2m}\},\text{ with }{a}_1<a_2<\cdots <a_{2m}$$ and $$S_{n+1}=\{b_1,b_2,\dots ,b_{2k}\},\text{ with }{b}_1<b_2<\cdots <b_{2k}.$$ The following statements can easily be proved by induction: Claim 1. $m=2^{n-1}$, $k=2^n$ and thus $|S_{n+1}|=2|S_n|$. Claim 2. $a_1=\frac{1}{n+1}$, $a_m=\frac{n}{n+1}$, $a_{m+1}=\frac{n+1}{n}$, $a_{2m}=n+1$. Claim 3. $b_1<b_2<\cdots <b_{2m}<1<b_{2m+1}<\cdots <b_{4m}$. Claim 4. $a_i=\frac{1}{a_{2m+1-i}}$, $b_i=\frac{1}{b_{4m+1-i}}$. Claim 5. $b_i=\frac{1}{1+a_{2m+1-i}}$, for $1\le i\le 2m$. Claim 6. $b_i=\frac{1}{b_{2m+1-i}}$, for $1\le i\le 2m$. Combining Claim 5 and Claim 4 we get: $$b_i=\frac{a_i}{1+a_i},\text{for }1\le i\le 2m.(2)$$ For all integers $n\ge 2$, we will prove that $a_{i+1}-a_i\le \frac{1}{2n-1}$ for all $1\le i\le m$. That is obviously true for $n=2$. As an induction hypothesis, let us assume that this holds for $n$. We will prove that the claim holds for $n+1$, i.e. we will prove that $b_{i+1}-b_i\le \frac{1}{2n+1}$ for all $1\le i\le 2m$. From (2) and Claim 2 we know that $$b_m=\frac{n}{2n+1},b_{m+1}=\frac{n+1}{2n+1}.$$ Therefore, $$b_{m+1}-b_m=\frac{1}{2n+1},$$ thus the claim holds for $i=m$. Let us prove that the claim holds for $i<m$. We have: $$b_{i+1}-b_i=\frac{1}{a_{i+1}+1}-\frac{1}{a_i+1}=\frac{a_{i+1}-a_i}{(1+a_i)(1+a_{i+1})}.$$ By induction hypothesis, $a_{i+1}-a_i\le \frac{1}{2n-1}$ and from Claim 2 we know that $a_i\ge \frac{1}{n+1}$ and $a_{i+1}\ge \frac{1}{n+1}$. Thus, $$b_{i+1}-b_i=\frac{a_{i+1}-a_i}{(1+a_i)(1+a_{i+1})}\le \frac{\frac{1}{2n-1}}{(1+\frac{1}{n+1})(1+\frac{1}{n+1})}<\frac{1}{2n+1},$$ with the last inequality being equivalent to $2n^2-5>0$ which holds for $n\ge 2$. Finally, we will prove that $b_{i+1}-b_i\le \frac{1}{2n+1}$ for $m<i<2m$. From Claim 6 we have: $$b_{i+1}-b_i=\frac{1}{b_j}-\frac{1}{b_{j+1}}=\frac{b_{j+1}-b_j}{(1+b_j)(1+b_{j+1})}<b_{j+1}-b_j<\frac{1}{2n+1}.$$ where we denoted $j=2m-i<m$. For $n=101$, let $S_{101}=\{c_1,c_2,\dots ,c_s\}$, where $c_1<c_2<\cdots <c_s$. Since $c_1=\frac{1}{102}$ and $c_s=\frac{101}{102}$ we know that $c_1-\frac{1}{111}<\frac{1}{201}$ and $\frac{110}{111}-c_s<\frac{1}{201}$. Therefore, in set $S_n^{\prime }=\{c_0,c_1,\dots ,c_s,c_{s+1}\}$ with $c_0=\frac{1}{111}$ and $c_{s+1}=\frac{110}{111}$ the following holds: $$c_{i+1}-c_i\le \frac{1}{201},\text{ for }0<i\le s.$$ For given $x\in [\frac{1}{111},\frac{110}{111}]$, let $j$ be an index such that $c_j\le x\le c_{j+1}$. Since, $c_{j+1}-c_j\le \frac{1}{201}$ we conclude that $|x-c_j|\le \frac{1}{402}$ or $|x-c_{j+1}|\le \frac{1}{402}$.