41st Balkan Mathematical Olympiad

If $k=1$, choose $p_1=3$, $n=2$. If $k=2$, choose $p_1=3$, $p_2=7$, $n=5$. Assume $k\ge 3$. Let $p_1,p_2,\dots ,p_k$ be primes congruent to $3$ modulo $4$. By the Chinese Remainder Theorem choose $n\equiv \frac{p_i+1}{4}(\mathrm{mod}{p}_i)$ for every $i$, that is, choose an integer $n$ such that $p_1{p}_2\cdots p_k\mid 4n-1$. Consider a fractional part $\theta =\frac{n}{q_1{q}_2\cdots q_r}$, where $q_1,q_2,\dots ,q_r$ are different primes among $p_1,p_2,\dots ,p_k$. Note that $\theta \approx \frac{1}{4}$ if $r$ is odd and $\theta \approx \frac{3}{4}$ if $r$ is even. If $r$ is odd, then working modulo $4$, we get $4n-1=q_1{q}_2\cdots q_r\cdot (4m+1)$, for some integer $m$. It follows that $$\frac{n}{q_1{q}_2\cdots q_r}=m+\frac{1}{4}+\frac{1}{4q_1{q}_2\cdots q_r}\text{and}\left\{\frac{n}{q_1{q}_2\cdots q_r}\right\}=\frac{1}{4}+\frac{1}{4q_1{q}_2\cdots q_r}.$$ If $r$ is even, then $4n-1=q_1{q}_2\cdots q_r\cdot (4m+3)$, for some integer $m$. Hence $$\frac{n}{q_1{q}_2\cdots q_r}=m+\frac{3}{4}+\frac{1}{4q_1\cdots q_r}\text{and}\left\{\frac{n}{q_1{q}_2\cdots q_r}\right\}=\frac{3}{4}+\frac{1}{4q_1{q}_2\cdots q_r}.$$ The difference between $n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_k}\right)$ and $A(n)$ equals to $$\begin{array}{rl}& \{n\}-\sum _{i=1}^k\left\{\frac{n}{p_i}\right\}+\sum _{1\le i<j\le k}\left\{\frac{n}{p_i{p}_j}\right\}-\cdots +(-1{)}^k\left\{\frac{n}{p_1{p}_2\cdots p_k}\right\}\\ & =-\sum _{i=1}^k\frac{1}{4}+\sum _{1\le i<j\le k}\frac{3}{4}-\cdots -\sum _{i=1}^k\frac{1}{4p_i}+\sum _{1\le i<j\le k}\frac{1}{4p_i{p}_j}-\cdots +(-1{)}^k\frac{1}{4p_1{p}_2\cdots p_k}\\ & =\frac{3}{4}\cdot 2^{k-1}-\frac{1}{4}\cdot 2^{k-1}+\frac{1}{4}\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)-1\\ & =2^{k-2}+\frac{1}{4}\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)-1\\ & >2^{k-3},\end{array}$$ for $k\ge 3$, as desired.

---

Alternative solution.

