N$ and choose $x_n = -n$ for each $n = 1, \dots, N$. Now for each index $1 \le n \le N$, define \[ S(n) = \left\{ \text{indices $i$ for which $f_i(n) \neq 0$} \right\} \subseteq \{1,\dots,k\}. \] As each $S(nt)$ is nonempty, by pigeonhole, two $S(n)$'s coincide, say $S(n) = S(n')$ for $n < n'$. But it's plainly impossible that $x_n > x_{n'}$ in that case due to the essentially increasing condition. \paragraph{Construction} It suffices to do $N = 2^k-1$. Rather than drown the reader in notation, we'll just illustrate an example of the (inductive) construction for $k=4$. Empty cells are zero. \[ \begin{array}{r|rrrr} & f_1 & f_2 & f_3 & f_4 \\ \hline x_1 = 3 & \mathbf{\color{red}3} &&& \\ \hline x_2 = 1 & 10 & \mathbf{\color{red}-9} && \\ x_3 = 4 & & \mathbf{\color{red}4} && \\ \hline x_4 = 1 & 100 & 200 & \mathbf{\color{red}-299} & \\ x_5 = 5 & & 200 & \mathbf{\color{red}-195} & \\ x_6 = 9 & 100 & & \mathbf{\color{red}-91} & \\ x_7 = 2 & & & \mathbf{\color{red}2} & \\ \hline x_8 = 6 & 1000 & 2000 & 4000 & \mathbf{\color{red}-6994} \\ x_{9} = 5 & & 2000 & 4000 & \mathbf{\color{red}-5995} \\ x_{10} = 3 & 1000 & & 4000 & \mathbf{\color{red}-4997} \\ x_{11} = 5 & & & 4000 & \mathbf{\color{red}-3995} \\ x_{12} = 8 & 1000 & 2000 & & \mathbf{\color{red}-2992} \\ x_{13} = 9 & & 2000 & & \mathbf{\color{red}-1991} \\ x_{14} = 7 & 1000 & & & \mathbf{\color{red}-993} \\ x_{15} = 9 & & & & \mathbf{\color{red}9} \end{array} \] The general case is handled in the same way with powers of $10$ replaced by powers of $B$, for a sufficiently large number $B$. \pagebreak \subsection{USAMO 2022/6, proposed by Yannick Yao} \textsl{Available online at \url{https://aops.com/community/p24774626}.} \begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}] There are $2022$ users on a social network called Mathbook, and some of them are Mathbook-friends. (On Mathbook, friendship is always mutual and permanent.) Starting now, Mathbook will only allow a new friendship to be formed between two users if they have at least two friends in common. What is the minimum number of friendships that must already exist so that every user could eventually become friends with every other user? \end{mdframed} With $2022$ replaced by $n$, the answer is $\left\lceil \frac 32 n \right\rceil - 2$. \paragraph{Terminology} Standard graph theory terms: starting from a graph $G$ on $n$ vertices, we're allowed to take any $C_4$ in the graph and complete it to a $K_4$. The problem asks the minimum number of edges needed so that this operation lets us transform $G$ to $K_n$. \paragraph{Construction} For even $n$, start with an edge $ab$, and then create $n/2-1$ copies of $C_4$ that use $ab$ as an edge, as shown below for $n=14$ (six copies of $C_4$). \begin{center} \begin{asy} dotfactor *= 2; pair A = (-1,0); pair B = (1,0); pair X, Y; for (int i=1; i<=6; ++i) { X = (-(i+3)/10, i/7 + 0.4); Y = ((i+3)/10, i/7 + 0.4); dot(X, grey); dot(Y, grey); draw(A--X--Y--B, grey); } draw(A--B, red+2); dot("$a$", A, 2*dir(-90), red); dot("$b$", B, 2*dir(-90), red); \end{asy} \end{center} This can be completed into $K_n$ by first completing the $n/2-1$ $C_4$'s into $K_4$, then connecting red vertices to every grey vertex, and then finishing up. The construction for odd $n$ is the same except with one extra vertex $c$ which is connected to both $a$ and $b$. \paragraph{Bound} Notice that additional operations or connections can never hurt. So we will describe a \emph{specific} algorithm that performs operations on the graph until no more operations are possible. This means that if this algorithm terminates with anything other $G = K_n$, the graph was never completable to $K_n$ to begin with. The algorithm uses the following data: it keeps a list $\mathcal C$ of cliques of $G$, and a labeling $\mathcal{L} \colon E(G) \to \mathcal C$ which assigns to every edge one of the cliques that contains it. \begin{itemize} \ii Initially, $\mathcal C$ consists of one $K_2$ for every edge of $G$, and each edge is labeled in the obvious way. \ii At each step, the algorithm arbitrarily takes any $C_4 = abcd$ whose four edges $ab$, $bc$, $cd$, $da$ do not all have the same label. Consider these labels that appear (at least two, and up to four), and let $V$ be the union of all vertices in any of these 2-4 cliques. \ii Do the following graph operations: connect $ac$ and $bd$, then connect every vertex in $V - \{a,b,c,d\}$ to each of $\{a,b,c,d\}$. Finally, complete this to a clique on $V$. \ii Update $\mathcal C$ by merging these 2-4 cliques into a single clique $K_V$. \ii Update $\mathcal{L}$ by replacing every edge that was labeled with one of these 2-4 cliques with the label $K_V$. Also, update every \emph{newly} created edge to have label $K_V$. However, if there were existing edges not labeled with one of the 2-4 cliques, then we do \emph{not} update these! \ii Stop once every $C_4$ has only one label appearing among its edges. When this occurs, no operations are possible at all on the graph. \end{itemize} A few steps of the process are illustrated below for a graph on six vertices with nine initial edges. There are initially nine $K_2$'s labeled A, B, \dots, I. Original edges are always bolder than added edges. The relabeled edges in each step are highlighted in color. Notice how we need an entirely separate operation to get G to become L, even though no new edges are drawn in the graph. \begin{center} \begin{asy} size(12cm); picture base; dotfactor *= 2; pair P1 = (0,1); pair P2 = (1,1); pair P3 = (2,1); pair P4 = (2,0); pair P5 = (1,0); pair P6 = (0,0); dot(base, "$1$", P1, 2*dir(90)); dot(base, "$2$", P2, 2*dir(90)); dot(base, "$3$", P3, 2*dir(90)); dot(base, "$4$", P4, 2*dir(-90)); dot(base, "$5$", P5, 2*dir(-90)); dot(base, "$6$", P6, 2*dir(-90)); real r = 7; transform t = shift(0,0); draw("A", t*(P6--P1), dir(180), black+2); draw("B", t*(P1--P2), dir(90), black+2); draw("C", t*(P2--P3), dir(90), black+2); draw("D", t*(P3--P4), dir(0), black+2); draw("E", t*(P4--P5), dir(-90), black+2); draw("F", t*(P5--P6), dir(-90), black+2); draw("G", t*(P6--P2), dir(135), black+2); draw("H", t*(P2--P5), dir(180), black+2); draw("I", t*(P5--P3), dir(135), black+2); add(t*base); label("Initial setup", P5, r*dir(270)); t = shift(3,0); draw("J", t*(P6--P1), dir(180), red+2); draw("J", t*(P1--P2), dir(90), red+2); draw("C", t*(P2--P3), dir(90), black+2); draw("D", t*(P3--P4), dir(0), black+2); draw("E", t*(P4--P5), dir(-90), black+2); draw("J", t*(P5--P6), dir(-90), red+2); draw("G", t*(P6--P2), dir(180), black+2); draw("J", t*(P2--P5), dir(180), red+2); draw("I", t*(P5--P3), dir(135), black+2); draw("J", t*(P1--P5), dir(0), red); add(t*base); label(minipage("Step 1: Operate on $1256$. \\ Merges ABFH into J. \\ $\theta(\text{J}) = 4$", 120pt), t*P5, r*dir(270)); t = shift(0,-2.5); draw("K", t*(P6--P1), dir(180), deepgreen+2); draw("K", t*(P1--P2), dir(90), deepgreen+2); draw("K", t*(P2--P3), dir(90), deepgreen+2); draw("D", t*(P3--P4), dir(0), black+2); draw("E", t*(P4--P5), dir(-90), black+2); draw("K", t*(P5--P6), dir(-90), deepgreen+2); draw("G", t*(P6--P2), dir(180), black+2); draw("K", t*(P2--P5), dir(180), deepgreen+2); draw("K", t*(P5--P3), dir(135), deepgreen+2); draw("K", t*(P1--P5), dir(0), deepgreen); draw("K", t*(P6--P3), dir(0), deepgreen); draw("K", t*(P1..(1,1.3)..P3), dir(90), deepgreen); add(t*base); label(minipage("Step 2: Operate on $1235$. \\ Merges CIJ into K. \\ $\theta(\text{K}) = 6$", 120pt), t*P5, r*dir(270)); t = shift(3,-2.5); draw("L", t*(P6--P1), dir(180), blue+2); draw("L", t*(P1--P2), dir(90), blue+2); draw("L", t*(P2--P3), dir(90), blue+2); draw("D", t*(P3--P4), dir(0), black+2); draw("E", t*(P4--P5), dir(-90), black+2); draw("L", t*(P5--P6), dir(-90), blue+2); draw("L", t*(P6--P2), dir(180), blue+2); draw("L", t*(P2--P5), dir(180), blue+2); draw("L", t*(P5--P3), dir(135), blue+2); draw("L", t*(P1--P5), dir(0), blue); draw("L", t*(P6--P3), dir(0), blue); draw("L", t*(P1..(1,1.3)..P3), dir(90), blue); add(t*base); label(minipage("Step 3: Operate on $2356$. \\ Merges GK into L. \\ $\theta(\text{L}) = 7$", 120pt), t*P5, r*dir(270)); \end{asy} \end{center} As we remarked, if the graph is going to be completable to $K_n$ at all, then this algorithm must terminate with $\mathcal C = \{K_n\}$. We will use this to prove our bound. We proceed by induction in the following way. For a clique $K$, let $\theta(K)$ denote the number of edges of the \emph{original} graph $G$ which are labeled by $K$ (this does \emph{not} include new edges added by the algorithm); hence the problem amounts to estimating how small $\theta(K_n)$ can be. We are trying to prove: \begin{claim*} At any point in the operation, if $K$ is a clique in the cover $\mathcal C$, then \[ \theta(K) \ge \frac{3 |K|}{2} - 2. \] where $|K|$ is the number of vertices in $K$. \end{claim*} \begin{proof} By induction on the time step of the algorithm. The base case is clear, because then $K$ is just a single edge of $G$, so $\theta(K) = 1$ and $|K| = 2$. The inductive step is annoying casework based on the how the merge occurred. Let $C_4 = abcd$ be the $4$-cycle operated on. In general, the $\theta$ value of a newly created $K$ is exactly the sum of the $\theta$ values of the merged cliques, by definition. Meanwhile, $|K|$ is the number of vertices in the union of the merged cliques; so it's the sum of the sizes of these cliques minus some error due to overcounting of vertices appearing more than once. To be explicit: \begin{itemize} \ii Suppose we merged four cliques $W$, $X$, $Y$, $Z$. By definition, \begin{align*} \theta(K) &= \theta(W)+\theta(X)+\theta(Y)+\theta(Z) \\ &\ge \frac32(|W|+|X|+|Y|+|Z|) - 8 = \frac32(|W|+|X|+|Y|+|Z|-4) - 2. \end{align*} On the other hand $|K| \le |W|+|X|+|Y|+|Z|-4$; the $-4$ term comes from each of $\{a,b,c,d\}$ being in two (or more) of $\{W,X,Y,Z\}$. So this case is OK. \ii Suppose we merged three cliques $X$, $Y$, $Z$. By definition, \begin{align*} \theta(K) &= \theta(X)+\theta(Y)+\theta(Z) \\ &\ge \frac32(|X|+|Y|+|Z|) - 6 = \frac32\left(|X|+|Y|+|Z|-\frac83\right) - 2. \end{align*} On the other hand, $|K| \le |X|+|Y|+|Z| - 3$, since at least $3$ of $\{a,b,c,d\}$ are repeated among $X$, $Y$, $Z$. Note in this case the desired inequality is actually strict. \ii Suppose we merged two cliques $Y$, $Z$. By definition, \begin{align*} \theta(K) &= \theta(Y)+\theta(Z) \\ &\ge \frac32(|Y|+|Z|) - 4 = \frac32\left(|Y|+|Z|-\frac43\right) - 2. \end{align*} On the other hand, $|K| \le |Y|+|Z| - 2$, since at least $2$ of $\{a,b,c,d\}$ are repeated among $Y$, $Z$. Note in this case the desired inequality is actually strict. \qedhere \end{itemize} \end{proof} \begin{remark*} Several subtle variations of this method do not seem to work. \begin{itemize} \ii It does not seem possible to require the cliques in $\mathcal C$ to be disjoint, which is why it's necessary to introduce a label function $\mathcal L$ as well. \ii It seems you do have to label the newly created edges, even though they do not count towards any $\theta$ value. Otherwise the termination of the algorithm doesn't tell you enough. \ii Despite this, relabeling existing edges, like G in step 1 of the example, 1 seems to cause a lot of issues. The induction becomes convoluted if $\theta(K)$ is not exactly the sum of $\theta$-values of the subparts, while the disappearance of an edge from a clique will also break induction. \end{itemize} \end{remark*} \pagebreak \end{document}