Let $f:\{1,2,\dots,2019\}\to\{-1,1\}$ be a function, such that for every $k\in\{1,2,\dots,2019\}$, there exists an $\ell\in\{1,2,\dots,2019\}$ such that $$ \sum_{i\in\mathbb{Z}:(\ell-i)(i-k)\geqslant 0} f(i)\leqslant 0. $$Determine the maximum possible value of $$ \sum_{i\in\mathbb{Z}:1\leqslant i\leqslant 2019} f(i). $$
Problem
Source: Turkey National Mathematical Olympiad 2019, Problem 5
Tags: function, algebra, combinatorics
AnSoLiN
24.12.2019 16:14
$1-$ Define $A=\{x:f(x)=1\}$ and $B=\{x:f(x)=-1\}$ with $\lvert A\rvert =a$ and $\lvert B\rvert =b$
$2-$ For $k$ in $B$, $l=k$ simply satisfy
$3-$ For $k$ in $A$, match $k$ with $l$ which provides the smallest $\lvert l-k\rvert$ among ones that satisfy given property.
$4-$ Observe that every matched $l$ is in $B$ (because otherwise another $l$ should had matched with $k$)
$5-$ Observe that every $l$ in $B$ can be matched with at most two different $k$ in $A$
$6-$ As result, $2b\geq a$ and $a+b=2019$, so $a-b\leq 673$
$7-$ An example function \[
f(x) = \left\{\begin{array}{lr}
+1, & \text{for } 1\leq x\leq 673\\
-1, & \text{for } 674\leq x\leq 1346\\
+1, & \text{for } 1347\leq x\leq 2019
\end{array}\right\}
\]
grupyorum
25.12.2019 19:54
To add more details,
673 adjacent blocks of $+-+$.
Each $\ell\in \{k:f(k)=-1\}$ can be matched with at most two guys in $\{k:f(k)=+1\}$: We claim that if $k_1<k_2$ in $\{k:f(k)=+1\}$ both matched with an $\ell \in \{k:f(k)=-1\}$ where $\ell<k_1$ and $\ell>k_2$ we get a contradiction. Indeed, we have $f(\ell)+\cdots+f(k_1)\leqslant 0$, whereas $f(\ell+1)+\cdots+f(k_1)\geqslant 1$ from the minimality, and thus, $f(\ell)+\cdots+f(k_1)=0$ and $f(\ell+1)+\cdots+f(k_1)=1$. Now if this is the case, then $f(\ell+1)+\cdots+f(k_1)=1$ on the one hand. On the other hand, $f(\ell+1)+\cdots+f(k_1)+f(k_1+1)+\cdots+f(k_2)=1$, and thus $f(k_1+1)+\cdots+f(k_2)=0$, thus $k_2$ should have matched with $k_1+1$, as the assignment minimizes the absolute distance. Hence, if an $\ell\in \{k:f(k)=-1\}$ is matched with two guys, it should be in between. But now if $k_1<k_2<k_3$ are all matched with $\ell\in\{k:f(k)=-1\}$, then $\ell$ must be in between $k_1$ and $k_2$, and also $k_2$ and $k_3$, which yields a clear contradiction.
Pathological
30.12.2019 02:49
Here is a proof by strong induction, which proves that with $2019$ replaced by $n$ the answer is at most $\left \lfloor \frac{n}{3} \right \rfloor.$ Using the same construction as above, this would show that the answer is $673.$ For $n = 1, 2, 3$, this is obvious. Suppose this holds for $n < t$. When $n = t$, we consider the smallest $k$ so that $f(1) + f(2) + \cdots + f(2k) = 0.$ Now, consider the smallest $x > 2k$ so that $f(1) + f(2) + \cdots + f(x) = k$. If this $x$ does not exist, then we consider two cases. Case 1. $k \le \frac{t}{3}.$ This means that $f(1) + f(2) + \cdots + f(t) \le k \le \frac{t}{3}$ by "continuity," and so we're done here. Case 2. $k > \frac{t}{3}.$ Then $f(1) + f(2) + \cdots + f(t) \le t - 2k < \frac{t}{3}.$ Otherwise, suppose that this $x$ actually exists. Then it's clear that $x \ge 3k$. We claim that defining $f_1 : \{1, 2, \cdots, t-x\} \rightarrow \{-1, 1\}$ by $f_1(y) = f(y+x)$ for $1 \le y \le t-x$ also satisfies the condition of the problem. From here, we'd have from induction that $\sum f(i) \le \left \lfloor \frac{t-x}{3} \right \rfloor + k \le \left \lfloor \frac{n}{3} \right \rfloor$ as desired. To show this, simply note that $f(1) + f(2) + \cdots + f(x)$ is bigger than $f(1) + f(2) + \cdots + f(z)$ for all $z \le x$, and consequently $f(z) + f(z+1) + \cdots + f(x) \ge 0$ for all $z \le x.$ This easily implies the above claim, and so the induction is complete because we've exhausted all cases. Applying the result of the induction on $n = 2019$, we have that $\sum f(i) \le 673.$ However the construction above also gets $673$, and so the answer is $\boxed{673}.$ $\square$
Counterattacker04
11.04.2022 11:40
It's easy to find and understand the answer is 673 if you paint a S(i)-f(i) function image ，where S(i)=f(1)+f(2)+......+f(i)(i=1,2,...2019).
charme7269
03.09.2023 19:16
A rephrased version of this problem in terms of combinatorial terminology is as follows: Some cells of a $1$ x $2019$ chessboard are marked. For each cell, there exists a group of consecutive cells accepting that cell as an endpoint, in which the number of marked cells is not greater than that of unmarked cells. Find the maximum possible value of the number of marked cells minus the number of unmarked cells.
bin_sherlo
06.07.2024 01:47
Answer is $673$ with example $\underbrace{1,1,...,1}_{673 \ \text{times}},\underbrace{-1,-1,...,-1}_{673 \ \text{times}},\underbrace{1,1,...,1}_{673 \ \text{times}}$ Denote $g(n)=f(1)+...+f(n)$ where $g(0)=0$. We have $|g(n+1)-g(n)|=1$. We will show that $g(2019)\leq 673$. Assume that $g(2019)>673$. Let $d(n)$ be the number of $g(i)=n, \ i\in [1,2019]$. Suppose that $d(k)=1$ where $k\in [1,\text{max}\{g(n)\}]$. Let $g(m)=k$. Hence $g(1),...,g(m-1)\leq k-1$ and $g(m+1),...,g(2019)\geq k+1$. We have $g(m)-g(m-i)>0$ and $g(m+i)-g(m-1)>0$ thus, $f(m)$ doesnot obey the rule.Assume that there exists $d(k)=2$ where $1\leq k\leq 672,$ denote $g(a)=k=g(b)$ where $a<b$. We must have $g(b+1)=g(b)+1$ since $g(2019)>673> k$. If $g(a+1),...,g(b-1)\in [0,k-1]$ then $g(b+1)>g(b+1-i)$ and $g(b)<g(b+i)$ but this gives a contradiction. If $g(a+1),...,g(b-1)\geq k+1$ then $g(a-1)>g(a+1-i)$ and $g(a-2)<g(a-2+i)$ which gives a contradiction again. Hence $d(2),...,d(672)\geq 3$. Since $g(2019)$ is odd, $g(2019)>673$ gives $g(2019)\geq 675$. But then $d(1),d(673),d(674),d(675)\geq 1$ and $d(2),...,d(672)\geq 3$ yields $2019=d(1)+...+d(675)+...\geq 4+3.672=2020$ which is impossible. Thus, $g(2019)\leq 673$ as desired.$\blacksquare$