The answer is $11 = \lceil \log_2(2022) \rceil$. Proof of bound: Take a strictly decreasing sequence $(x_1,\ldots,x_{2022})$ which never hits $0$. Suppose there existed working functions $f_1,\ldots,f_{10}$. Define $v(n) = (f_1(n),\ldots,f_{10}(n))$. Simply consider which of these are zero and which are nonzero in the tuple, and that's a binary string of zero/nonzero. Since there are only $2^{10}<2022$ possible binary strings, by pigeonhole two must repeat. Suppose $v(n_1)$ and $v(n_2)$ have the same zero/nonzero pattern, WLOG $n_1<n_2$. Let $I=\{i \in [1,10]: v(n_1)[i]\not=0\}$. (The set $I$ is non-empty since if it was empty, then $f_i(n_1)=0$ for each $i$, so $x_{n_1}=0$, contradiction to assumption.) For $i\in I$, we have $f_i(n_1)\not = 0$ and $f_i(n_2)\not = 0$, so $f_i(n_1) \le f_i(n_2)$ since $f_i$ is essentially increasing. Now summing, \[ \sum_{i=1}^{10} f_i(n_1)=\sum_{i\in I}f_i(n_1) \le \sum_{i\in I} f_i(n_2) = \sum_{i=1}^{10} f_i(n_2) \implies x_{n_1}\le x_{n_2}. \]But $\vec{x}$ is strictly decreasing and $n_1<n_2$, contradiction. Construction: We will prove a stronger claim which finishes by simply taking the first $2022$ values for $m=11$: For any integer $m\ge 2$, reals $x_1,\ldots,x_{2^m-1}$ are fixed. There exist essentially increasing functions $f_1,\ldots,f_m$ for which $f_1(n)+\cdots+f_m(n)=x_n$ for all $n\in [1,2^m-1]$. We induct on $m$, base case of $m=1$ very easy. The main idea for the induction step is illustrated in the following example for $m=4$: \[ \begin{tabular}{ c|c|c|c|c|c| } $n$&$x_n$&$f_1(n)$&$f_2(n)$&$f_3(n)$&$f_4(n)$ \\ \hline 1 & $x_1$ & ~ & ~ & ~ & 0 \\ \hline 2 & $x_2$ & ~ & ~ & ~& 0 \\ \hline 3 & $x_3$ & ~ & ~ & ~ & 0 \\ \hline 4 & $x_4$ & ~ & ~ & ~& 0 \\ \hline 5 & $x_5$ & ~ & ~ & ~& 0 \\ \hline 6 & $x_6$ & ~ & ~ & ~& 0 \\ \hline 7 & $x_7$ & ~ & ~ & ~& 0 \\ \hline 8 & $x_8$ & $A$ & $2A$ & $4A$ & $-7A+x_8$ \\ \hline 9 & $x_9$ & $0$ & $2A$ & $4A$ & $-6A+x_9$ \\ \hline 10 & $x_{10}$ & $A$ & $0$ & $4A$ & $-5A+x_{10}$ \\ \hline 11 & $x_{11}$ & $0$ & $0$ & $4A$ & $-4A+x_{11}$ \\ \hline 12 & $x_{12}$ & $A$ & $2A$ & $0$ & $-3A+x_{12}$ \\ \hline 13 & $x_{13}$ & $0$ & $2A$ & $0$ & $-2A+x_{13}$ \\ \hline 14 & $x_{14}$ & $A$ & $0$ & $0$ & $-1A+x_{14}$ \\ \hline 15 & $x_{15}$ & $0$ & $0$ & $0$ & $x_{15}$ \\ \hline \end{tabular} \]Fill in the blank table using the same values from the induction for $m-1$. Make the rightmost values in the first half of the table all $0$. Then the sum of these rows is the same. Make $A$ a real number larger than $100$ times the absolute value of all numbers in the inductive table above. Second half of rows: Fill in multiples of $A$ based on the binary representation of $2^m-1-n$ for row $n$. Then make the rightmost value $-(2^m-1-n)A+x_n$. Hence the sum is $x_n$ on row $n$ for each $n$. And it is easy to see that the columns are all essentially increasing -- the last is since $A$ is massive, and the rest are since they are essentially increasing in the first half by induction and then all are $0$ or an insanely large constant value.

