Lucy starts by writing $s$ integer-valued $2022$-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples $\mathbf{v}=(v_1,\ldots,v_{2022})$ and $\mathbf{w}=(w_1,\ldots,w_{2022})$ that she has already written, and apply one of the following operations to obtain a new tuple: \begin{align*} \mathbf{v}+\mathbf{w}&=(v_1+w_1,\ldots,v_{2022}+w_{2022}) \\ \mathbf{v} \lor \mathbf{w}&=(\max(v_1,w_1),\ldots,\max(v_{2022},w_{2022})) \end{align*}and then write this tuple on the blackboard. It turns out that, in this way, Lucy can write any integer-valued $2022$-tuple on the blackboard after finitely many steps. What is the smallest possible number $s$ of tuples that she initially wrote?
Problem
Source: ISL 2022 C7
Tags: combinatorics
09.07.2023 14:25
09.07.2023 14:46
Same as cbk's.Sorry to my low level of LaTeX, I can't post more details to show my ideas.
13.07.2023 07:16
Nobody solved this problem when it came in INDIA TST 2023(D2P3). One guy claimed it was 3 but gave a false construction $$1,2,3,\cdots , 2021, 2022$$and $$1,-2,3,-4,5,\cdots...,-2020,2021,-2022$$ The correct construction is $$1, -4, 9, -16, 25, \cdots , -2020^2, 2021^2, -2022^2$$and $$1, 4, 9, 16, \cdots, 2020^2, 2021^2, 2022^2$$
20.07.2023 13:04
The answer is $s=3$. The construction is $(1,1,\ldots,1)$, $(-1^2-C,-2^2-C,\ldots,-2023^2-C)$, and $(-2023^2-C,-2022^2-C,\ldots,-1^2-C)$. The bound uses the fact that $a_1u_1+a_2u_2+\ldots+a_{2023}u_{2023}\geq0$ if at most one $a_i$ is negative and the statement is true for the two starting tuples.
18.08.2023 09:54
Ok, I'll admit I got spoiled tragically. $:'($ Unbelievable $n = 3$ is the spoiler. Construction is: $$\langle -1, -1, -1, \ldots, -1 \rangle$$ $$\langle 2, 4, 6, \ldots, 2 \cdot 2022 \rangle$$ $$\langle 10^{100}, 10^{100} - 1^2, 10^{100}-2^2, \ldots, 10^{100} - 2021^2 \rangle$$ The rest of the proof is left to the reader, essentially you just show each coordinate can be the strictly maximal coordinate of an entirely positive vector, then apply $-1$ until it is the only positive coordinate and equal to $1$, then apply the maximum function to transform it into an effective indicator function on that coordinate. Then to construct any vector just use the negative $-1$ vector plus indicator functions.
05.01.2024 16:49
It also appeared in BRAZIL TST 2023
21.03.2024 23:15
Extremely Nice Problem! We claim that $s=3$
18.05.2024 02:42
Assume for the sake of contradiction that two tuples is possible. Firstly, note that if $v_i\ge cv_j$ and $w_i\ge cw_j$ for some nonnegative $c$ then $v_i+w_i\ge c(v_j+w_j)$ and \[\max(v_i,w_i)\ge\max(cv_j,cw_j)=c\max(v_j,w_j)\]so if we start with only two tuples $\mathbf{v}$ and $\mathbf{w}$, and there exist indices $i$ and $j$ that make the above true then any tuple Lucy generates will also satisfy the same inequality, so Lucy cannot generate any tuples $\mathbf{t}$ for which $t_i\le ct_j$. $~$ Secondly, note that if $v_i,w_i\ge 0$ or $v_i,w_i\le 0$ then any tuple Lucy produces will preserve the sign of that index, so $v_i\ge 0\implies w_i< 0$. By pigeonhole principle, then, there exists two indices $i,j$ such that $v_i,v_j>0$ and $w_i,w_j<0$. Then, let $v_i=cv_j$, so we have $w_i\le cw_j$. However, then $w_j\ge \tfrac1c w_i$ and $v_j\ge \tfrac1c v_i$ which is a contradiction. $~$ Now we prove that three tuples is possible. Note that it suffices to show that Lucy can generate all of the following: a tuple with all zeroes except the $i$th index, which is $1$, for all $i$, and a tuple with all $-1$s. Our construction is: \begin{align*} \mathbf{u}&=(-1,-1,-1,\dots,-1)\\ \mathbf{v}&=(2,4,6,8,\dots,4044)\\ \mathbf{w}&=(C-1,C-4,C-9,C-16,\dots,C-2022^2) \end{align*}where $C$ is extremely large. Consider the $i$th index of $k\mathbf{v}+\mathbf{w}$ for some nonnegative integer $k$, which is $k(2i)+C-i^2$. Over all indices $i$, this is maximized when $i=k$. Thus, for all indices $i$ we can construct a tuple for which the $i$th term is the unique largest. Then, we repeatedly add $u$ to it until we get a tuple $\mathbf{z_1}$ whose terms are all nonpositive except the $i$th index, which is $1$ and a tuple $\mathbf{z_2}$ whose terms are all negative except the $i$th index, which is $0$. Take $\mathbf{z_2}\lor u$, which is the tuple with all $-1$s except the $i$th index, which is $0$. Then, do this for each $i$ and $\lor$ all of them to get an the zero tuple, $\mathbf{0}$. Now, take $\mathbf{z_1}\lor \mathbf{0}$ to get the desired tuple that is all zeroes except the $i$th index, which is $1$.
30.06.2024 03:12
How did you find the squares numbers?