Alternative Solution. Note that $$A(n)=n-\sum _{i=1}^k\lfloor \frac{n}{p_i}\rfloor +\sum _{1\le i<j\le k}\lfloor \frac{n}{p_i{p}_j}\rfloor -\cdots +(-1{)}^k\lfloor \frac{n}{p_1{p}_2\cdots p_k}\rfloor .$$ Denote by ${\Pi }_k=(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$ and $f_k(n)=n{\Pi }_k-A(n)$, then $$f_k(n)=\{n\}-\sum _{i=1}^k\left\{\frac{n}{p_i}\right\}+\sum _{1\le i<j\le k}\left\{\frac{n}{p_i{p}_j}\right\}-\cdots +(-1{)}^k\left\{\frac{n}{p_1{p}_2\cdots p_k}\right\}.$$ In particular, the function $f_k(n)$ satisfies $$f(n)-f(n-1)=\{\begin{array}{ll}{\Pi }_k-1,& \text{if }\gcd (n,p_1{p}_2\cdots p_k)=1;\\ {\Pi }_k,& \text{if }\gcd (n,p_1{p}_2\cdots p_k)>1.\end{array}$$ We consider the function $f_k(x)$ over the real numbers. Note that $f_k(x)$ is periodic: $f_k(x+p_1{p}_2\cdots p_k)=f_k(x)$. Also, it satisfies $f_k(x)=-f_k(p_1{p}_2\cdots p_k-x)$ for all $x$ except integer points of discontinuity. For example, the graph of $f(x)=\{x\}-\{\frac{x}{3}\}-\{\frac{x}{7}\}+\{\frac{x}{21}\}$ looks as follows: We prove by induction, for $k\ge 2$, that we can find primes $p_1,\dots ,p_k$ such that a slightly stronger inequality holds: $\max |f_k(n)|>2^{k-3}+{\Pi }_k$. The base case: if $k=2$ then choose $p_1=3,p_2=7$. We have $\max |f_2(n)|=|f_2(5)|$ and $$|f_2(5)|=\left|\{5\}-\left\{\frac{5}{3}\right\}-\left\{\frac{5}{7}\right\}+\left\{\frac{5}{21}\right\}\right|=\frac{8}{7}>\frac{1}{2}+\left(1-\frac{1}{3}\right)\left(1-\frac{1}{7}\right).$$ Given primes $p_1,\dots ,p_k$, suppose $-m_k\le f_k(n)\le M_k$, where $-m_k$ and $M_k$ are the minimum and maximum values that $f_k(n)$, $n\in \mathbb{Z}$, can achieve. We can see that $\sup f_k(n)=m_k$ and $m_k=M_k+{\Pi }_k$ because of the discontinuity at the supremum integer point. Suppose we can find primes $p_1,p_2,\dots ,p_k$ such that $\max |f_k(n)|>2^{k-3}+{\Pi }_k$. We show how to find a prime $p_{k+1}$ such that $\max |f_{k+1}(n)|>2^{k-3}+{\Pi }_{k+1}$. Let $\{a_1,a_2,\dots ,a_k\}$ and $\{b_1,b_2,\dots ,b_k\}$ be the two sets of residues modulo $p_1,p_2,\dots ,p_k$, respectively, which identify two integers for which minimum and maximum of $f_k(n)$ occurs. Note that $a_i\ne 0$ for all $1\le i\le k$ because the minimum value occurs at a point of discontinuity, at an integer coprime with $p_1{p}_2\cdots p_k$. Suppose we add a prime $p_{k+1}$, then $f_{k+1}(n)=f_k(n)-f_k(\frac{n}{p_{k+1}})$. Set $n=m{p}_{k+1}+r$, where $m$ is an integer and $0\le r\le p_{k+1}-1$. Since $\frac{r}{p_{k+1}}<1$, we get $$\begin{array}{rl}{f}_{k+1}(n)& =f_k(n)-f_k\left(\frac{n}{p_{k+1}}\right)\\ & =f_k(n)-f_k(m)-f_k\left(\frac{r}{p_{k+1}}\right)\\ & =f_k(n)-f_k(m)-\frac{r}{p_{k+1}}\cdot {\Pi }_k\\ & \ge f_k(n)-f_k(m)-{\Pi }_{k+1}.\end{array}$$ Pick an integer $r\not\equiv b_i(\mathrm{mod}{p}_i)$, where $1\le i\le k$. By Dirichlet's Theorem there exist infinitely many primes $p_{k+1}$ such that $p_{k+1}\equiv (b_i-r)\cdot a_i^{-1}(\mathrm{mod}{p}_i)$ for all $1\le i\le k$, which satisfy $n=m{p}_{k+1}+r$, where $m\equiv a_i(\mathrm{mod}{p}_i)$ and $n\equiv b_i(\mathrm{mod}{p}_i)$. Therefore we can find a prime $p_{k+1}>r$ satisfying the given conditions and $M_{k+1}\ge M_k+m_k-{\Pi }_{k+1}$. Using induction hypothesis we conclude that $$m_{k+1}=M_{k+1}+{\Pi }_{k+1}\ge M_k+m_k=2m_k-{\Pi }_k>2(2^{k-3}+{\Pi }_k)-{\Pi }_k>2^{k-2}+{\Pi }_{k+1}.$$

---

Alternative solution.

Alternative Solution. The most obvious approach appears to be induction on $k$. Let's see if we can make that work. Step 1. Say $n$ and $p_1,p_2,\dots ,p_k$ work. We are going to keep these primes and add one new prime $q$ to them. We'll set things up so that $q$ is much larger than $p_1,p_2,\dots ,p_k$. We will select some new positive integer $N$ to go with $p_1,p_2,\dots ,p_k,q$. Let $P=p_1{p}_2\cdots p_k$. We decree right from the start that $N$ is congruent to $n$ modulo $P$. So $N=KP+n$ for some positive integer $K$. This way, we get to keep all fractional parts from the induction hypothesis. Also, we want all of $p_1,p_2,\dots ,p_k$ to be odd, and we want none of $p_1,p_2,\dots ,p_k$ to divide $n$. Consider this part of the induction hypothesis. We require that $Pq$ divides $nq+N+C$. Let's see how to ensure that. Since $P$ and $q$ are relatively prime, this is the same as $P$ divides $nq+n+C$ and $q$ divides $N+C$. The requirement that $P$ divides $nq+n+C$ gives us $q$ congruent to $1(\mathrm{mod}P)$. By Dirichlet, there are infinitely many primes $q$ with this property. (Note that this special case of Dirichlet has a known proof accessible to high-schoolers, unlike, to the best of my knowledge, the general case.) So we set $q$ to some crazy large prime in this arithmetic progression. We'll see how large later on. Once we've fixed $q$, we moreover have to ensure that $q$ divides $N+C=KP+n+C$. Since $q$ and $P$ are relatively prime, we can choose $K$ such that this holds. To recap, $q$ is absolutely enormous and $Pq$ divides $nq+N+C$. Step 3. Let $P^{\prime }$ be any product of several (possibly zero) distinct primes out of $p_1,p_2,\dots ,p_k$. So $P^{\prime }$ is any divisor of $P$. Then $\{n/P^{\prime }\}$ is a summand in our induction hypothesis and $\{N/P^{\prime }q\}$ is a summand in what we hope will eventually amount to our induction step. Consider $n/P^{\prime }+N/P^{\prime }q$. This is $(nq+N)/P^{\prime }q$. By Step 2, we have that $P^{\prime }q$ divides $nq+N+C$. Also, remember that $q$ is really insanely large. So $(nq+N)/P^{\prime }q$ is $C/P^{\prime }q$ below the nearest larger positive integer. Here, $C/P^{\prime }q$ is at most $C/q$. So by making $q$ absurdly large we can guarantee that $n/P^{\prime }+N/P^{\prime }q$ is arbitrarily close to a positive integer, from below, for all $P^{\prime }$. In particular, we can make it so close to a positive integer that its fractional part is larger than the fractional parts of all expressions of the form $n/P^{\prime }$. Then it follows immediately that, for each expression of the form $n/P^{\prime }$, we have that $\{N/P^{\prime }q\}$ is arbitrarily close to $1-\{n/P^{\prime }\}$. Step 4. Let $S$ be the sum of the fractional parts for $p_1,p_2,\dots ,p_k$ and $n$; that is, $$\{n\}-\sum \{n/p_i\}+\sum \{n/p_i{p}_j\}-\dots ,$$ and so on. By the induction hypothesis, we know $|S|>2^{k-3}$. Let $T$ be the analogous sum for $p_1,p_2,\dots ,p_k,q$ and $N$. Since $N$ is congruent to $n$ modulo $P$, we have that $T$ contains all terms from $S$. The new terms are all things of the form $e\{N/P^{\prime }q\}$, where $e=\pm 1$. We know that each such thingie is very close to $e(1-\{n/P^{\prime }\})=e+(-e)\{n/P^{\prime }\}$. Here, $(-e)\{n/P^{\prime }\}$ is a term which appears in $S$ as well, with this sign exactly. So $T$ is really very close to $2S$ plus the sum of all the $e$'s. The sum of all the e's, on the other hand, is just the alternating sum of the binomial coefficients in row k of Pascal's triangle; so, zero. Therefore, T is very close to $2S$. By making q sufficiently large, we can make “very close” amount to as close as we wish. Since $|S|>2^{k-3}$ by the induction hypothesis, when $T$ is sufficiently close to $2S$, we get $|T|>2^{(k+1)-3}$, as needed. The induction step is complete. Step 5. We still have to take care of the base case. It looks like $k=1$, $p_1=3$, and $n=1$ works with $|S|=1/3>1/4$. $\square$