Sketch: $n$ max is $2^k-1$. You can prove this by dividing the $x_j$ into $f_k(j)=0$, $f_k(j)\ne 0$, and one freebie caused by $f_k(j)=x_j$, which allows everything else to be 0 and this to be removed. Anyways, first I show $2^k$ doesn't work with $k$ functions. I claim any $x_1>x_2>\cdots>x_{2^k}>0$ works. We induct on $k$, with the base case $k=1$ being clear with $x_1=10, x_2=-1$. Let $y_t=x_t-f_k(t)$ Inductive Step: let $A$ be the set of $t$ such that $f_k(t)=0$. We have $\sum\limits_{j=1}^{k-1} f_j(t)=y_t=x_t$ for all $t\in A$. Since $x_t$ is decreasing as $t$ increases in $a$, $|A|\le 2^{k-1}-1$ by inductive hypothesis. Let $B$ be the set of $t$ such that $f_k(t)\ne 0$. There exists at most one $t$ such that $y_t=0$ because $y_t$ is strictly decreasing. Therefore we are left with at least $2^k-2^{k-1}-1+1=2^{k-1}$ numbers for $k-1$, which doesn't work. Now I show $2^k-1$ works with $k$ functions. We do the iterative algorithm: keep a set of intervals. Initially we have an interval of length $2^k-1$. The idea is to divide and conquer on intervals. For an interval with $2^l-1$ elements, call $a_1, \cdots, a_{2^l-1}$, we make $f_l(a_1)=\cdots=f_l(a_{2^{l-1}-1})=0$, $f_l(a_{2^{l-1}})\le \cdots \le f_l(a_{2^l-2})< -5000C 2^l$ for some sufficiently large $C$. Note $f_l(a_{2^l-1})$ is out of the picture because we can set $f_1(a_{2^l-1})=\cdots=f_{l-1}(a_{2^l-1})=0$ We can guarantee after dividing the interval, into two intervals $L,R$, if $t\in L, u\in R$ then $\sum\limits_{j=1}^{m} f_j(t) < \sum\limits_{j=1}^{m} f_j(u)$ for any $m<l$. Basically, you have $2^{k-l}$ sorted intervals of $2^l-1$ elements at a time and you divide and conquer. In the end, $l=1$ so we have $2^{k-1}-1$ numbers out of the picture (0's) and not out of the picture numbers are monotonically increasing. One function $f_1$ suffices.

Very beautiful problem, probably my favorite on the test. Replace $2022$ with $n$, the answer is $1+\lfloor \log_2 n\rfloor$, so that for $2022$ the answer is $k=11$. To show that $k\ge 1+\lfloor \log_2 n\rfloor$ is required, consider $x_m=-m$ for $1\le m\le n$. Suppose that there exist $\lfloor\log_2 n\rfloor$ essentially increasing functions $f_1,\dots, f_{\lfloor\log_2 n\rfloor}$ satisfying the condition of the problem. For each $1\le m\le n$, let $S_{m}$ be the set of $i$ for which $f_i(m)\not= 0$. Note that there cannot be $m$ such that $S_m=\emptyset$, because then $f_1(m)+\dots+f_{\lfloor\log_2n\rfloor}(m)=0\not=-m$. Thus the $S_i$ are nonempty subsets of $\{1,\dots,\lfloor\log_2n\rfloor\}$. By the pigeonhole principle, there exist distinct $1\le u<v\le n$ such that $S_u=S_v$, since $n>2^{\lfloor\log_2n\rfloor}-1$. This implies that for every $1\le i\le \lfloor\log_2n\rfloor$, $f_i(u)\le f_i(v)$, since they are either both $0$ in which case the inequality is obvious, or both nonzero in which case the inequality follows from the essentially increasing property. Adding these inequalities for all $1\le i\le\lfloor\log_2n\rfloor$ yields that $x_u\le x_v$, in contradiction with the fact that $-u>-v$. Thus at least $1+\lfloor\log_2 n\rfloor$ functions are required. The remainder of the solution is motivated by the construction for $x_m=-m$. Clearly it suffices to provide a construction for $n$ of the form $2^j-1$, for which $1+\lfloor\log_2n\rfloor=j$.

We will show by induction on $j$ that given real numbers $x_1,\dots, x_n$ with $n=2^j-1$, there exist $j$ essentially increasing functions $f_i$ such that $f_1(m)+\dots+f_j(m)=x_m$ for all $1\le m\le n$. The base case of $j=1$ is obviously given by just $f_1(1)=x_1$. Now suppose that we have shown the claim for $n=2^{j-1}-1$, then we will show it for $n=2^j-1$. First, note by the inductive hypothesis that there exist $j-1$ essentially increasing functions $f_1',\dots, f_{j-1}'$ such that, for all $2^{j-1}+1\le m\le 2^j-1$, $f_1'(m)+\dots+f_{j-1}'(m)=x_m$. We now construct our $f_i$ as follows: let $C$ be a very large positive constant. For $1\le i\le j-1$ \[f_i(m)= \begin{cases} f_i'(m)&\text{if $m\ge 2^{j-1}+1$}\\ -C\cdot 2^i&\text{if $1\le m\le 2^{j-1}$ and the $i$th least significant bit of $m-1$ is $1$}\\ 0&\text{otherwise} \end{cases} \]and \[ f_j(m)= \begin{cases} 0& \text{if $2^{j-1}+1\le m\le 2^j-1$}\\ 2C\cdot (m-1) +x_m &\text{if $1\le m\le 2^{j-1}$} \end{cases} \]By inspection we can see that if $C$ is sufficiently large, all of the $f_i$ will be essentially increasing. Then note that \[ f_1(m)+\dots+f_{j-1}(m)= \begin{cases} x_m& 2^{j-1}+1\le m\le 2^j-1\\ -2C\cdot (m-1)&1\le m\le 2^{j-1} \end{cases} \]so adding $f_j$ completes the construction, as desired.

What score should I expect if I proved that at least 11 functions are needed and 12 functions are enough (using a not-as-smart construction)?

The answer is $\textbf{11}$. Proof that $k\geq 11$: Consider a $k\times 2022$ table ($k$ rows and $2022$ columns) with $f_{i}(j)$ written in the cell $(i,j)$ ($i$-th row and $j$-th column). Color the cells with nonzero value black and those with zeros white. $\textbf{Lemma:}$ We can't have two columns be identically coloured. $\textbf{Proof:}$ Let $x_{1}>x_{2}>\cdots >x_{2022}$. Assume that the $a$-th and $b$-th columns ($a<b$) be identically coloured. Then notice that $\forall 1\leq i\leq k$ we have that $f_{i}(a)\leq f_{i}(b)$. Indeed, if $f_{i}(a)=0$, then because of the coloring, $f_{i}(b)=0$ as well and since $f$ is $\textit{essentially increasing}$, then if $f_{i}(a)\neq 0$ and $a<b$ (because the cells have the same colour) $f_{i}(b)\geq f_{i}(a)$. Thus we reach a contradiction: \[x_{b}<x_{a}=\sum\limits_{i=1}^{2022} f_{i}(a)\leq \sum\limits_{i=1}^{2022} f_{i}(b) = x_{b}\]Now, going back to the problem, each column has $k$ cells and each cell can be colored in one of two ways, so there are $2^{k}$ possibilities. Notice that if we take $x_{i}\neq 0$, the possibility of an all-white column vanishes, so in reality there are $2^{k}-1$ possibilities. The Lemma implies that $2022\leq 2^{k}-1$, so $k\geq 11$. Proof that $k=11$ works. Here is a binary coloring for $k=4$ and $n=15$ just to get an idea and visualise things: $ \begin{array}[b]{|c|c|c|c|c|} \hline & f_{1} & f_{2} & f_{3} & f_{4}\\\hline 1 & & & & \bullet \\\hline 2 & & & \bullet & \bullet \\\hline 3 & & & \bullet & \\\hline 4 & & \bullet & \bullet & \bullet \\\hline 5 & & \bullet & & \bullet \\\hline 6 & & \bullet & \bullet & \\\hline 7 & &\bullet& & \\\hline 8 & \bullet & \bullet & \bullet & \bullet \\\hline 9 & \bullet & & \bullet & \bullet \\\hline 10 & \bullet& \bullet & & \bullet \\\hline 11 & \bullet& & & \bullet \\\hline 12 & \bullet & \bullet & \bullet & \\\hline 13 & \bullet& & \bullet & \\\hline 14 & \bullet&\bullet& & \\\hline 15 & \bullet & & & \\\hline \end{array} $ Each column represents a function and each row - a number from $1$ to $15$ (respectively $1$ to $2022$). By ordering the colored squares in the rows as shown, we have fixed the values of the functions in the rows where there's only one black cell. After that, just pick $f_{i}(j)=2^{i}M>>0$ (for completeness, one may choose $M>\sum\limits |x_{i}|$) for $8\leq j\leq 15$ and $2\leq i\leq 4$ (respectively $999\leq j\leq 2022$) and respectively determine $f_{1}(i)$ for $8\leq i\leq 15$ (the $M>>0$ condition implies that $f_{1}$ is $\textit{essentially increasing}$ and so are the other functions going down the value of $i$ as they are constant in the interval $[8,15]$). Now, do the same for $f_{2}$ in the smaller interval, pick another big constant, smaller than $M$, but still big enough to satisfy the condition $f(s)\leq f(t)$. This gives a construction for $k=11$, so we're done ($n=15$ was considered purely for a visualisation of the idea).

When you forget about binary and think the answer is 1012 for some dumb reason

SHZhang wrote: What score should I expect if I proved that at least 11 functions are needed and 12 functions are enough (using a not-as-smart construction)? Depends on what your construction is. Typically, you get points for making progress towards the "right" solution (construction for 11, in this case); you usually don't get points for making progress towards a separate goal (constructing 12) if it doesn't help with the main goal.

Can I get some point if I prove $k=12$ works but $k=11$ doesn't :yaw:

adamov1 wrote: We now construct our $f_i$ as follows: let $C$ be a very large positive constant. For $1\le i\le j-1$ \[f_i(m)= \begin{cases} f_i'(m)&\text{if $m\ge 2^{j-1}+1$}\\ -C\cdot 2^i&\text{if $1\le m\le 2^{j-1}$ and the $i$th least significant bit of $m-1$ is $1$}\\ 0&\text{otherwise} \end{cases} \]and \[ f_j(m)= \begin{cases} 0& \text{if $2^{j-1}+1\le m\le 2^j-1$}\\ 2C\cdot (m-1) +x_m &\text{if $1\le m\le 2^{j-1}$} \end{cases} \]By inspection we can see that if $C$ is sufficiently large, all of the $f_i$ will be essentially increasing. Then note that \[ f_1(m)+\dots+f_{j-1}(m)= \begin{cases} x_m& 2^{j-1}+1\le m\le 2^j-1\\ -2C\cdot (m-1)&1\le m\le 2^{j-1} \end{cases} \]so adding $f_j$ completes the construction, as desired. DANG IT DUDE! I had almost this exact solutoin but couldn't figure out the details in test. I knew something like this would work (

The answer is $\boxed{11}.$ $\emph{Proof of Minimality:}$ Assume $k\le 10,$ and choose a strictly decreasing sequence $x_1,\dots x_{2022}.$ For each $n\in\{1,\dots,2022\},$ let $S_n$ denote the set of all $i$ such that $f_i(n)\neq 0.$ Since $S_n\subseteq\{1,\dots,k\}$ for all $n,$ there are only $2^k\le 1024$ choices for each $S_n.$ Thus, by Pigeonhole, $S_a=S_b$ for some $a<b.$ This means that for all $i,$ one of the following is true: $f_i(a)=f_i(b)=0$ $f_i(a)\ne 0,f_i(b)\ne 0,$ which implies $f_i(a)\le f_i(b).$ Therefore, $$\sum_{i}f_i(a)\le\sum_{i}f_i(b),$$or $x_a\le x_b.$ This contradicts the fact that $\{x_i\}$ is strictly decreasing. $\emph{Construction:}$ Say a sequence is $\emph{doubly decreasing}$ if both the sequence and its first difference sequence are decreasing. We first show that $k=1+\lfloor\log_2(n)+1\rfloor$ suffices if $\{x_i\}$ is doubly decreasing. We induct on $n;$ the base case is clear. Note that $\{x_1,x_3,\dots,\}$ is doubly decreasing, so we can inductively construct $f_i(1),f_i(3),\dots.$ Then, set $f_i(2)=f_i(1),f_i(4)=f_i(3),$ and etc. Finally, define $$f_{k+1}(1)=0,f_{k+1}(1)=x_{1}-x_{2},$$$$f_{k+1}(3)=0,f_{k+1}(4)=x_{3}-x_{4},$$$$\vdots$$Clearly, $f_{k+1}$ is essentially increasing, and the sum condition is satisfied. Now, consider an arbitrary sequence $\{x_i\}.$ Choose $m$ sufficiently large, and create $f_1,\dots,f_k$ for $\{2^m,2^{m-1},\dots,2^{m-n+1}\}.$ Then, increment $f_1$ as follows: $$f_1(1)\to f_1(1)+(x_1-2^m),$$$$f_1(2)\to f_1(2)+(x_2-2^{m-1}),$$$$\vdots$$If $m$ is large enough, then $f_1$ will still be essentially increasing. Moreover, the new sums will be $x_1,\dots,x_n,$ as desired.

Very nice problem! In general with $k$ functions, we can achieve a maximum of upto $2^k - 1$ real numbers $x_i$. The problem is better thought of as trying to sort the $x_i$ into eventually something that is essentially increasing. Consider ignoring $f_k(n)$ and replacing $x_n \rightarrow x_n - f_k(n)$, after doing this $k-1$ times, we want the sequence to be essentially increasing. For the construction, do it inductively, let $C$ be a very large constant. Define $f_k(n)$ to be $C$ for the second to $2^{k-1}$th number, $f(x_1) = x_1$ and define it to be $0$ on all the remaining numbers. For $x_1$, define all the other $f$'s to be $0$ on it so we can ignore it. Now by the inductive hypothesis, we can sort each group into essentially increasing order, and so we can just take $C$ big enough so nothing in the first group is ever going to be bigger than something in the second group. Now, for the bound, consider the "first sort", replacing $x_k \rightarrow x_k - f_k(n)$ and divide $x_i$ into groups $Z$ and $N$ which stand for zero and nonzero respectively. Take the sequence $x_i$ to be a strictly decreasing sequence with all terms nonzero. Note that there can be at most $2^{k-1} - 1$ numbers in $Z$ by the inductive hypothesis since the numbers in $Z$ are still strictly decreasing and none of them zero. Now, there can be at most $2^{k-1}$ numbers in $N$ because it is still strictly decreasing (since $f$ on these values is strictly increasing) and at most one of them can become $0$ and hence ignorable. Therefore, there can be at most $(2^{k-1}-1) + 2^{k-1} = 2^k - 1$ numbers overall, so we're done proving the bound. So for the problem, since $k$ functions can do at most $2^k - 1$, $10$ can only do upto $1023$ and so the minimum value is $k = 11$. $\blacksquare$

Let $0>x_1>\cdots>x_{2022}.$ For each $1\leq n\leq 2022,$ define the set $S_n:=\{i:f_i(n)=0\}\subseteq \{1,2,\ldots,k\}.$ Notice that $\forall i,$ $x_i\neq 0$ so $S_i\neq \{1,2,\ldots,k\}.$ Assume that $2^k\leq 2022.$ Then, by the pigeonhole principle, there exist $a>b$ such that $S_a=S_b:=S.$ Then, note that \[\sum_{i=1}^kf_i(a)=x_a<x_b=\sum_{i=1}^kf_i(b)\implies \sum_{i=1}^kf_i(a)-f_i(b)<0.\]This, however, is a contradiction, because for all $i\in S$ we have $f_i(a)-f_i(b)=0$ and for all $i\in \{1,2,\ldots,k\}\setminus S,$ since $f_i(a)f_i(b)\neq0$ and $a>b$ we have $f_i(a)\leq f_i(b),$ or in other words, $f_i(a)-f_i(b)\geq 0.$ Thus, $2^k>2022.$ The above argument holds for any $n$ instead of $2022.$ In general, the smallest $k_n$ is at least $\lfloor\log_2(n)\rfloor+1.$ We will show that for all $n,$ the minimal $k_n$ is indeed $\lfloor\log_2(n)\rfloor+1,$ which also implies that the answer to our problem is $11.$ Notice that it is actually enough to show that if $t=2^n-1$ then for any $t$ real numbers $x_1,x_2,\ldots,x_t,$ there exist $n$ essentially increasing functions which satisfy the given conditions. We prove the latter via induction: assume the claim holds for $n$. Then, for $n+1$ consider the following construction: We choose a constant $C$. By the induction hypothesis, we can consider $n$ essentially increasing functions $f_1',f_2',\ldots,f_n'$ which satisfy the condition for $(x_2-C,x_3-C,\ldots, x_{2^n}-C).$ Then, let $f_1'',f_2'',\ldots,f_n''$ be $n$ essentially increasing functions that satisfy the condition for $(x_{2^n},x_{2^n+1},\ldots,x_{2^{n+1}-1}).$ Finally, consider $f_1,f_2,\ldots,f_{n+1}$ as such: Let $f_1(1)=x_1,$ for $2\leq i\leq 2^n$ let $f_1(i)=C,$ and for $2^n+1\leq i\leq 2^{n+1}-1$ let $f_1(i)=0.$ For all other $i,$ let $f_i(1)=0$ and for all $1\leq j\leq 2^n-1$ let $f_i(1+j)=f_{i-1}'(j)$ and $f_i(2^n-1+j)=f_{i-1}''(j).$ Notice that by the definition of our functions, for all $i$ we indeed have $f_1(i)+\cdots+f_{n+1}(i)=x_i.$ It only remains to show that for a proper choice of $C,$ all of $f_1,f_2,\ldots,f_{n+1}$ are essentially increasing. If $C\geq x_1$ then $f_1$ is essentially increasing. Now, for $i>1,$ the values of $f_i(1),f_i(2),\ldots,f_i(2^{n+1}-1)$ are, in order \[0,f'_{i-1}(1),f'_{i-1}(2),\ldots,f'_{i-1}(2^{n}-1),f''_{i-1}(1),f''_{i-1}(2),\ldots,f''_{i-1}(2^{n}-1).\]Note that $f'_{i-1}(1),\ldots,f'_{i-1}(2^n-1)$ and $f''_{i-1}(1),\ldots,f''_{i-1}(2^n-1)$ are essentially increasing sequences, so if \[\max_{\neq 0}(f'_{i-1}(1),\ldots,f'_{i-1}(2^n-1))\leq\min_{\neq 0}(f''_{i-1}(1),\ldots,f''_{i-1}(2^n-1)) \qquad (*)\]then $0,f'_{i-1}(1),\ldots,f'_{i-1}(2^{n}-1),f''_{i-1}(1),\ldots,f''_{i-1}(2^{n}-1)$ is an essentially increasing sequence, or in other words $f_i$ is essentially increasing, as desired. The catch, however, is that the RHS in $(*)$ is fixed for all $i,$ but since $f'_1,f'_2,\ldots,f'_n$ satisfy the our condition for $(x_2-C,\ldots,x_{2^n}-C),$ the LHS will always get as small as needed for big enough $C.$ Therefore, for a suitable $C,$ using the inductive hypothesis, we can indeed find $n+1$ essentially increasing functions which satisfy our condition. The base case for $n=1$ is trivial, and the induction holds. The solution is complete. Amazing problem, harder than P3 in my opinion. Gabriel Carroll ORZ

in test solution that i almost finished , slightly different from what people have above Within the sequence $x_1, \ldots , x_{2022}$, define a chunk to be a consecutive nondecreasing subsection. Denote $F(n)$ as the minimum number of functions required for $n$ chunks. Clearly, $F(1) = 1$ under any context since a chunk can always be covered by one function. In general, say we have $x_1, \ldots , x_{k}$ split into $\ell \leq k$ chunks, $C_1, \ldots , C_\ell$ in order from $x_1$ to $x_k$, covered by $F(\ell)$ functions. Choose one function $f$ to be defined as follows: \[f \equiv \begin{cases} x_i & \text{for all $x_i \in C_1$} \\ A >> \max{|x_i|} & \text{for all $x_i \in C_{2m + 2}$}\\ 0 & \text{for all $x_i \in C_{2m + 3}$} \end{cases}\]Then, $C_1$ gets entirely covered (we don't have to worry about it in the other functions, just set values to be $0$), and then each of the adjacent pairs $(C_2 - \{A\}, C_3), (C_4 - \{A\}, C_5), \ldots$ gets combined into one chunk each, possibly with one leftover that does not get combined. Either way, that leaves $\lceil \tfrac{\ell - 1}{2}\rceil$ chunks for the remaining $F(\ell) - 1$ functions to cover. There may be a better way to choose the first function, but that does not matter, because we now have\[F(\ell) \leq 1 + F\left(\left\lceil \frac{\ell - 1}{2}\right\rceil\right).\]Going back to the original problem, note that $2022$ $x_i$'s form at most $2022$ chunks no matter what, so our answer is\begin{align*}\text{min \# functions} = F(2022) &\leq 1 + F(1011)\\ &\leq 2 + F(505)\\ &\leq 3 + F(252)\\ &\leq 4 + F(126)\\ &\leq 5 + F(63)\\ &\leq 6 + F(31)\\ &\leq 7 + F(15)\\ &\leq 8 + F(7)\\ &\leq 9 + F(3)\\ &\leq 10 + F(1)\\ &= 11 \end{align*}hence our answer is $\leq 11$, and the construction for $\lceil \log_2(\ell) \rceil$ can be extrapolated from repeatedly choosing a function of the same form as $f$ as we induct down to a smaller number of chunks. Now to show the answer is $\geq 11$, we simply choose the sequence $x_i$ to be decreasing. Suppose there were $T < 11$ functions; there would be $\leq 1024$ different possible zero configurations across the $2022$ T-tuples $(f_1(n), \ldots , f_T(n))$, so some two of these tuples, say for $n_1 < n_2$, must have the same zero configuration. Then, note that\[x_{n_1} = \sum f_i(n_1) < \sum f_i(n_2) = x_{n_2}\]since $n_1 < n_2$, so each individual comparison $f_i(n_1) \leq f_i(n_2)$ can be made because either they are both $0$, or else $f_i(n_1) < f_i(n_2)$ since $n_1 < n_2$. This is contradictory to our assumption of decreasingness, so $< 11$ functions cannot be sufficient in all cases. Hence, our final answer is $\boxed{11}$, and it can be achieved through the inductive construction described in the first part of the solution.

Nice problem, ok the answer is $k=\lceil \log_2(n+1) \rceil$ . It is at least that much for obvious reasons. If ,say , $(n,n-1,...,1)$ is the sum of $k$ essentially increasing sequences then record for each slot the subset of of the $k$ sequences that have a nonzero number there , due to decreasingness the same subset cannot be recorded $2$ times and the empty subset cannot be recorded, therefore $2^k-1\ge n$. Now consider a random $(2^k-1)$-tuple $(x_1,x_2,...,x_{2^k-1})$ we are going to subtract succesively $k$ essentially increasing sequences to transform it to zero.(note: i use the same letters for different numbers) -In the first step subtract $(x_1,M,0,M,0,...,M,0)$ for $M$ large enough such that the resulting sequence is of the form: $(0,y(1,1)<y(1,2),y(2,1)<y(2,2),...,y(2^{k-1}-1,1)<y(2^{k-1}-1,2))$ -In the second step subtract $(0,y(1,1),y(1,2),M,M,0,0,M,M,0,0,...,M,M,0,0)$ such that the resulting sequence is of the form: $(0,0,0,y(1,1)<y(1,2)<y(1,3)<y(1,4),...,y(2^{k-2}-1,1)<y(2^{k-2}-1,2)<y(2^{k-2}-1,3)<y(2^{k-2}-1,4))$ In general if after the $j$ step the sequence has the form $(0,0,0,...,0,y(1,1)<...<y(1,2^j),...,y(2^{k-j}-1,1)<...<y(2^{k-j}-1,2^j))$ ($2^j-1$ initial $0$'s ) In the $j+1$ step subtract $(0,0,...,0,y(1,1),y(1,2),...,y(1,2^j),M,M,...,M,0,0,...,0,M,M,....,M,...,0,0,...,0)$ alternating blocks of $M$ and $0$ of size $2^j$ so that the resulting sequence has the form $(0,0,0,...,0,y(1,1)<...<y(1,2^{j+1}),...,y(2^{k-j-1}-1,1)<...<y(2^{k-j-1}-1,2^{j+1}))$ After the $k-1$ step the sequence has the form $(0,0,0,...,0,y(1,1)<...<y(1,2^{k-1}))$ which is essentially increasing so we are done.

Claim 1. $k \ge 11$ Choose a monotonically decreasing sequence $\{x_n\}$ such that $x_i \neq 0$ for any $i$.Let $I_m$ be the set of indexes of functions $\{ f_1(m),...,f_k(m) \}$ such that $f_i(k) \neq 0$. Then we have $$ x_m=\sum_{i=1}^k f_i(m) = \sum_{i \in I_m} f_i(m) \le \sum_{i \in I_{m+t}} f_i(m+t)= \sum_{i=1}^k f_i(m+t)=x_{m+t}$$Where $t \in \mathbb{N}$. Which is true if $I_m=I_{m+t}$. Since $I_m$ is depended on number of functions, this motivates us to check number of possible $I_m$, which is $2^{k}$. Hence, if $k>10$, then $2^{k}> 2022$, which means that we can choose some functions that $I_m \neq I_{m+t}$, if $k<11$, we have $2^k<2022$, by pigeonhole principle, for any $I_m$, there is some $t$ such that $I_m=I_{m+t}$, hence $k \ge 11. \ \square$ Now we have to show a construction for $k=11$. By induction we will prove that there exists functions $f_1,f_2,..,f_m$ satisfying the properties in question and $f_1(n)+f_2(n)+...+f_m(n)=x_n$ for all $ 1 \le x_n \le 2^m-1$. We will divide the functions to two sets with $f_1,f_2,...,f_{m-1}$ and $f_m$. Our main idea is we will give the functions $f_1,...,f_{m-1}$ $0$ and non-$0$ values in some intervals such that makes them essentially increasing, and choosing specific $f_m$ such that their sum gives $x_n$ and apply the same construction for the remaining part of $n$ For the base case $m=1$, it is trivially true. Hence by induction hypothesis, assume our claim is true for some $k$, we will show a construction for $ 2^{k-1} \le n \le 2^k-1$, the remaining part will be fulled with our induction. Choose arbitrarly bigger positive real $C$.We will Chooce functions for the first set such that $f_i$ gets values $2^{i-1}C,0$ only( for $2^{k-1} \le n \le 2^k-1$). Change between these values after $2^{i-1}$ times.Starting from $n=2^{k-1}$, our example for $f_3$ is $4C,4C,4C,4C,0,0,0,0,4C,...$ while for $f_1$ is $C,0,C,0,...$. Then we can define $f_m(n)=-C(2^{m}-1-n) + x_n$ ( for the same interval $n$) In the interval $[2^{k-1},2^k-1]$, our functions are clearly essentially increasing and their sum gives $x_n$. For the other part of the $n$, define $f_m=0$, and make similiar construction for $f_1,...,f_{m-1}$, Hence essentially this will end and we will have a construction for $k=11. \ \blacksquare$

The answer is $11$. When 2022 is replaced with arbitrary $N$, the answer is $1 + \lfloor \log_2 N \rfloor$. Define \[ \chi(n, i) := 1 - \textbf{1}_{f_i(n)=0}, \]and label the lattice points $(n, i)$ in $S=[1, 2022] \times [1, k]$ with $\chi(n, i)$. Construction. What we do for each $n=1, \dots, 2022$ is that we make $f_1, f_2, \dots, f_{k-1}$ ``free" so that $f_k$ is fixed. Our construction is inductive, in that we define it in a piecewise fashion on intervals of the form $[2^i, 2^{i+1})$. Let $n$ be in the interval $[2^i, 2^{i+1})$. Choose $C>\sum_{\ell = 1}^{2022} |x_\ell|$. Then we take $f_j(n)/C$ to be power of $2$ corresponding to the $j$th digit from the left in the binary representation of $2^{i+1}-1-n$ when $j \le i$, $\frac{1}{C} \left[x_n - \sum_{j=1}^i f_j(n)\right]$ when $j=i+1$, and $0$ otherwise. The construction can be seen to easily work by induction on $m$, where we consider $n \in [1, 2^m)$ with the base case $m=1$ trivial. Lower bound. Assume for contradiction that $k=10$ works. Suppose that $(x_i)$ is a nonzero, strictly decreasing sequence. Claim: No two columns of $S$ are identical. Proof. Assume for contradiction that two columns $x=r$ and $x=s$ with $r<s$ are identical. Call $m$ cool if $\chi(r, m) = 1$. Then for cool $m$, $f_m(r) \le f_m(s)$, as $f$ is essentially increasing. Thus we globally sum to obtain \[ \sum_{m \in [1, 10]} f_m(r) = \sum_{m \ \text{cool}} f_m(r) \le \sum_{m \ \text{cool}} f_m(s) = \sum_{m \in [1, 10]} f_m(s). \]However, this means that $x_r \le x_s$, a contradiction to the assumption that $(x_i)$ is strictly decreasing. By the claim, there are at most $2^{10}$ columns in $S$, but this is a contradiction since there are $2022$ columns. Thus $k \ge 11$.

OMG 17 MINUTE SOLVE (BOUND) YO. THAT FELT REALLY DARN GOOD. The answer is $11$. Construction is pretty simple and I didn't work out the details: you essentially take a grid of $k$ rows and $2022$ columns where row $i$ and column $j$ represents the value for $f_i(j)$, and then assign zeros so that the set of the zeros' positions in each column is distinct. Then you can form $2021$ systems of equations by subtracting consecutive rows and then assign values (this should work). Actually, since I gave the construction first, the solution should make some sense. Taking the said grid, we define $S_i$ for $1\le i\le 2022$ as the set of $1\le \ell\le k$ such that $f_\ell(i)\neq 0$. If $S_i=S_j$ then taking $x_j<x_i$ is a contradiction. This means $2^k$ (the possible number of $S_i$) is at least $2022$, so $k\ge 11$. Done! ok judging from above sols maybe construction isnt that easy but WTV we GOT THE DUB.

asdf334 wrote: OMG 17 MINUTE SOLVE (BOUND) YO. THAT FELT REALLY DARN GOOD. The answer is $11$. Construction is pretty simple and I didn't work out the details: you essentially take a grid of $k$ rows and $2022$ columns where row $i$ and column $j$ represents the value for $f_i(j)$, and then assign zeros so that the set of the zeros' positions in each column is distinct. Then you can form $2021$ systems of equations by subtracting consecutive rows and then assign values (this should work). Actually, since I gave the construction first, the solution should make some sense. Taking the said grid, we define $S_i$ for $1\le i\le 2022$ as the set of $1\le \ell\le k$ such that $f_\ell(i)\neq 0$. If $S_i=S_j$ then taking $x_j<x_i$ is a contradiction. This means $2^k$ (the possible number of $S_i$) is at least $2022$, so $k\ge 11$. Done! ok judging from above sols maybe construction isnt that easy but WTV we GOT THE DUB. orz rbo took less than a sixth of the time I took

The answer is $k=11$ — this is clearly a minimum, since if $x_1 > \cdots > x_{2022}$, for each $n$, the subset of $f_1 (n), \ldots , f_k (n)$ which equals zero must be distinct. To prove that $11$ functions is always enough, we will show recursively that $k$ functions is enough to represent $2^k-1$ reals $x_1 , \ldots$. When $k=1$, this is obvious — for $k> 1$, here is what we do. First, we set $f_k (n) = 0$ for $n = 1,\ldots, 2^{k-1}-1$. By our inductive hypothesis, we can select the values that $f_1 (n), \ldots, f_{k-1} (n)$ take when $n =1, \ldots, 2^{k-1}-1$. Next, for $n=2^{k-1}, \ldots 2^k-1$, it is possible to choose $f_k (n)$ such that $x_n-f_k(n)$ is an arithmetic sequence of positive integers of the form \[D \left( 2^{k-1}-1 \right), D \left( 2^{k-1}-2 \right), \ldots, D, 0\]for any sufficiently large $D$. If $D$ is sufficiently large, for each $n$, we can fix each of $f_1 (n), \ldots, f_{k-1} (n)$ so that the nonzero functions form the binary representation of $2^k-n-1$.