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 τ(n2ν2(n)). Proof. Let us suppose that n=∑bi=ai, where b>a are positive. Then we have 2n=(b−a+1)(b+a)Write n=2ν2(n)⋅o(n), i.e. o(n) is the odd part of n, then we have 2ν2(n)+1⋅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=x+y−12 and therefore a=|x−y|+12, which implies b>a are positive as well. Therefore, it suffices to find x,y of different parity such that 2ν2(n)+1⋅o(n)=xy. WLOG x is even and y is odd, then we just need to solve x2ν2(n)+1⋅y=o(n), and therefore there are τ(o(n))=τ(n2ν2(n)) ways to do so. Now, suppose there exists such n, we claim that we can find a sequence of consecutive integers x,x+1,…,x+n−1 such that τ(x+i2ν2(x+i))>2020for 0≤i≤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.