Determine if there is a positive integer $n$ such that for any $n$ consecutive positive integers, there is one of them(denote $c$) such that $c$ can be written as sum of consecutive integers(not necessarily all positive) of at most $2020$ distinct ways.
Problem
Source: Brazil Ibero TST 2020 #1
Tags: number theory
28.04.2022 08:24
mathisreal wrote: Determine if there is a positive integer $n$ such that for any $n$ consecutive positive integers, there is one of them(denote $c$) such that $c$ can be written as sum of consecutive integers(not necessarily all positive) of at most $2020$ distinct ways. Claim. The number of way $n$ can be written as sum of consecutive integers is at least $\tau \left( \frac{n}{2^{\nu_2(n)}} \right)$. Proof. Let us suppose that $n = \sum_{i = a}^b i$, where $b > a$ are positive. Then we have \[ 2n = (b - a + 1)(b + a) \]Write $n = 2^{\nu_2(n)} \cdot o(n)$, i.e. $o(n)$ is the odd part of $n$, then we have \[ 2^{\nu_2(n) + 1} \cdot o(n) = (b - a + 1)(b + a) \]First, we claim that as long as $x,y$ are of different parity and positive, then $\{ x, y \} = \{ b - a + 1, b + a \}$ will gives us a unique solution. Indeed, adding both equation, we will have $b = \frac{x + y - 1}{2}$ and therefore $a = \frac{|x - y| + 1}{2}$, which implies $b > a$ are positive as well. Therefore, it suffices to find $x,y$ of different parity such that $2^{\nu_2(n) + 1} \cdot o(n) = xy$. WLOG $x$ is even and $y$ is odd, then we just need to solve $\frac{x}{2^{\nu_2(n)} + 1} \cdot y = o(n)$, and therefore there are $\tau(o(n)) = \tau \left( \frac{n}{2^{\nu_2(n)}} \right)$ ways to do so. Now, suppose there exists such $n$, we claim that we can find a sequence of consecutive integers $x, x + 1, \dots, x + n - 1$ such that \[ \tau \left( \frac{x + i}{2^{\nu_2(x + i)}} \right) > 2020 \]for $0 \le i \le n - 1$. It suffices to use CRT for this: take $x$ such that: \begin{align*} x &\equiv 0 \pmod{3^{2021}} \\ x + 1 &\equiv 0 \pmod{5^{2021}} \\ \vdots \\ x + n - 1 &\equiv 0 \pmod{p_n^{2021}} \end{align*}This would imply that $\tau(o(x + i)) \ge 2021 > 2020$, which implies the result.