Given that $a_1, a_2, \ldots,a_{2020}$ are integers, find the maximal number of subsequences $a_i,a_{i+1}, ..., a_j$ ($0<i\leq j<2021$) with with sum $2021$
Problem
Source: Serbia TST 2021, P4
Tags: combinatorics
27.10.2021 04:04
Define $b_i=a_1+a_2+...+a_i$ and $b_0=0$. The question becomes: given integers $b_0=0,b_1,b_2,...,b_{2n}$, find the maximum number, $N$, of pairs $(i,j)$ with $i<j$ and $b_j-b_i=2021$. Call such a pair good. (In the original question $n=1010$.) We claim that the answer is $N=n^2+n$ by induction. The base case $n=1$ is obvious. Suppose it is true for $n=m$. Consider $m+1$. Let $i$ be an index such that $b_i \ne b_{i+1}$ (if it dosent exist, then the $b_i$ are constant, which gives 0). Note that $N$=no. of good pairs over $\{0,1,2,...,i-1,i+2,...,2m\}$+no. of good pairs with one from $\{0,1,2,...,i-1,i+2,...,2m\}$ and one from $\{i,i+1\}$+(if $(i,i+1)$ is a good pair) 1. This is $\le (m-1)^2+(m-1)+(2m-1)+1=m^2+m$. This completes The induction. Construction for the $b_i$: 0,0,...,0,2021,0,0,...,0 @below genius
27.10.2021 12:29
Let $b_i=a_1+\cdot+a_i$ and define $b_0=0$. Consider the graph on $\{0,1,\dots,2020\}$ where $i,j$ are connected if and only if $|b_i-b_j|=2021$. It can be easily proved that the graph contains no odd cycles. Hence the graph is bipartite so the number of edges is at most of the form $x(2021-x)\le 1010\cdot 1011$. Construction: $a_i=0$ for all $i$ except $a_{1011}=2021$.