What is the minimal numbers to collect from arrays of numbers?

Question

Suppose I have $k$ arrays of numbers: $v_1,v_2,\ldots, v_k$, each array has length $l$, denoted by $l(v_1)=l(v_2)=\ldots=l(v_k)$, where $l(v_i)$ is just the cardinality of $v_i$. Each $v_i\subset [d]=\{1,\ldots,d\}$. Now, pick First $a_1,a_2,\ldots,a_k\geq 0$ entries from $v_1,v_2,\ldots,v_k$ respectively. I call a natural number $N$ good if for every $(a_1,a_2,\ldots,a_k)$ such that $a_1+a_2+\ldots+a_k=N$ we have $v_1[1:a_1]\cup v_2[1:a_2]\cup\ldots\cup v_k[1:a_k]=[d]$. The question is what is the minimal good number ?

Example: Let $v_1=\{1,2,3,4\}, v_2=\{5,6,2,1\}, v_3=\{4,3,6,5\}$, then $v_1,v_2,v_3\subset [6]=\{1,2,3,4,5,6\}$. The minimal good number $N$ is $8$. In this case, $6$ is not a good number because although $a_1=4,a_2=2,a_3=0$ such that $a_1+a_2+a_3=6$ and $\{1,2,3,4\}\cup\{5,6\}=[6]$, $a_1=4,a_2=0,a_3=2$ such that $a_1+a_2+a_3=6$ but $\{1,2,3,4\}\cup\{4,3\}=\{1,2,3,4\}\neq [6]$.

Answer 1

Ok, it sounds like you are asking the following question, which I think is pretty interesting and to which I think I have an answer [thanks to the comment by Junyan Xu!].

Given $k$-many $\ell$-length lists $v_i$ of numbers from $\{1,\dots d\}$, what is the smallest $N$ so that if you choose a total of $N$ terms from these lists by choosing initial segments from each list, you must obtain every number from $1$ to $d$? [The value of $N$ of course depends on the particular $v_i$, but I won’t represent that dependence in the notation below.]

Let’s first think about how you can be sure you choose the number $1$. Let $v_i^1$ be the leftmost position of $1$ in $v_i$. (Let $v_i^1=\infty$ if $1$ is not in $v_i$, though we won’t need to worry about that.) Then in order to get $1$ from any choice of initial segments, you must guarantee to have chosen either the first $v_1^1$ elements of $v_1$ or the first $v_2^1$ elements of $v_2$ or ... the first $v_k^1$ elements of $v_k$, omitting from the requirement choosing from any $v_i$ where $v_i^1=\infty$.

This is pretty messy to express, but you could let $J_i=\{j:i\mbox{ appears in }v_k\}$ and then your choices of initial segment lengths $a_i$ must satisfy $a_i\ge v_i^1$ for at least one $i\in J_1$. Your $N$ for these particular $v_i$ must then force the requirement that $a_i\ge v_i^1$ for at least one $i\in J_1$ whenever $\sum_{i=1}^k a_i=N$.

Now thinking about all the numbers in $[d]$, you must choose $N$ large enough that for any sequence $a_i$ with $\sum_{i=1}^k a_i=N$, you can be sure that it is the case for all $p\in [d]$ that $a_i\ge v_i^p$ for at least one $i\in J_p$.

In order to guarantee that you get just the number $1$, you must choose enough positions in total to guarantee that you choose at least $\min_i(v_i^1)$ numbers from some $i\in J_1$. You could fail to do this if $N$ equaled $f(1)=(d-|J_1|)\ell+\sum_{i\notin J_1}\cdot(v_i^1-1)$.

So [and I didn’t think this through in my original answer] it should be sufficient that $N$ just be at least as big as $f(i)+1$ for each $i$. If it is, you can’t choose $a_i$ to avoid any particular number, and if it is not, you can choose $a_i$ to avoid at least one number.